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) | ↑ページトップ |