ブログトップ 記事一覧 ログイン 無料ブログ開設

hamadakoichi blog このページをアンテナに追加 RSSフィード

2008-07-20

[][] Dijkstra algorithm 00:29  Dijkstra algorithm - hamadakoichi blog を含むブックマーク  Dijkstra algorithm - hamadakoichi blog のブックマークコメント

Dijkstra algorithm (ダイクストラ アルゴリズム)。


"全てのEdge(辺)のWeight(重み)が非負の場合"に、

重みつき有向グラフ G=(V,E) に対する

Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。

実装の仕方により、Dijkstra algorithmの実行時間は Bellman-Ford algorithmより短くすることができる。

Dijkstra algorithmは、始点 s からの最終的な最短路重みが既に決まっているVertex(頂点)の集合 S を管理する。最小の最短路推定値 d[u] を持つ頂点 u ∈ V-S を選び、u を S に追加し、u から出る辺に対して、緩和操作 Relax の実施を繰り返す。

V-Sの全てのvertexを含み、最短路推定値 dの値をキーとする優先度つき Queue Qを管理する。

Dijkstra(G,w,s)
1. Initialize-Single-Source(G,s)
2. S ← φ
3. Q ← V[G]
4. while Q ≠φ
5.  do u ← Extract-Min(Q)
6.   S ← S ∪ {u}
7.   for each vertex v ∈ Adj[u]
8.    do Relax(u,v,w)

Initialize-Single-Source(G,s), Relax(u,v,w)はRelaxation(緩和操作)を参照


[実行時間(計算量)]

Dijkstra algorithmの実行時間は、"Min-Priority Queue(優先度つきmin-Queue)"の

実装方法に依存している。

 (1) Initialize-Single-Source(G,s)は O(V),

 [Min-Priority Queue操作]

 (2) Insert(3行目)は、      |V|回 × Insert実行時間

 (3) Extract-Min (5行目)は、   |V|回 × Extract-Min実行時間

 (4) Decrease-Key(8行目 Relax)は、|E|回 × Decrease-Key実行時間

   (For Loopの繰り返し数 |E|回)


・[Min-Priority Queueの実装例1:1から|V|に番号が振られた頂点を使用]

 単に配列のv番目の位置に 最短路推定値 d[v] を記憶すればよい。

 [2] Insertの実行時間    ... O(1)

 [3] Extract-Minの実行時間 ... O(V)

 [4] Decrease-Keyの実行時間 ...O(1)

 ⇒全体の実行時間 O(V^2 + E) = O(V^2)


・[Min-Priority Queueの実装例2:min-heapの使用]

 グラフが十分に疎 (E =o(V^2 /logV))である場合の実用的な方法。

 (2) Min-Heapの実現... O(V)

 [3] Extract-Minの実行時間 ... O(logV)

 [4] Decrease-Keyの実行時間 ...O(logV)

 ⇒全体の実行時間 O((V+E)logV)。

  全ての頂点が、始点 s から到達可能な場合、O(E logV)

  (E=o(V^2/logV)の場合における O(V^2)時間の改良)


・[Min-Priority Queueの実装例3:Fibonacci Heap(フィボナッチヒープ)の使用]

 [3] Extra-Minのならし実行時間 ... O(logV)

 [4] Decrease-Keyのならし実行時間...O(1)

 ⇒全体の実行時間 O(VlogV +E)


[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

2008-06-29

[][] DAG-Shortest-Paths algorithm 23:48  DAG-Shortest-Paths algorithm - hamadakoichi blog を含むブックマーク  DAG-Shortest-Paths algorithm - hamadakoichi blog のブックマークコメント

DAG-Shortest-Paths algorithm

(有向非巡回グラフ 最短路アルゴリズム)。

有向非巡回グラフ(DAG: Directed Acyclic Graph)の最短路を求めるアルゴリズム


DAG G =(V,E)のEdgeに対し次の操作を行う:

1. DAG G に対し、Topological sortを行い、

  線形順序を与える。

 (⇒ vertex u から vertex v への経路があれば u が v に先行する。)

2. 与えられた線形順序の順に、各 veretex vに対し一度、

  Relaxation(緩和操作) を実行する。


負の重みのEdgeがあっても、DAGには 負の重みに閉路は存在しないので、

最短路はDAG上では、常に明確に定義されている。

DAG-Shortest-Paths(G,w,s)
 Topological-Sort(G)
 Initialize-Single-Source(G,s)
 for each vertex u (Topological sortの順に)
  do for each vertex v ∈ Adj[u]
   do Relax(u,v,w)

ここで、

Adj[u] : vertex uの隣接 vertexリスト

また、次の各関数の内容は次を参照:

・Topological-Sort(G)

 ⇒ Topological Sort

・Initialize-Single-Source(G,s),

 Relax(u,v,w)

 ⇒Relaxation


[計算量]

DAG-Shortest-Paths algorithm の計算時間は、Θ(V+E)。

次であるため:

(1) Topological-Sort(G)の計算時間は、Θ(V+E)。

(2) Initialize-Single-Source(G,s)の計算時間は、Θ(V)。

(3) for LoopはVertexごとに1回の操作を行い、E回繰り返される、

  また、内部 for Loopは Θ(1)時間で実行されるので、このLoopの計算時間は、Θ(E)。

※この実行時間は、グラフの隣接リストのサイズに対して線形。


[関連]

PERT chart の Critical-Path算出:

Critical-Pathとは、有向非巡回グラフの最長路。

順序列を実行するのに要する最長時間に対応する。

Critical Pathの経路重みは、全てのJobを実行するのに要する時間の下界になる。


次のどちらかの変換、算出方法で算出できる。

・Edge の重みを負にし、DAG-Shortest-Path(G,w,s)を実行

・Initialize-Single-Sourceの第2行で、"∞"を"−∞"に置き換え、

 Relax(u,v,w)で、">"を"<"で置き換えて、

 DAG-Shortest-Paths(G,w,s)、を実行。


[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

[][] Bellman-Ford algorithm 23:05  Bellman-Ford algorithm - hamadakoichi blog を含むブックマーク  Bellman-Ford algorithm - hamadakoichi blog のブックマークコメント

Bellman-Ford Algorithm (ベルマン・フォード アルゴリズム)。

"負の重みの辺を許す"一般的な、

Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。

"始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行う。

(存在する場合、Falseを返す。)


Bellman-Ford algorithmでも、緩和法を用い、Edgeごとに何度もRelaxation(緩和操作)を行う。

(一方、Dijkstra algorithm, DAG-shortest path algorithm、では Edgeごとに1回の緩和操作のみ。)

始点s から各頂点 v∈V への最短路の重みに関する推定値 d[v]を、

実際の最低路重み δ(s,v)になるまで順次、減らしていく。

Bellman-Ford(G,w,s)
 Initialize-Single-Source(G,s)
 for i ←1 to |V[G]|-1
  do for each Edge (u,v) ∈ E[G]
   do Relax(u,v,w)
 for each Edge (u,v) ∈ E[G]
  do if d[v] > d[u] + w(u,v)
   then return False
 return True

ここで、

・始点 Vertex s

・重み関数 w: E→R

・重みつき有向グラフ G=(V,E)

また、

・Initialize-Single-Source(G,s)

・Relax(u,v,w)

Relaxation(緩和操作)を参照。


[計算量]

Bellman-Ford Algorithmの計算量は、O(VE)

次であるため:

(1) Initialize-Single-Source(G,s)は O(V),

(2) Edge に関する |V|-1回の走査はそれぞれ O(E)時間で実行される →合計 O(VE),

(3) 最後の閉路確認は、O(E),

※"始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行うため、(2)で、Edgeごとに数回の操作を行う。


[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

2008-06-22

[][] Relaxation 22:30  Relaxation - hamadakoichi blog を含むブックマーク  Relaxation - hamadakoichi blog のブックマークコメント

Relaxation (緩和法)。

各Vertexの最短路重みの上界: d[v]

各vertex v∈V に関し、始点 sから、vへの最短路の重みに関する

上界 d[v]を、vertexの属性として管理する。


 d[v] :最短路の推定値(shortest-path estimate)


初期化:Initialize-Single-Source(G,s)

Single-source shortest-path Problem (単一始点最短路問題)での、

最短路の推定値 d[v], 先行点 π(v)の初期化。

 s:始点vertex。

Initialize-Single-Source(G,s)
 for each vertex v ∈ V[G]
  do d[v] ← ∞
   π[v] ← NIL
d[s] ←0    

緩和操作:Relax(u,v,w)

Edge (u,v)に関する緩和操作 Relax(u,v,w)。

これまで発見されている最短路を「vertex u を通ることにより改善できるか」を判定。

改善できるなら、vertex vの 最短路推定値 d[v], 先行点 π[v]を更新する。


緩和操作により、d[v]が減少し、π[v]が更新されていく。

 w:"Edge weight(辺重み)"。Edge(辺)を、実数値の重みに変換する関数(w: E →R)

Relax(u,v,w)
 if d[v] > d[u] + w(u,v)
  then  d[v] ← d[u] + w(u,v)
     π[v] ← u

[操作]

初期化 "Initialize-Single-Source(G,s)"を呼び出し、

Edge (u,v)に対しする、緩和操作 "Relax(u,v,w)"を行っていく。

結果、各vertexに対し、最短路推定値 d[v], 先行vertex π[v]を、更新していくことができる。


各Single-Source Shortest-Path Algorithmでの、緩和操作:

Single-Source Shortest-path Problemの、解法の各Algorithmにごとに違うのは、

各Edgeに対し、

・緩和操作を実行する回数

・Edgeに対する緩和操作の順序。


[負の辺を許す 一般的な単一始点最短路問題]

 ・Bellman-Ford algorithm (ベルマン・フォード アルゴリズム)

 ⇒Edgeごとに何度も緩和操作を行う。


[閉路を含まない有向グラフの最短路問題]:

 ・Dijkstra algorithm (ダイクストラ アルゴリズム)

 ・DAG-shortest path algorithm (有向非巡回グラフ 最短路アルゴリズム)

 ⇒Edgeごとに1回の緩和操作


[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

[][] Shortest-Path Problem 20:21  Shortest-Path Problem - hamadakoichi blog を含むブックマーク  Shortest-Path Problem - hamadakoichi blog のブックマークコメント

"Shortest-Path Problem (最短路問題)"とは、

"最短路(shortest path)"を求める問題。


『vertex(頂点) u からvertex vへの最短路』とは

『経路重みが、最短路重みに等しい経路』。

 w(p) = ¥delta (u,v)


※ここで、"辺重み","経路重み", "最短路重み"の定義は以下:

[辺重み]

 Edge(辺)を、実数値のWeight(重み)に変換する関数 w:w: E →R

[経路重み]

 経路  p = < v_0, v_1, ..., v_k> の 重みは、構成するEdgeの重みの和:

  w(p)= ¥sum_{i=1}^{k} w(v_{i-1}, v_{i})

[最短路重み]

 vertex uからvertex vへの最短路重み  ¥delta (u,v)は、次のように定義される

 ¥delta (u,v)

  = min ¥{w(p): u -> v ¥} (uからvへの経路が存在するとき)

  = ¥infty        (uからvへの経路が存在しないとき)


[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

2008-06-15

[][] Topological Sort 22:01  Topological Sort - hamadakoichi blog を含むブックマーク  Topological Sort - hamadakoichi blog のブックマークコメント

Topological Sort (トポロジカル ソート):

Directed Acyclic Graph(DAG:非循環有向グラフ) G=(V,E)に対し、

全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。

Topological-Sort(G)
1. 各vertexの終了時刻 f[v]を計算するために、DFS(G)を呼び出す。
2. 終了vertexを連結リストの先頭に挿入する
3. retun vertexの連結リスト

[Reference]:

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

[][] Depth-First Search 20:12  Depth-First Search - hamadakoichi blog を含むブックマーク  Depth-First Search - hamadakoichi blog のブックマークコメント

Depth-First Search (深さ優先検索).

(Reference:"Introduction to Algorithms, Second Edition")


可能ならば常に"より深く"、グラフを探索する。

未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全てを探索し終えると、vを発見したときに通ったedgeを "Back track(後戻り)"し、直前のvertexから出る edgeを再探索する。

DFS(G)
 for each vertex u ∈ V[G]
  do color[u] ← WHITE
   π[u] ← NIL
 time ← 0

 for each vertex u ∈ V[G]
  do if color[u]= WHITE
   then DFS-Visit(u)

DFS-Visit(u)
 color[u] ← GRAY
 time ← time +1
 d[u] ← time
 for each vetex v ∈ Adj[u]
  do if color[v] = WHITE
   THEN π[v] ← u
    DFS-Visit(v)
 color[u] ← BLACK
 f[u] ← time ← time+1  

表記:

Adj[u]:vertex uの隣接 vertexリスト

π[u] :predecessor vertex (uの先行vertex)

d[u]: vertex uを発見した時刻

f[u]: vertex uの隣接リストAdj[u]を調べ終えた時刻

time: 1 から 2|Vertex数|の、整数

[color]

WHITE:発見前のvertex

GRAY :発見後の全処理終了前の

BLACK:隣接リスト Adj[u]を調べ終えた時刻


Depth-First Search DFS の計算量は、Θ(|V| + |E|)


[Reference]:

Introduction to Algorithms, Second Edition

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

アルゴリズムイントロダクション 第3巻 精選トピックス


Depth-first search - Wikipedia

2008-06-08

[][] Moore, Breadth First Seach 23:45  Moore, Breadth First Seach - hamadakoichi blog を含むブックマーク  Moore, Breadth First Seach - hamadakoichi blog のブックマークコメント

Edward F. Moore の Breadth First Seach Algorithm。

[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.

Algorithm MOORE [G=(V, E), s, e]
開始Vertex sから終了Vertex eへの、
接続グラフ G =(V,E)の最短路を決定するAlgorithm。

入力:
・開始Vetexを s、終了Vertexを e
 全てのEdge (i,j)で長さl(i,j)=1の接続グラフを、G=(V,E)とする。
・最初は全てのVertexにラベルがない。

出力:
・G=(V,E)の中の最短路 s → e

手続き:

1.sにラベル0をつける

2.i=0 とする。

3.ラベル iが付いているVertexに隣接する、
 全てのラベル付けされていないVertexを検索する

4.見つかったVertexにラベル i+1 をつける

5.if(終了端 eにラベルがつけられた)
  ラベルの逆探索により、最短路を導出:
  k(eのラベル)、k-1, ..., 0とラベルを探索していき、
  各該当Vertexを出力する。

 else
  i=i+1 と増やし、Step 3へ戻る
 

計算量、メモリ使用量のOrderはそれぞれ次。

・計算量Order    ...O(Edge数)

(sから順にVertexを移動し、隣接Vertexを検索していく手続きが、"2×Vetex回"行われる。)

・メモリ使用量Order...O(Vertex数)

(Vertexにつけるラベルの成分数)


巡回セースルマン問題(Traveling Salesman Problem)で、全てのEdge(辺)の長さが 1 の場合の解法。(※巡回セールスマン問題:与えられたグラフの最短Hamilton経路(グラフの全てのVertex(頂点)を通る経路)を決定する問題)


[Reference]:

最適化とグラフ理論 (技術者のための高等数学)

Introduction to Algorithms, Second Edition

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)


[][][] 新しいクラス、グラフ理論 21:17  新しいクラス、グラフ理論 - hamadakoichi blog を含むブックマーク  新しいクラス、グラフ理論 - hamadakoichi blog のブックマークコメント

最近、"新しいクラス"のグラフ理論(Graph Theory)の構築/取扱いを進行。


それに関連し、共有のため、

離散数学/グラフ理論/組合せ最適化、等、の基礎や関連Topicsも紹介していこうと思います。