fc2ブログ



ユークリッドの互除法

2006.04.26 23:50  整数

ユークリッドの互除法は、

x ≧ y のとき、gcd(x, y) と gcd(y, x%y) は等しい

という定理を用いて、x と y の最大公約数を効率良く求めるアルゴリズムです。
(ここで、x%y は x を y で割った余りを示します)

具体的な例を見てみましょう。

gcd(54, 20) (54 % 20 = 14)
= gcd(20, 14) (20 % 14 = 6)
= gcd(14, 6) (14 % 6 = 2)
= gcd(6, 2) (6 % 2 = 0)
= gcd(2, 0)
= 2

ユークリッドの互除法を実装したプログラム例です。

001 int gcd( int x, int y ){
002     int r;
003     // x ≧ y を満たすことを保障する
004     if ( x < y ) swap( x, y );
005     
006     while ( y > 0 ){
007         r = x % y;
008         x = y;
009         y = r;
010     }
011     
012     return x;
013 }



定理の証明,,,,
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |




最大公約数

2006.04.26 23:21  整数

2つの正の整数 x と y の最大公約数とは

x / d と y / d の余りがともに 0 となる d のうち最大のもの

を言います。最大公約数は英語で Greatest Common Divisor と言われ、一般的に gcd と略されます。いくつか例を見てみましょう。

gcd(35, 14) = 7
(公約数 1, 7 のうち最大の数である 7)
gcd(128, 192) = 64
(公約数 1, 2, 4, 8, 16, 32, 64 のうち最大の数である 64)


誰もが思いつく最大公約数を求める方法が、以下の力任せのアルゴリズムです。

001 int gcd( int x, int y ){
002     int n;
003     n = min( x, y ); // x と y の小さい方
004     // n から 1 までの数で、x と y を順に割っていき、
005     // 余りが 0 になったらその数を返す
006     for ( int d = n; d >= 1; d-- ){
007         if ( x % d == 0 && y % d == 0 ) return d;
008     }
009     assert ( false ); // 入力に 0 がきたらエラー
010 }


このアルゴリズムは実用的ではありません。

| コメント(0) | トラックバック(0) | ↑ページトップ |




最短経路

2006.04.26 22:53  グラフ 最短経路

Shortest path problem (最短経路問題) とは、重みつきグラフ G(V, E) において、ある与えられたノード x, y を接続する path の中で、エッジの重みの総和が最小である path を求める問題です。この問題には、様々な応用がありますが、以下の2つが重要です。

Single Source Shortest Path (SSSP) problem
グラフ G において、与えられた1つのノード s から、他の全てのノードへの最短経路を求める問題。
All Pairs Shortest Path (APSP) problem
グラフ G において、全ての "ノードのペア" 間の最短経路を求める問題。

Single Source Shortest Path Problem (単一始点最短経路)

G(V, E) をエッジのコスト(長さ)が非負である重みつきグラフとし、s を、G のノードとします。ただし、s から G の全てのノードに対して経路があるものとします。このとき、s を根とし、s から G の全てのノードへの最短経路を包含する G の spanning tree T が存在します。このような tree を shortest path spanning tree といいます。以下に例を示します。

SP.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |




Kruskal's Algorithm クラスカルのアルゴリズム

2006.04.26 22:53  グラフ 最小全域木

Kruskal's Algorithm は、グラフ G(V, E) の MST を求めるためのアルゴリズムです。これも Greedy Algorithm で、各計算ステップで、最も適したエッジを選び、MST を求めます。このアルゴリズムを実装するために必要なデータ構造が Disjoint Sets です。Kruskal's Algorithm は以下のように実装します。

グラフ G(V, E) のノード全体の集合を V
エッジ全体の集合を E
MST に属するノードの集合を T とし、
Disjoint Sets のデータ構造 dset を用意します。
1. V の全ての要素 v を互いに素な集合とします
つまり、全ての v に対して dset.makeSet( v ) を行います。
2. E を、重みが小さい順に整列します。
3. E から順番にエッジ (u, v) を取得し、以下の処理を行います。
もし uv が同じ集合に属していないならば
つまり、dset.findSet( u ) ≠ dset.findSet( v ) ならば、
    u, vT に追加し、
    u, v を合併する。すなわち dset.union( u, v ) を行います。


class edge{
    public:
    int source, target;
    double cost;
    edge(){}
    edge( int source, int target, double cost ):
    source(source), target(target), cost(cost){}
    
    bool operator < ( const edge &e ) const{
        return cost < e.cost;
    }
};

int N;
vector<edge> edges;

void kruskal( vector<edge> &mst ){
    
    sort( edges.begin(), edges.end() );
    
    DisjointSet dset = DisjointSet( N );
    
    for ( int i = 0; i < N; i++ ) dset.makeSet( i );
    
    int source, target;
    for ( int i = 0; i < edges.size(); i++ ){
        edge e = edges[i];
        if ( dset.findSet( e.source ) != dset.findSet( e.target ) ){
            mst.push_back( e );
            dset.union( e.source, e.target );
        }
    }
}

| コメント(0) | トラックバック(0) | ↑ページトップ |




Prim's Algorithm プリムのアルゴリズム

2006.04.26 22:52  グラフ 最小全域木

Prim's Algorithm は、グラフ G(V, E) の最小全域木 (MST) を求めるための、最も一般的なアルゴリズムです。基本的な考え方は以下のようになります。

グラフ G(V, E) のノード全体の集合を V
MST に属するノードの集合を T とします。
1. G(V, E) から任意のノード r を選び、それを MST のルートとして、T に追加します。
2. 以下のようなエッジ (u, v) を選択します。
uT に属し、vV - T に属する。
- エッジ (u, v) は、T に属するノードとV - T に属するノードをつなぐエッジの中で、重みが最小のものである。
vT に追加します。
この処理を、T = V になるまで繰り返します。

このアルゴリズムを実装するポイントは、各選択ステップで "どのように最小の重みをもつエッジを記録するか" です。Prim's Algorithm は以下のように実装します。

グラフ G(V, E) のノード全体の集合を V
MST を属するノードの集合を T
とし、各ノードに値 cost, pi を割り当てます。
1. 初期状態で、T は空です。
G(V, E) から任意のノード r を選び、
  cost[r] = 0
  pi[r] = -1
と初期化します。
2. ノードの集合 V - T の中から、cost[u] が最も小さいノード u を選択します。
uT に追加すると同時に、u に隣接しかつ V - T に属する全てのノード v に対する値を以下のように更新します。
もし、 エッジ (u, v) の重み ≦ cost[v] ならば、
  cost[v] = エッジ (u, v) の重み
  pi[v] = u
この処理を T = V となるまで繰り返します。

(cost[v]pi[v]) には、T に属するノード u と、V - T に属するノード v をつなぐエッジの中で、重みが最小のエッジの情報が記録されます。cost[v] には重みを、pi[v] には、ノード u、つまり MST におけるノード v の親が記録されます。従って、各ステップで、ノード u を選択するという操作は、「T に属するノードと V - T に属するノードをつなぐエッジの中で、重みが最小のもの」を選ぶ操作に相当します。 また、u が選ばれた時点で、エッジ ( u, pi[u] ) が MST を構成するエッジとなります。


primStep.gif

001 int N;
002 int M[MAX][MAX];
003 
004 void prim(){
005     dist = 0.0;
006     
007     bool visited[MAX];
008     int cost[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < N; i++ ){
012         visited[i] = false;
013         cost[i] = INT_MAX;
014     }
015     
016     cost[0] = 0;
017     pi[0] = -1;
018     
019     while ( 1 ){
020         int mincost = INT_MAX;
021         int u;
022         // cost が最小となるノード u を選択する
023         for ( int i = 0; i < N; i++ ){
024             if ( !visited[i] && cost[i] < mincost ){
025                 mincost = cost[i];
026                 u = i;
027             }
028         }
029         
030         // すべてのノードが MST に含まれたとき
031         if ( mincost == INT_MAX ) break;
032         
033         visited[u] = true;
034         
035         for ( int v = 0; v < N; v++ ){
036             if ( visited[v] || M[u][v] == INT_MAX ) continue;
037             // 更新処理
038             if ( M[u][v] < cost[v] ){
039                 cost[v] = M[u][v];
040                 pi[v] = u;
041             }
042         }
043     }
044 }

| コメント(0) | トラックバック(0) | ↑ページトップ |




最小全域木

2006.04.26 22:52  グラフ 最小全域木

Tree
木 (tree)とは、閉路をもたないグラフのことを言います。以下に例を示します。下図の左のグラフは、例えば、0 → 3 → 1 → 0 のような閉路をもつので、木ではありません。一方、残りの2つは、閉路をもたないグラフなので木です。 あるノード r から v まで、必ず1通りの path があります。

isTree.gif

Spanning Tree
グラフ G(V, E) の極大木(spanning tree)G(V', E') とは、グラフの全ての頂点 V を含む部分グラフであって(V = V')、木である限りできるだけ多くのエッジを持つものをいいます。グラフの極大木は、DFS または BFS で求めることができます。グラフの極大木は1つとは限りません。以下に、与えられたグラフの極大木の例を示します。

ST.gif

Minimum Spanning Tree
最小極大木 (minimum spanning tree)とは、与えられたグラフの極大木の中で、エッジの重みの総和が最小のものをいいます。以下に、与えられたグラフの最小極大木の例を示します。

MST.gif


最小極大木を求めることは、現実問題で非常に重要になり、多くの応用をもちます。例えば、グラフ G の各ノード u を都市とし、各エッジ (u, v) の重みを都市 u から都市 v への高速道路を建設する費用とすれば、G の最小全域木は、すべての都市を結ぶ高速道路網を可能な限り最小の費用で建設する解となります。

| コメント(0) | トラックバック(0) | ↑ページトップ |




貪欲なアルゴリズム

2006.04.26 22:51  グラフ 最小全域木

多くの実用的なアルゴリズムは、「解の一部を選択する計算ステップの繰り返し」という構成になっています。Greedy Algorithm (貪欲アルゴリズム、よくばり法)は、各計算ステップで、局所的に最適(その時点で最も最適と思われるもの)な選択を繰り返し、最終的に大域的な最適解を求める方法です。

さらに一般化すると、Greedy Algorithm では、候補の集合 C、すでに選択された要素の集合 S、各ステップで、まだ選ばれていない候補の中から最適とされる要素を決定する選択関数 F、から成ります。最初は、選択された要素の集合 S は空で、その後1ステップごとに、候補の集合 C から選択関数 F によって決定された最適な要素を S に追加します。選択された要素は候補 C から取り除かれます。

例えば、これから紹介するグラフの最小全域木を求めるための Prim's AlgorithmKruskal's Algorithm、グラフの単一始点最短経路を求めるための Dijkstra's Algorithm はGreedy Algorithm に分類されます。

この中でも、Prim's Algorithm と Dijkstra's Algorithm は同様の計算スキームをもち、以下のように動作します。

グラフ G(V, E) のノード全体の集合を V
問題の最適解を構成するノードの集合を T
各ノード u に割り当てられる値を cost[u]、 とします。
1. 初期状態で、T は空であり、
T に追加するためのノードの候補の集合は V となります。
任意の(または指定した)ノード s に対応する cost[s] の値を初期化します。
2. 各計算ステップで、cost の値を基に、 ノードの集合 V - T の中から最も良いとされるノード u を選択します。
uT に追加すると同時に、u に隣接しかつ T に含まれない全てのノード v に対する cost[v] を更新します。
この処理を T = V となるまで繰り返します。

| コメント(0) | トラックバック(0) | ↑ページトップ |




単一始点最短経路 (重みなし)

2006.04.26 22:51  グラフ 探索

bfsBack.gif


001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 
005 void breadthFirstSearch( int source ){
006     queue< int > Q;
007     bool visited[MAX];
008     int dist[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < size; i++ ) {
012         visited[i] = false;
013         dist[i] = INT_MAX;
014     }
015     int currentNode = source;
016     
017     Q.push( currentNode );
018     visited[currentNode] = true;
019     dist[currentNode] = 0;
020     pi[currentNode] = -1;
021     
022     while ( !Q.empty() ){
023         currentNode = Q.front(), Q.pop();
024         
025         for ( int nextNode = 0; nextNode < size; nextNode++ ){
026             if ( !adjMatrix[currentNode][nextNode] ) continue;
027             if ( !visited[nextNode] ){
028                 visited[nextNode] = true;
029                 dist[nextNode] = dist[currentNode] + 1;
030                 pi[nextNode] = currentNode;
031                 Q.push( nextNode );
032             }
033         }
034     }
035 }

| コメント(0) | トラックバック(0) | ↑ページトップ |




Ariticulation Points 関節点 切断点

2006.04.26 22:50  グラフ 探索

連結グラフGにおいて、ノード u と、 u から出ている全てのエッジを削除して得られる部分グラフが、もはや連結でなくなってしまうとき、ノード u をグラフ GArticulation Point (関節点または切断点)といいます。例えば、以下に示すグラフで、赤いノードが Articulation Points です。


articulationPoints.gif

連結グラフの Articulation Points を検出することは、実際の問題で非常に重要になります。たとえば、コンピュータの通信網をグラフとしてモデル化した場合、この通信網の Articulation Points になっているコンピュータが故障してしまえば、その通信網は機能しなくなってしまいます。一方、Articulation Points が存在しない連結グラフになれば、たとえ1つのコンピュータが故障しても、他の全てのコンピュータは通信ができることが保障されます。

以下に示す Depth First Search (DFS) の応用によって、連結グラフ G の全ての Articulation Points を検出することができます。

G の任意のノードをスタート点として、DFS を行う。グラフ G の各ノード u に対して、DFS における訪問の順番 prenum[u] を記録します。
DFS によって生成される木(DFS Tree)における u の親 parent[u] を記録します。ここで、この DFS Tree を T とします。
各ノード u に対して、以下のうちの最小値として lowest[u] を計算すます。
i.prenum[u]
ii.GBack edge (u, v) が存在するとき、ノード v における prenum[v]. Back edge (u, v) とは、ノード u から T に属するノード v に向かう T に属さない G のエッジです 
iii.T に属するノード u のすべての子供 x に対する lowest[x]
Articulation Points は以下のように決定されます
(1)T のルート r が2つ以上の子供をもつとき(必要十分条件)、 rG の Articulation Point です。
(2)各ノード u において、u の親 parent[u] p とすると、prenum[p] ≦ lowest[u] ならば(必要十分条件)、p は Articulation Point である(p がルートの場合は (1) を適用します)。

具体的な例を考えてみましょう。

Example 1

以下の図はグラフ G と、G をノード 0 から DFS を行った DFS Tree T を表しています。T において、Back edges は点線で表されていて、各ノードの左側にそれぞれ prenum[u]lowest[u] が示されています。

prenum[u] は DFS において各ノード u が訪問される順番(pre-order): 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 という順番で記録されます。

lowest[u] は DFS において各ノード u の訪問が"終了"する順番(post-order): 4 → 7 → 6 → 5 → 3 → 2 → 1 → 0 という順番で"決定"されます。lowest[u] がどのように"更新"されていくかは、後ほど説明します。

Graph : G DFS Tree : T
artPointG1.gif
artPointT1.gif


(1) より
T のルートであるノード 0 の子供の数は 1 つなので、ノード 0 は Articulation Point ではありません。

(2) より
各ノード u の親を p とすると prenum[p] ≦ lowest[u] を満たすかをチェックします。

case 1. ノード 5 (親がノード 3)に注目します
prenum[3] ≦ lowest[5] を満たす (4 ≦ 6)ので、ノード 3 が Articulation Point になります。つまり、ノード 5 またはノード 5 から Tのノードを任意の数だけ下にたどったノード 5 の子孫から、ノード 3 の祖先へのエッジがないことを示しています。

case 2. ノード 2 (親がノード 1)に注目します
prenum[1] ≦ lowest[2] を満たさないので、ノード 1 は Articulation Point ではありません。つまり、ノード 2 またはノード 2 の子孫から、ノード 1 の祖先へのエッジが存在していることを示しています。

以下の例も考えてみましょう。

Example 2

Graph : G DFS Tree : T
artPointG2.gif
artPointT2.gif


#define SIZE 1000

Graph graph = Graph( SIZE ); // graph structure
bool visited[SIZE];

int prenum[SIZE]; int parent[SIZE]; int lowest[SIZE]; int timer;

void dfs( int current, int prev ){

    // ノード current を訪問した直後の処理
    prenum[current] = timer; lowest[current] = timer;
    timer++;

    visited[current] = true;

    int next;

    while ( (next = graph.next( current )) != graph.END ){
        if ( !visited[next] ){
            // ノード current からノード next へ訪問する直前の処理
            parent[next] = current;

            dfs( next, current );

            // ノード next の探索が終了した直後の処理
            lowest[current] = min( lowest[current], lowest[next] );
        } else if ( next != prev ){
            // エッジ current --> next が Back-edge の場合の処理
            lowest[current] = min( lowest[current], prenum[next] );
        }
    }

    // ノード current の探索が終了した直後の処理


}

void depthFirstSearchScheme(){
    for ( int i = 0; i < SIZE; i++ ) visited[ i ] = false;
    int root = 0;
    timer = 1;
      
    graph.reset();

    // lowest の計算
    dfs( root, -1 );
}

| コメント(2) | トラックバック(0) | ↑ページトップ |




幅優先探索木 Breadth First Search Tree

2006.04.26 22:50  グラフ 探索

| コメント(0) | トラックバック(0) | ↑ページトップ |




深さ優先探索木 Depth First Search Tree

2006.04.26 22:49  グラフ 探索

| コメント(0) | トラックバック(0) | ↑ページトップ |




グラフのプロパティ

2006.04.23 20:57  グラフ

作成中

| コメント(0) | トラックバック(0) | ↑ページトップ |




幅優先探索 Breadth First Search (BFS)

2006.04.21 00:01  グラフ 探索

Breadth Frist Search (幅優先探索)は、グラフの全てのノードをシステマティックに訪問するためのアルゴリズムの1つで、以下の例のような様々なグラフの問題に応用されます。

  • グラフの連結性(connectivity)
  • グラフの連結成分(connected component)
  • グラフの最短経路問題(重み無し)
  • Maximum flow (最大流)
  • 探索
  • etc.


see-try-see

BFS は以下のようにノードを訪問します。

1. 最初に訪問するノードを決め、その番号をキュー(FIFO)に入れる
2. キューの先頭からノード番号を取り出し、そのノードを訪問し、そのノードに隣接した未訪問である全てのノードの番号をキューに入れる。キューが空になるまで 2 を繰り返す

このアルゴリズムを実装するためには、FIFO (First In First Out)の仕組みをもつキューのデータ構造が必要であり、プログラムの雛形が以下のようになります。

void breadthFirstSearch(){
    
  最初に訪問するノードをキューに入れる

    while ( キューが空でない間 ){
        キューの先頭からノード currentNode を取り出す

    ( currentNode に隣接しているノード nextNode を探す ){
        
            nextNode が未訪問ならば nextNode を訪問済みとし、
            キューに入れる

        }
    }
}



隣接行列による BFS の実装例です。

001 #define MAX 1000
002 int size;
003 int adjMatrix[ MAX ][ MAX ]; // graph structure
004 
005 void breadthFirstSearch(){
006     queue< int > Q;
007     bool visited[ MAX ];
008     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
009     int currentNode = 0;
010     
011     Q.push( currentNode );
012     visited[ currentNode ] = true;
013     
014     while ( !Q.empty() ){
015         currentNode = Q.front(), Q.pop();
016         
017         cout << currentNode << endl;
018         
019         for ( int nextNode = 0; nextNode < size; nextNode++ ){
020             if ( !adjMatrix[ currentNode ][ nextNode ] ) continue;
021             if ( !visited[ nextNode ] ){
022                 visited[ nextNode ] = true;
023                 Q.push( nextNode );
024             }
025         }
026     }
027 }
028 
029 void inputGraph(){
030     cin >> size;
031     for ( int i = 0; i < size; i++ ){
032         for ( int j = 0; j < size; j++ ){
033             adjMatrix[i][j] = 0;
034         }
035     }
036     
037     int source, target;
038     for ( int i = 0; i < size; i++ ){
039         for ( int j = 0; j < size; j++ ){
040             cin >> adjMatrix[i][j];
041         }
042     }
043 }
044 
045 int main(){
046     inputGraph();
047     breadthFirstSearch();
048     
049     return 0;
050 }

| コメント(0) | トラックバック(0) | ↑ページトップ |




深さ優先探索 Depth First Search (DFS)

2006.04.21 00:01  グラフ 探索

Depth Frist Search (深さ優先探索)は、グラフの全てのノードをシステマティックに訪問するための、最も自然で基本的なアルゴリズムです。DFS は以下の例のような様々なグラフの問題に応用されます。


see-try-see

DFS は以下のようにノードを訪問します。

1. 最初に訪問するノードを決める(任意のノード)
2. ノードを訪問した後、以下のようにして次に訪問するノードを探す
そのノードに隣接した未訪問のノードがあれば、そのノードのどれか(任意のノードでよい)を訪問し、2 の処理へ

未訪問のノードがなければ、今訪問しているノードの前のノードに引き返して、2の処理の続きを行う(つまり、前のノードにおいて、次に訪問するノード探しの続きを行う)

このアルゴリズムを実装するために必要なプログラミングテクニックが「再帰」であり、プログラムの雛形が以下のようになります。

void depthFirstSearch( int currentNode ){
    
    currentNode を訪問済みとする

    ( currentNode に隣接しているノード nextNode を探す ){

        nextNode が未訪問ならば depthFirstSearch( nextNode );

    }
}


隣接行列による DFS の実装例です。

001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 bool visited[MAX];
005 
006 void dfs( int currentNode ){
007     visited[ currentNode ] = true;
008     
009     // perform some activities here
010     
011     for ( int nextNode = 0; nextNode < size; nextNode++ ){
012         if ( !adjMatrix[ currentNode ][ nextNode ] ) continue;
013         if ( !visited[ nextNode ] ){
014             dfs( nextNode );
015         }
016     }
017 }
018 
019 void depthFirstSearch(){
020     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
021     int startNode = 0;
022     
023     dfs( startNode );
024 }
025 
026 void inputGraph(){
027     cin >> size;
028     
029     for ( int i = 0; i < size; i++ ){
030         for ( int j = 0; j < size; j++ ){
031             adjMatrix[i][j] = 0;
032         }
033     }
034     
035     int source, target;
036     // input based on adjMatrix
037     for ( int source = 0; source < size; source++ ){
038         for ( int target = 0; target < size; target++ ){
039             cin >> adjMatrix[source][target];
040         }
041     }
042 }
043 
044 int main(){
045     inputGraph();
046     depthFirstSearch();
047     
048     return 0;
049 }


隣接リストによる DFS の実装例です。

class Graph{
    private:
    vector<vector<int> > adjList;
    vector<vector<int>::iterator> pos;

    public:
    static const int END = -1;
    Graph(){}
    Graph( int n ) { resize(n); }

    void resize( int n ){
	adjList.resize(n), pos.resize(n);
	for ( int i = 0; i < n; i++ ){
	    adjList[i].clear();
	}
    }
    
    int size(){ return adjList.size(); }

    void insert( int source, int target ){
	adjList[source].push_back( target );
    }
    
    int next( int source ){
	if ( pos[source] == adjList[source].end() ) return END;
	return *pos[source]++;
    }
    
    void reset( int i ){ pos[i] = adjList[i].begin(); }
    void reset(){ for ( int i = 0; i < size(); i++ ) reset(i); }
};

Graph graph = Graph( SIZE ); // graph structure
bool visited[ SIZE ];

void dfs( int currentNode ){

    visited[ currentNode ] = true;

    int nextNode;

    while ( (nextNode = graph.next( currentNode )) != graph.END ){
	if ( visited[ nextNode ] ) continue;
	dfs( nextNode );
    }
}

void depthFirstSearchScheme(){
    for ( int i = 0; i < SIZE; i++ ) visited[ i ] = false;
    int startNode = 0;

    graph.reset();
    dfs( startNode );
}

void inputGraph(){

    int source, target;
    // input based on adjList
    cout << "input edges: ";
    while (1){
	cin >> source >> target;
	if ( source == -1 && target == -1 ) break;
	graph.insert( source, target );
	graph.insert( target, source );
    }
}

int main(){
    inputGraph();
    depthFirstSearchScheme();

    return 0;
}

| コメント(0) | トラックバック(0) | ↑ページトップ |




隣接リスト

2006.04.21 00:00  グラフ

各ノードが、そのノードに隣接するノードの番号のリストを持ちます。重みつきグラフの場合は、番号だけではなく重みもリストの要素に追加されます。リストの最後に番兵を設置しておくと便利です。

有向グラフ
DUList.gif


重みつき有向グラフ
DWList.gif


隣接リスト表現の特徴
  • エッジの数に比例したメモリしか必要としない
  • ノード u とノード v の関係を調べるには、リストを探索しなければならない
  • エッジの追加・削除の操作が難しく、効率的に行えない
  • 実装がやや難しい

| コメント(0) | トラックバック(0) | ↑ページトップ |




隣接行列

2006.04.21 00:00  グラフ

行列という名の通り、グラフを2次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この2次元配列を M とすると、M[i][j] がノード i とノード j の関係を表します。


無向グラフ
ノード i とノード j の間にエッジがある場合、M[i][j]M[j][i] の値を 1 とします。エッジがない場合は 0 とします。隣接行列は右上と左下が対照になります。

UUMatrix.gif


有向グラフ
ノード i からノード j へ向かってエッジがある場合、M[i][j] の値を 1 とします。エッジがない場合は 0 とします。

DUMatrix.gif


重みつき無向グラフ
ノード i とノード j の間に重さ w のエッジがある場合、M[i][j]M[j][i] の値を w とします。エッジがない場合は、問題上有り得ない値に設定します。例ではとしていますが、プログラムでは非常に大きな値に設定しておくと便利な場合が多いです。

UWMatrix.gif


重みつき有向グラフ
ノード i からノード j へ向かって重さ w のエッジがある場合、M[i][j] の値を w とします。エッジがない場合は、非常に大きな値に設定します。
DWMatrix.gif


隣接行列表現の特徴
  • M[u][v] でエッジを参照できるので、ノード u とノード v の関係を定数時間でチェックすることができる
  • エッジの追加や削除が簡単かつ効率的(定数時間)
  • ノードの数が増えるとメモリをかなり消費する。ノード数を n とすると、n^2 のスペースが必要

| コメント(0) | トラックバック(0) | ↑ページトップ |




選択ソート セレクションソート Selection Sort

2006.04.20 00:13  整列

選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの1つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

選択ソート
各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
selectionSortStep2.gif
1.「未ソートの部分」から最小の要素を探します。
選択ソート
2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
選択ソート
1. 2. を未ソートの部分がなくなるまで繰り返します。

選択ソート
1. 初期状態は全ての要素が未ソートの部分に属します。
2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。
3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。
4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。
5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。
6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。
7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。
8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。
9. ソートが完了します。


選択ソートインデックス

Program は、データの数 size を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。

選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n2-n)/2となり、選択ソートはO(n2)のアルゴリズムとなります。

| コメント(0) | トラックバック(0) | ↑ページトップ |




ソートのアルゴリズム

2006.04.20 00:08  整列

様々なソートアルゴリズムが考案されてきましたが、用途やデータの特徴、またはプログラムで使うデータ構造などに応じて、それらを的確に選ばなくてはなりません。以下の表は、代表的なソートのアルゴリズムとそれらの効率・特徴を示しています。

アルゴリズムの名前 効率 安定性 特徴
選択ソート
(Selection Sort)
O(n2) × 単純で最も直感的だが、効率が悪い
バブルソート
(Bubble Sort)
O(n2) 単純だが効率が悪い
挿入ソート
(Insertion Sort)
O(n2) ぼぼ整列されているデータに対して効率的
マージソート
(Merge Sort)
O(nlonn) 外部の記憶領域が必要
ヒープソート
(Heap Sort)
O(nlonn) × ヒープのデータ構造を応用する
クイックソート
(Quick Sort)
O(nlonn) × ほぼ整列されているデータに対して効率的ではない


選択ソート、バブルソートはソートのアルゴリズムの導入に紹介されるくらいで、実践で(現場で)使うことはほんとんどありません。データの特徴や問題の仕様に合わせて適切なアルゴリズムを設計することが重要です。マージソートは安定で高速、しかも実装が比較的容易なのでおすすめです。クイックソートは、理論上最速と言われていますが、安定ではないので注意が必要です。

| コメント(0) | トラックバック(0) | ↑ページトップ |




安定なソート

2006.04.20 00:06  整列

アルゴリズムを設計、選ぶ際に重要なポイントとなるのがその効率ですが、整列のアルゴリズムに関しては、それが「安定なソート」であるかを考慮に入れなくてはなりません。安定なソートとは、キーの値が同じ要素が2つ以上あるデータセットにおいては、それらの要素をソート前とソート後で順番が変わらないようなソート方法です。以下の例を見てみましょう。


stableSort.gif


上の例は、同じデータを整列したもので、どちらの配列もデータが昇順に並べ替えられましたが、左が「安定なソート」、右が「安定でないソート」です。このデータには、2つの「3」があります。「緑の3」と「青の3」です。初期データは、「緑の3」→「青の3」の順番となっていますが、「安定なソート」ではこの順番が保たれています。一方、「安定でないソート」では、「青の3」→「緑の3」と順番が逆になっています。

このソートの安定性を考慮に入れなければ、思わぬ失敗をしてしまいます。




stableSortCards.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |




整列 ソート

2006.04.20 00:05  整列

整列されたデータは探索(検索)し易い、ということをすでに紹介しました。データの整列は、多くのアルゴリズムの基礎になります。たくさんのデータを、あるキーに従って昇順(小さい順)または降順(大きい順)に整列するためのアルゴリズムをいくつか記録したいと思います。

sort.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |




グラフの表現

2006.04.19 18:10  グラフ

グラフはコンピュータ上で表されるデータ構造の一種です。コンピュータの中で、問題に応じたグラフ構造を効率的に表現し操作されるようなプログラムを実装しなければなりません。

プログラム上でグラフを表現し操作する代表的な方法に、
隣接行列 (adjacency matrices)による表現と、
隣接リスト (adjacency lists)による表現があります。

これらの方法とその特徴を簡単に紹介します。

| コメント(1) | トラックバック(0) | ↑ページトップ |




グラフの種類

2006.04.19 18:09  グラフ

グラフの種類には大きく分けて4つあります。

名前 特徴
無向グラフ エッジに方向がない
有向グラフ エッジに方向がある
重みつき無向グラフ エッジに重みがあり、方向がない
重みつき有向グラフ エッジに重みがあり、方向がある


無向グラフの例

友達関係をグラフにした例です。この例ではエッジに方向をもたせていません。例えば、「友達の友達は友達としたとき、A君とB君は友達ですか?」や「いくつの友達グループがありますか?」などの問題が考えられます。

graphExample1.gif

有向グラフの例

物事の手順をグラフにした例です。朝起きてから学校に行くまでの簡単な手順を示していますが、このグラフから様々な要素が読み取れます。例えば、朝起きてから朝食を食べなくても学校へ行けますが、着替えなければ学校には行けないことが分かります。起きて→着替えて→学校へ行く、というのがこの手順の最短経路となります。

graphExample2.gif

重みつき無向グラフの例

各ノードが市町を表し、エッジが市町を行き来するのにかかる時間を表しています(架空のもの)。ある町からある町への最短経路を求めたいなどの類の問題はよくあります。

graphExample3.gif


ここで取り上げたものは、ほんの例でしかありません。「すべての問題はグラフで表せる」と言われるほど、グラフ構造は様々な問題で応用されます。

| コメント(0) | トラックバック(0) | ↑ページトップ |




グラフとは

2006.04.19 18:09  グラフ


グラフ(Graph)とは「対象の集合と、それらのつながりの集合」を表すためのデータ構造で、様々な問題に応用されます。現実世界のあらゆる問題をモデル化することができるので、グラフに関する重要なアルゴリズムが数多く存在します。

簡単なグラフの例を以下に示します。


graph.gif



「対象」はノード(node)またはバーテックス(vertex)と呼ばれ、上図の円に相当します。「つながり」はノードとノードの関係を表し、エッジ(edge)と呼ばれ、上図で円と円を結んでいる線に相当します。

グラフには様々な種類があり、問題によって応用の方法も違ってきます。

| コメント(0) | トラックバック(0) | ↑ページトップ |




キュー (待ち行列) Queue

2006.04.19 17:03  データ構造

キューは「待ち行列」とも呼ばれ、データを到着順に処理したいときに使用するデータ構 造で、データの中で最初に入ったものが最初に取り出される、先入れ先出し(FIFO: First In First Out)のルールに従ってデータを管理します。スーパーのレジやATMの待ち行列にお ける人々の動きやそこにある暗黙のルール(割り込みや追い越しの禁止)は、キューのデー タ構造そのものです。

キューの操作
  • enqueue(x): キューの末尾に要素 x を追加します。
  • dequeue(): キューの先頭から要素を取り出します。
  • isEmpty(): キューが空かどうかを調べます。
  • isFull(): キューが満杯かどうかを調べます。

実用的なキューには、これらの他にもキューの先頭の要素を参照したり、キューに指定され たデータが含まれているかを調べたりするオプション的な操作も含まれますが、ここでは上 記4つの操作を含むキューを実装します。

キューの制約
  • データの中で最初に入ったものが最初に取り出されます。


整数型のデータが格納されるキューを配列を用いて実装します。以下に、実装に必要なもの を示します(下図参照)。

array queue


データを格納するための整数型1 次元配列: buffer
配列buffer の各要素にエンキューされたデータを格納していきます。問題に応じた十分な 記憶領域を確保することが必要です。Fig.4.3-1 では、既にいくつかの要素が格納されてい ます。

先頭カーソルである整数型変数:head
キューの先頭の場所を指し示す変数です。dequeue されるとhead で指された要素が取り出 されます。キューの先頭の要素のインデックスが0 とは限らないことに注意して下さい。

末尾カーソルである整数型変数:tail
キューの末尾+ 1 の場所(最後の要素の隣)を指し示す変数です。tail は新しい要素が追加 される場所を示します。

実際にキューのデータ構造を操作する様子を見てみましょう。Fig. 4.3-2は、実際にキューに適当な値を適当に出し入れしている様子を示しています。

array queue 初期化: head = tailのときキューが空になります。初期値はhead = tail = 0とします。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 3 )。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 7 )。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 1 )。

dequeue: headが指す要素を取り出し、headを1増やします (例: 3を取り出す)。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 8 )。

dequeue: headが指す要素を取り出し、headを1増やします (例: 7を取り出す)



このように配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、headとtailに挟まれたキューのデータ本体が配列の末尾に向かって(図の右側に)移動していき、すぐに要領をオーバーしてしまいそうに見えます。

下図に示すように、dequeueされたときにheadを常に0に保つようにデータ全体を配列の先頭に(左に)向かってシフトしていては、dequeueの度にO(n)の計算が必要になってしまいます。一方で、tailが配列の領域を超えた時点でoverflowとしてしまったのでは、まだ使える配列の領域を無駄にしてしまいます。

array queue shift

これらの問題を避けるために、配列によるキューの実装ではFig.4.3-4に示すように、配列をリングバッファとみなしてキュー内のデータを管理します。

array queue ring

リングバッファとは通常の1次元配列で実現しますが、キューの範囲を指し示すカーソルheadまたはtailが配列の領域を超えてしまったときにこれらのカーソルを循環させます。つまり、カーソルを1つ増やして、それが配列の範囲を超えてしまった場合には、カーソルを0にリセットします。

上図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示しています。最初に1を追加したときに、tailの値が1つ増えますが、配列の領域を超えてしまうので、tailを0に設定します。リングバッファを時計回りに見ると、キューにデータがある場合は必ずhead→tailの順番に並びます。

次のは配列によってキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。



main関数
キューのオブジェクトqueueを操作します。無限ループによってキーボードからコマンドcommandの入力を待ち続けます。commandがenqueueであればxを読み込みそれをqueueに追加します。commandがdequeueであればqueueからデータを取り出し、それを出力します。それ以外のcommandが入力されたときループから抜けプログラムが終了します。

initialize
queue を空にします。queue が空のときhead とtail が同じ位置を示します。ここでは初期 値を0 と設定します。

isEmpty
queue が空の場合真を返します。head とtail が同じ値のときキューが空となります。

isFull
queue が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されていま す。head が(tail+1)%MAX に等しいとき、queue が満杯になります。リングバッファを時 計回りに見ると、tail → head の間は常に1 つ以上の空きがあります。

enqueue(x)
queue が満杯の場合は”overflow” と出力します。そうでなければ、tail が指す場所にx を追 加します。queue の要素が1 つ増えたのでtail を1 増やします。ただし、増やした値が配 列の容量であるMAX 以上になってしまう場合はtail を0 として循環させます。

dequeue
queue が空の場合は”underflow” と出力します。そうでなければ、head が指すqueue の先 頭の要素を変数x に一時記録し、head を1 増やしてからx を返します。ただし、head を 増やした値がMAX 以上になってしまう場合はhead を0 として循環させます。

| コメント(1) | トラックバック(0) | ↑ページトップ |




スタック Stack

2006.04.19 17:02  データ構造

スタックは一時的にデータを退避したいときに有効なデータ構造で、データの中で最後に 入ったものが最初に取り出される後入れ先出し(LIFO: Last In First Out)のルールに従いデー タを管理します。例えば、以下の何気ない日常の行動が、スタックのデータ構造をうまく表 現してくれます。

テストの勉強中で以下のような一連の行動をとった場面があるかもしれません。
  • 1. 英語の教科書を読む
  • 2. 分からない単語があったので、辞書を引く
  • 3. 辞書を引いている途中で、友達からメールがキタのでメールを書く
  • 4. メールの返信が終わったので、辞書を引きなおす
  • 5. 単語を理解したので、教科書の続きを読む
  • 6. 教科書を読み終える

この行動の流れをスタックで表わすと以下のようになります:

stack.gif

積み木のように「行動」が順番に重なっていきます。積み木の最上部が進行中の行動で、そ の下にあるもの全てが中断されている行動になります。この例での重要なポイントは、例え ばステップ4 でメールを返信した後に教科書を読むのではなく、メールの対応によって中 断されていた「辞書を引く」ことに戻るということです。

このように、コンピュータにおいても処理していたことを一時的に退避させ、適時それを取 り出して正しい順番で続行しなければならない場面は多くあります。この例では、もし順番 が乱れて単語の意味を理解しないまま教科書を読もうとしてもつまづいてしまいます。この ような行動をコンピュータにおけるデータや処理と置き換えたものが、スタックのデータ構 造です。

スタックの操作
  • push(x): スタックの先頭(頂点)に要素 x を追加します。
  • pop(): スタックの先頭(頂点)から要素を取り出します。
  • isEmpty(): スタックが空かどうかを調べます。
  • isFull(): スタックが満杯かどうかを調べます。

スタックの制約
  • データの中で最後に入ったものが最初に取り出されます。

スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法があります。ここでは、データ構造の操作と制約の理解に重点をおきますので、簡単な例を通して1つの実装方法を示します。整数型のデータが格納されるスタックを配列を用いて実装します。以下に、実装に必要なものを示します(下図参照)。

データを格納するための整数型1次元配列: buffer
配列bufferの各要素にプッシュされたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。また、便宜上 0 番目には常に何も入れないようにします。Fig. 4.2-2は、容量が7のスタックに既に5つの要素が格納されている様子を表しています。

array stack

スタックポインタである整数型変数: top
スタックの頂点の要素(一番最後に追加された要素)を指し示す整数型の変数です。この変数をスタックポインタといいます。またtop の値はスタックの要素数をも示します。

実際にスタックのデータ構造を操作する様子を見てみましょう。Fig. 4.2-3は、実際にスタックに適当な値を適当に出し入れしている様子を示しています。データ構造の操作は動的に発生するものなので、スタックの要素は変動していきます。

array stack 初期化: top = 0としてスタックを空にします。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 3 )。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 12 )。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 1 )。

pop: topが指している要素を取り出し、topを1減らします (例: 1を取り出す)。

pop: topが指している要素を取り出し、topを1減らします (例: 12を取り出す)。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 5 )

以下のプログラムは配列によってスタックを実現し、スタックへのデータの追加・取り出しをシミュレーションします。プログラムは、”push x” (xは整数)とキーボードから入力されると、スタックにxを追加し、”pop” と入力されると、スタックの頂点の要素を取り出しそれを出力します。これら以外の形式が入力されたときプログラムが終了します。
スタックのデータ構造はクラスとして実装されています。クラスとしてデータ構造を実装しておけば、それらを部品として使えるので、プログラムで複数の異なるスタックを使いたい場合などに便利になります。


main 関数
スタックのオブジェクト(※ 1)stack を操作します。無限ループによってキーボードから コマンドcommand の入力を待ち続けます。command がpush であればx を読み込みそれ をstack に追加します。command がpop であればstack からデータを取り出し、それを出 力します。それ以外のcommand が入力されたときループから抜けプログラムが終了します。

initialize
stack を空にします。stack が空のときはtop が0 を指します。

isEmpty
stack が空の場合真を返します。top が0 のときstack が空の状態になります。

isFull
stack が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されています。 top がMAX 以上のときにstack が満杯の状態になります。

push(x)
stack が満杯の場合は”overflow” と出力します。そうでなければ、top を1 つ増やし、その 場所にx を追加します。

pop
stack が空の場合は”underflow” と出力します。そうでなければ、stack の頂点の要素を変数 x に一時記録し、top を1 減らしてからx を返します。



普通は、以下のように便利なライブラリを使います。



練習問題1

see-try-see

| コメント(0) | トラックバック(0) | ↑ページトップ |




データ構造

2006.04.19 17:01  データ構造

データ構造とは、プログラムの中でデータを一定の形式に系統立てて格納するときの形式です。プログラムの中で、どのようなデータ構造を用いたかが、そこで実装されたアルゴリズムの効率に大きく影響します。 データ構造は、
  • 「データの集合」
  • 「データの集合に対する操作」
  • 「データをルールに従って正しく保つための制約」

から成りたっています。

これから記録していきたいデータ構造↓

  • スタック Stack
  • キュー Queue
  • 優先順位キュー Priority Queue
  • Disjoint Sets
  • 二分探索木
  • etc.

| コメント(0) | トラックバック(0) | ↑ページトップ |