Priority First Search 順位優先探索
2006.05.25 00:03 グラフ 最短経路
Dijkstra's Algorithm のオーダーは、O(|V|^2) (ノードの数の2乗)です。これは、u を S に追加するためのループ(|V| 回)の中で、u を選択するためのループ(|V| 回)を行っていることから、簡単に導くことができます。このオーダーは、隣接行列で実装しても、隣接リストで実装しても同じですが、疎なグラフに対しては隣接リストで実装すべきです。(以下のテーブルを参照して下さい)。
タイプ | 演算回数 | オーダー |
隣接行列 | |V|^2 + |V|^2 | |V|^2 |
隣接リスト | |V|^2 + |E| | |V|^2 |
Dijkstra's Algorithm は、隣接リストによる実装と、Priority Queue (Heap) を応用することによって、効率化することができます。このアルゴリズムは、Priority First Search (順位優先探索) とも呼ばれ、以下のように実装します。
グラフ G(V, E) のノード全体の集合を V、 source をスタート地点、 S を「 source から S 内の各ノード v への最短経路が必ず S 内にあるような、最短経路の部分的な解の集合」とします(Dijkstra's Algorithm 参照)。 |
|
各計算ステップにおいて、V - S の各ノード v について、S 内のノードのみを経由した source から v への最短経路のコスト(距離)を d[v] とします。また、各ノード間のコスト(距離) (x, y) は、行列 M[x][y] に記録されているものとします。 | |
1. |
初期状態で、S は空です。 source に対して   d[s] = 0 source 以外の V に属する全てのノード v に対して   d[v] = ∞ と初期化します。 |
d[v] をキーとして、V - S に属するノードを minimum heap として構築します。これを heap とします。 | |
2. |
heap から d[u] が最小であるノード u を取り出します。 u = heap.extractMin() |
u を S に追加すると同時に、u に隣接しかつ V - S に属する全てのノード v に対する値を以下のように更新します。 | |
d[v] = min( d[v], d[u] + M[u][v] ) d[v] が更新された場合は、heap を更新します。 heap.update( v ) (v から upheap を施します) |
|
この処理を S = V となるまで繰り返します。 |
Priority First Search のオーダーは、O((|V| + |E|)log|V|) となります。u を heap から取り出すために |V|log|V|、d[v] を更新するために |E|log|V| の演算回数が必要です。
Priority First Search のプログラム例を以下に示します。
class Graph{ public: vector<vector<int> > adjList; vector<vector<int>::iterator> pos; Graph(){} Graph( int size ){ resize( size );} void resize( int size ){ adjList.resize( size ); pos.resize( size ); for ( int i = 0; i < size; i++ ) adjList[i].clear(); } int size(){ return adjList.size(); } void insert( int i, int j ){ adjList[i].push_back( j ); } int next( int i ){ if ( pos[i] == adjList[i].end() ) return -1; return *pos[i]++; } void reset( int i ){ pos[i] = adjList[i].begin(); } void reset(){ for( int i = 0; i < size(); i++ ) reset(i); } }; class Heap{ public: int size; int H[MAX + 1]; // heap buffer int index[MAX + 1]; // index of v in the heap buffer int *key; // keys for heap condition Heap(){} Heap( int size, int d[] ): size(size){ key = d; } void construct(){ for ( int i = 0; i < size; i++ ){ H[i + 1] = i; // heap is 1 base not 0 index[i] = i + 1; } for ( int i = size / 2; i >= 1; i-- ) downheap( i ); } int extractMin(){ int v = H[1]; H[1] = H[size]; index[ H[size] ] = 1; size--; downheap(1); return v; } int update( int v ){ upheap( index[v] ); } private: void downheap( int k ){ int j, v; v = H[k]; while( k <= size/2 ){ j = k + k; if ( j < size && key[ H[j] ] > key[ H[j+1] ] ) j++; if ( key[v] <= key[ H[j] ] ) break; H[k] = H[j]; index[ H[j] ] = k; k = j; } H[k] = v; index[ v ] = k; } void upheap( int k){ int v; v = H[k]; while ( k > 1 && key[ H[k/2] ] >= key[v] ){ H[k] = H[k/2]; index[ H[k/2] ] = k; k = k/2; } H[k] = v; index[v] = k; } }; int size; int M[MAX][MAX]; Graph graph; void dijkstra( int s, int d[] ){ bool visited[MAX]; // S に属するノードは true for ( int i = 0; i < size; i++ ){ d[i] = INT_MAX; visited[i] = false; } d[s] = 0; // 最初に s が u として選ばれる Heap heap = Heap( size, d ); heap.construct(); graph.reset(); while( heap.size >= 1 ){ int u = heap.extractMin(); visited[u] = true; // u を S に追加 int v; while ( ( v = graph.next( u ) ) != -1 ){ if ( visited[v] ) continue; if ( d[u] + M[u][v] < d[v] ){ d[v] = d[u] + M[u][v]; heap.update( v ); } } } }
このプログラム例ですと、自作の Heap を使っているので、プログラムが分かりづらくなってしまいました。私は、普段は自作の Heap を使うことはなく、以下のように既存の Priority queue に候補となるノードを突っ込んでいくアルゴリズムを実装しています。
class Graph{ public: vector<vector<int> > adjList; vector<vector<int>::iterator> pos; Graph(){} Graph( int size ){ resize( size );} void resize( int size ){ adjList.resize( size ); pos.resize( size ); for ( int i = 0; i < size; i++ ) adjList[i].clear(); } int size(){ return adjList.size(); } void insert( int i, int j ){ adjList[i].push_back( j ); } int next( int i ){ if ( pos[i] == adjList[i].end() ) return -1; return *pos[i]++; } void reset( int i ){ pos[i] = adjList[i].begin(); } void reset(){ for( int i = 0; i < size(); i++ ) reset(i); } }; class Node{ public: int id, cost; Node(){} Node( int id, int cost ): id(id), cost(cost){} bool operator < ( const Node &n ) const{ return cost > n.cost; } }; int size; int M[MAX][MAX]; Graph graph; void dijkstra( int s, int d[] ){ bool visited[MAX]; // S に属するノードは true for ( int i = 0; i < size; i++ ){ d[i] = INT_MAX; visited[i] = false; } d[s] = 0; priority_queue<Node> PQ; PQ.push( Node( s, 0 ) );// 最初に s が u として選ばれる graph.reset(); while( !PQ.empty() ){ int u = PQ.top().id; PQ.pop(); visited[u] = true; // u を S に追加 int v; while ( ( v = graph.next( u ) ) != -1 ){ if ( visited[v] ) continue; if ( d[u] + M[u][v] < d[v] ){ d[v] = d[u] + M[u][v]; PQ.push( Node( v, d[v] ) ); } } } }
純粋に Heap を用いるのと比べて効率はやや劣りますが(なぜなら priority queue の中に余分なゴミが溜まっていくから)、オーダーがたかだか O((|V| + |E|)log|E|) になるだけなので、私の経験上、実用には問題ないようです。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |