第4章 空間解析 2.ネットワーク分析 (1) 最短経路検索 久保田光一 [email protected] 地理情報科学教育用スライド ©久保田李光一 最短経路探索 池袋 御茶ノ水 秋葉原 新宿 東京 地理情報科学教育用スライド ©久保田李光一 最短経路探索 • 出発地の駅から，目的地の駅まで移動する． – 所要時間が一番短い経路 – 料金が一番安い経路 • 自動車で目的地まで移動する． – 距離が一番短い経路 – 所要時間が一番短い経路 – 高速料金などの料金が一番安い経路 地理情報科学教育用スライド ©久保田李光一 最短経路探索 19分 出発地：池袋 11分 6分 御茶ノ水 2分 15分 秋葉原 新宿 5分 2分 目的地：東京 29分 地理情報科学教育用スライド ©久保田李光一 グラフ • グラフは道路網や鉄道網などのネットワーク を表すための基本的な構造． • 頂点： 駅，地点，建物などを表す. • 枝（辺ともいう）： 鉄道，道路などを表す. – 有向枝 (u,v) : 始点u, 終点v – 無向枝 {u,v} : 端点u, 端点v – 枝の長さ L(u,v), L{u,v} – 枝の重み w(u,v), w{u,v} 地理情報科学教育用スライド ©久保田李光一 グラフ 池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ５ 新宿 ２９ 東京 地理情報科学教育用スライド ©久保田李光一 単純グラフ • セルフループ loop, self loop • 頂点から出て同じ頂点に戻る枝 • 平行枝 parallel edge • 同じ頂点を結ぶ枝 • 有向なら向きも同じ • グラフが単純 – セルフループも平行枝も無いグラフのこと 地理情報科学教育用スライド ©久保田李光一 ダイクストラ法 • 枝の重みが0以上（非負）であることが大事！ – 実際の多くのネットワークは非負の重み． • 考え方 – 出発地からの経路が短い順に，各頂点までの最 短経路を定める．目的地までの最短経路が見つ かれば終了．あるいは，すべての点までの最短 経路を計算して終了． 地理情報科学教育用スライド ©久保田李光一 グラフ 出発地：池袋 秋葉原 １９ １１ 御茶ノ水 ６ ２ １５ ２ ５ 新宿 ２９ 目的地：東京 地理情報科学教育用スライド ©久保田李光一 グラフ 出発地：池袋 0 秋葉原 １９ １１ ∞ ６ ∞ ∞ 御茶ノ水 ２ １５ ２ ５ 新宿 ２９ ∞ 地理情報科学教育用スライド ©久保田李光一 目的地：東京 グラフ 池袋 0 19 御茶ノ水 １１ 11 ６ 6 秋葉原 １９ ２ １５ ２ ５ 新宿 ２９ ∞ 地理情報科学教育用スライド ©久保田李光一 東京 グラフ 池袋 0 19 御茶ノ水 １１ 11 ６ 6 秋葉原 １９ ２ １５ ２ ５ 新宿 ２９ 35 地理情報科学教育用スライド ©久保田李光一 東京 グラフ 池袋 0 19 →13 御茶ノ水 １１ 11 ６ 6 秋葉原 １９ ２ １５ ２ ５ 新宿 ２９ 35→16 地理情報科学教育用スライド ©久保田李光一 東京 グラフ 池袋 0 19 →13 御茶ノ水 １１ 11 ６ 6 秋葉原 １９ ２ １５ ２ ５ 新宿 ２９ 35→16→15 地理情報科学教育用スライド ©久保田李光一 東京 グラフ 池袋 0 19 →13 御茶ノ水 １１ 11 ６ 6 秋葉原 １９ ２ １５ ２ ５ 新宿 ２９ 35→16→15 地理情報科学教育用スライド ©久保田李光一 東京 ダイクストラ(Dijkstra)法 • 記号： – – – – – – s: 出発頂点（始点） u, v:頂点 (u,v):頂点uから頂点v への有向枝 w(u,v): 枝(u,v)の重み d(v): 頂点vにおける作業場所（仮の距離distanceを格納） p(v): 頂点v における最短経路上でuの直前（親 parent） の頂点（太い枝を表現） 地理情報科学教育用スライド ©久保田李光一 ダイクストラ法(アルゴリズム） • • • • • 出発点を s と記す． s から各頂点 v までの距離を d(v) に計算する. d(s)=0, s 以外のすべての頂点 v について d(v)=∞． Q をすべての頂点からなる集合とする． Qが空集合になるまで以下を繰り返す. – 集合 Q に含まれる頂点vの中で d(v) が最小となるvを u と記す． – ここで d(u) に計算された値が sからu に至る最短経路長として確定. – u を Q から取り除く. – uを端点に持つ全ての枝 (u,v) を考える. – その枝のu以外のもう一方の端点をv とする. – もし d(v)>d(u)+w(u,v)なら d(v)=d(u)+w(u,v) とする． – そうでないなら何もしない． 地理情報科学教育用スライド ©久保田李光一 ダイクストラ法に関する性質 • 計算量: 頂点の数をn, 枝の数をmとする. – 単純な実装では O(n^2) ． – 集合Qを効率よく扱うと，O(n log n + m) ． – グラフが大規模で，出発地から目的地までの最短経路に限る場合，A*アル ゴリズムと組み合わせてもっと効率よく計算する方法がある. • 出発地 s からの最短経路は木構造となる． – 単一頂点sから他のすべての頂点への最短経路を計算する． • 木構造の計算 – 出発点 s から v に至る経路上で，v の直前の頂点を p(v) として示すように， p(v) の値を更新していけばよい． – そのためにはd(v)の値を更新するときに，頂点vの親頂点を表すp(v)という作 業場所を用意し，その値をuに更新すればよい． – 目的地vからp(v)を辿って，出発地に戻る経路が最短経路を与える． 地理情報科学教育用スライド ©久保田李光一 ワーシャル・フロイド法 • Warshall-Floyd 法，ウォーシャル・フロイド法，フロイド・ウォー シャル法ともいう • 全ての2頂点間の最短経路を同時に計算． – n + 1 個の 2次元配列 c0, c1, c2, … , cn を用意する． – 頂点 v_i から頂点 v_j に至る経路のうち，最短のものの経路長を cn[i][j] という配列要素に最終的に計算する． • 考え方：頂点v_i と頂点 v_j を結ぶ経路について，経由しても よい頂点（経由可能頂点）を指定する． – c1[i][j] : 経由可能頂点の集合が {v_1} の経路の最短経路長 – c2[i][j] : 経由可能頂点の集合が {v_1,v_2} である経路の最短経路長 – （以下経由可能頂点の集合を一つずつ大きくする） – cn[i][j] : 任意の点を経由可能な経路の最短経路長 地理情報科学教育用スライド ©久保田李光一 ワーシャル・フロイド法 • 経由してもよい頂点を直接指定することに注意！ v_2 c1[i][j]=min(c0[i][j], c0[i][1]+c[1][j]) c0[i][j]=w(i,j) v_1 v_i v_j 経由頂点なし v_i v_1 v_j v_1だけを経由可能 v_i v_j v_1 と v_2 を経由可能 c2[i][j]=min(c1[i][j], c1[i][2]+c1[2][j]) 地理情報科学教育用スライド ©久保田李光一 ワーシャル・フロイド法 v_k v_1, v_2, …, v_(k-1) v_j v_i ck[i][j]=min( c(k-1)[i][j], c(k-1)[i][k]+c(k-1)[k][j] ) v_1, v_2, …, v_(k-1), v_k v_j v_i 地理情報科学教育用スライド ©久保田李光一 グラフ 池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ５ 新宿 ２９ 東京 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 枝の重み（距離）を行列（2次元配列）の形にする． – 枝1本で接続する２点間の距離w(I,j) : c0[i][j]=w(i,j) – 枝の無い頂点間の距離は∞（無限大） 池 新 御 秋 東 池袋 0 6 11 19 ∞ 新宿 6 0 15 ∞ 29 御茶ノ水 11 15 0 2 5 秋葉原 19 ∞ 2 0 2 東京 ∞ 29 5 2 0 0 6 11 19 6 0 15 29 C 11 15 0 2 5 19 2 0 2 29 5 2 0 c0[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 池袋駅を経由してもよい 池 新 御 秋 東 池 池袋 0 6 11 19 ∞ 新宿 6 0 15 ∞ 29 御茶ノ水 11 15 0 2 5 秋葉原 19 ∞ 2 0 2 東京 ∞ 29 5 2 0 新 御 秋 東 池袋 0 6 11 19 ∞ 新宿 6 0 15 25 29 御茶ノ水 11 15 0 2 5 秋葉原 19 25 2 0 2 東京 ∞ 29 5 2 0 c0[i][j] c1[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 池袋駅と新宿を経由してもよい 池 新 御 秋 東 池 池袋 0 6 11 19 ∞ 新宿 6 0 15 25 29 新 御 秋 東 池袋 0 6 11 19 35 新宿 6 0 15 25 29 御茶ノ水 11 15 0 2 5 秋葉原 19 25 2 0 2 御茶ノ水 11 15 0 2 5 東京 ∞ 29 5 2 0 秋葉原 19 25 2 0 2 東京 35 29 5 2 0 c1[i][j] c2[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 池袋駅と新宿と御茶ノ水を経由してもよい 池 新 御 秋 東 池 池袋 0 6 11 19 35 新宿 6 0 15 25 29 新 御 秋 東 池袋 0 6 11 13 16 新宿 6 0 15 17 20 御茶ノ水 11 15 0 2 5 秋葉原 19 25 2 0 2 御茶ノ水 11 15 0 2 5 東京 35 29 5 2 0 秋葉原 13 17 2 0 2 東京 16 20 5 2 0 c2[i][j] c3[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 池袋駅と新宿と御茶ノ水と秋葉原を経由して もよい 池袋 新宿 御茶ノ水 秋葉原 東京 池 新 御 秋 東 0 6 11 13 16 6 0 15 17 20 11 15 0 2 5 13 17 2 0 2 16 20 5 2 0 c3[i][j] 池 新 御 秋 東 池袋 0 6 11 13 15 新宿 6 0 15 17 19 御茶ノ水 11 15 0 2 4 秋葉原 13 17 2 0 2 東京 15 19 4 2 0 c4[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • 全駅（池袋駅と新宿と御茶ノ水と秋葉原と東 京）を経由してもよい 池 新 御 秋 東 池 新 御 秋 東 池袋 0 6 11 13 15 池袋 0 6 11 13 15 新宿 6 0 15 17 19 新宿 6 0 15 17 19 御茶ノ水 11 15 0 2 4 秋葉原 13 17 2 0 2 東京 15 19 4 2 0 御茶ノ水 11 15 0 2 4 秋葉原 13 17 2 0 2 東京 15 19 4 2 0 c4[i][j] c5[i][j] 地理情報科学教育用スライド ©久保田李光一 ウォーシャルフロイド法 • ｎ個の頂点をv1,v2,…,vnとする． • 2個の2次元配列 c[i][j] と d[i][j] を用意する． – c[i][j]= 頂点viと頂点vjを結ぶ枝の距離 – 枝が無い場合には, 無限大（∞） – c[i][i]はゼロ • for k=1 to n do begin – for i=1 to n do for j=1 to n do – d[i][j]=min( c[i][j], c[i][k]+c[k][j] ) – for i=1 to n do for j=1 to n do c[i][j]=d[i][j] – End (* c と d は同じ配列を用いて一行上を削除可能 *) 地理情報科学教育用スライド ©久保田李光一 2番目に短い最短経路 • 乗り換え案内など，最短経路だけでなく，2番目， 3番目に短い経路に興味がある場合もある． – 探索経路の条件：simple な経路（パス） • Simpleでない経路の例：同じ頂点を2度通るもの • 考え方：最短経路を構成する枝がp本あるとする． – その p本の枝のそれぞれ1本だけを除いたグラフにお ける最短経路を調べる – その p個の最短経路のうち，経路長が最短のものが 元のグラフでの2番目に短い経路 – これを「頂点数-1」本まで繰り返す． – 実は，元のグラフを二つ用意して適宜それらを接続すると， 1回ダイクストラ法を用いて計算するだけで済む 地理情報科学教育用スライド ©久保田李光一
© Copyright 2024 ExpyDoc
