地図情報処理特論 第9回、第10回 多様なルート生成.

Presentation on theme: "地図情報処理特論 第9回、第10回 多様なルート生成."— Presentation transcript:

1 地図情報処理特論 第9回、第10回 多様なルート生成

2 授業計画 6/12->19 6/12->19 6/19->26 6/19->26 6/26->7/3
7/3->7/10 7/3->7/10 7/10->7/24 7/10->7/24 7/24-7/31 7/24->7/31 7/31->8/7 7/31->8/7 8/7->8/8

3 多様なルートの生成 例題 ダイクストラ法やＡ＊法は 最小コストのルートを求める方法 現実問題では 多様なルートを列挙したい場合が 多い

4 Yen’s Algorithm JOURNAL ARTICLE
AN ALGORITHM FOR FINDING SHORTEST ROUTES FROM ALL SOURCE NODES TO A GIVEN DESTINATION IN GENERAL NETWORKS JIN Y. YEN Quarterly of Applied Mathematics Vol. 27, No. 4 (JANUARY 1970), pp Published by: Brown University 1970年に発表 ダイクストラ法は1959年

5 K shortest path アルゴリズム ノードCからノードHまでの経路 𝐴 1 : 1st shortest path
最短ルート(Dijkstra法） ルートパス ルートパス C D E F G H 3 4 2 1 𝐴 1 = 𝐶,𝐸,𝐹,𝐻:5 𝐴 1 = 𝐶,𝐸,𝐹,𝐻:5 𝐴 1 = 𝐶,𝐸,𝐹,𝐻:5 Spur（尾根） node Spur（尾根） node Spur（尾根） node 𝑅 2 1 ={𝐶} 𝑅 2 2 ={𝐶,𝐸} 𝑅 2 3 ={𝐶,𝐸,𝐹} 𝐴 1 : 1st shortest path 𝐶−𝐸がroot path に 含まれるため除外 𝐸−𝐹がroot path に 含まれるため除外 𝐹−𝐻がroot path に 含まれるため除外 最短ルート(Dijkstra法） 最短ルート(Dijkstra法） 最短ルート(Dijkstra法） 𝑆 2 1 ={𝐶,𝐷,𝐹,𝐻} 𝑆 2 2 ={𝐸,𝐺,𝐻} 𝑆 2 3 ={𝐹,𝐺,𝐻} 𝐴 2 1 = 𝑅 𝑆 2 1 ={𝐶,𝐷,𝐹,𝐻:8} 𝐴 2 2 = 𝑅 𝑆 2 2 ={𝐶,𝐸,𝐺,𝐻:𝟕} 𝐴 2 3 = 𝑅 𝑆 2 3 ={𝐶,𝐸,𝐹,𝐺,𝐻:8} C D E F G H ∞ 1 2 3 4 C D E F G H 2 1 ∞ 3 4 C D E F G H 2 1 3 ∞ 4 ルートパス spur node 3ルートの中で最小コストの𝐴 2 を採用 5

6 K shortest path アルゴリズム 𝐴 2 ={𝐶,𝐸,𝐺,𝐻:7} 2ルートの中で最小コストの𝐴 3 を採用
𝐴 2 = 𝐶,𝐸,𝐺,𝐻:7 𝐴 2 = 𝐶,𝐸,𝐺,𝐻:7 𝐴 2 = 𝐶,𝐸,𝐺,𝐻:7 Spur node Spur node Spur node C D E F G 2 1 3 4 H 𝑅 3 1 ={𝐶} 𝑅 3 2 ={𝐶,𝐸} 𝑅 3 3 ={𝐶,𝐸,𝐺} 𝐶−𝐸がroot path に 含まれるため除外 𝐸−𝐺がroot path に 含まれるため除外 𝐺−𝐻がroot path に 含まれるため除外 最短ルート(Dijkstra法） 最短ルート(Dijkstra法） 最短ルート(Dijkstra法） 3 4 3 4 C D E F G H ∞ 1 2 3 4 C D E F G H 2 1 ∞ C D F 2 1 1 2 2 3 ∞ E G H 𝑆 3 1 ={𝐶,𝐷,𝐹,𝐻} 𝑆 3 2 ={𝐸,𝐷,𝐹,𝐻} 𝑆 3 3 ={ ルート無し} 𝐴 3 1 = 𝑅 𝑆 3 1 ={𝐶,𝐷,𝐹,𝐻:8} 𝐴 3 2 = 𝑅 𝑆 3 2 ={𝐶,𝐸,𝐷,𝐹,𝐻:8} 𝐴 3 3 ：存在せず 2ルートの中で最小コストの𝐴 3 を採用

7 K shortest path アルゴリズム 𝐴 1 = 𝐶,𝐸,𝐹,𝐻:5 𝐴 3 ={𝐶,𝐷,𝐹,𝐻:8}
𝐴 2 ={𝐶,𝐸,𝐺,𝐻:7} 3 4 𝐴 3 ={𝐶,𝐷,𝐹,𝐻:8} C C D F Spur node 2 1 1 2 2 3 2 ∞ 4 E G H C D F 𝐶−𝐷が それまでの root path に含まれるため除外 ∞ 1 1 2 2 3 2 E G H 𝑅 4 1 ={𝐶} 𝑆 4 1 ={−} 𝐴 4 は存在しない。

8 K shortest path アルゴリズム 𝐴 1 ={𝐶,𝐸,𝐹,𝐻:5} 𝐴 2 ={𝐶,𝐸,𝐺,𝐻:7}
C D E F G H 3 4 2 1 𝐴 1 ={𝐶,𝐸,𝐹,𝐻:5} C D E F G 2 1 3 4 H C D E F G H ∞ 1 2 3 4 𝐴 2 ={𝐶,𝐸,𝐺,𝐻:7} 𝐴 2 ={𝐶,𝐸,𝐹,𝐻:8} C D E F G H 2 1 3 ∞ 4 𝐴 2 ={𝐶,𝐸,𝐹,𝐺,𝐻:8} C D E F G H 2 1 3 4 𝐴 3 ={𝐶,𝐷,𝐹,𝐻:8} C D E F G H 2 1 ∞ 𝐴 3 ={𝐶,𝐸,𝐷,𝐹,𝐻:8}

9 K shortest path アルゴリズム (1)−−−− 𝑖 −−−− 𝑗 , 𝑖≠𝑗≠1
(1)−−−− 𝑖 −−−− 𝑗 , 𝑖≠𝑗≠1 始点 1 N-2 ノード 𝑖 を経由する（１）から(𝑗)までの経路 3 2 N-3 N 終点 𝑑 𝑖,𝑗 ≤ 0, 𝑖≠𝑗 ノード𝑖,𝑗間のコスト > N-1 𝐴 𝑘 = 1 − 2 𝑘 − 3 𝑘 − …. − 𝑄 𝑘 𝑘 − 𝑁 , 𝑘=1,2,…,𝐾 ノード(1)から(N)までのk番目の最短経路　kth shortest path 𝐴 𝑖 𝑘 , 𝑖=1,2,…, 𝑄 𝑘 𝐴 𝑘−1 からのノード(𝑖)からの偏移(𝑑𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛)

10 K shortest path　アルゴリズム 𝐴 𝑘 = 1 − 2 𝑘 − 3 𝑘 − …. − 𝑄 𝑘 𝑘 − 𝑁 , 𝑘=1,2,…,𝐾 𝐴 𝑖 𝑘 , 𝑖=1,2,…, 𝑄 𝑘 𝐴 𝑘−1 からのノード(𝑖)からの偏移(𝑑𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛) 𝐴 𝑘−1 = 1 − 2 𝑘−1 − 3 𝑘−1 − …. − 𝑄 𝑘−1 𝑘−1 − 𝑁 , 𝑘=1,2,…,𝐾−1

11 K shortest path アルゴリズム Iteration 1 𝐴 1 の決定 Iteration k (k=2,3,…,K)
𝐴 𝑘 の決定 𝐴 1 , 𝐴 2 , 𝐴 3 ,,.., 𝐴 𝑘−1 は求まっているとする。 𝑖=1,2,.., 𝑄 𝑘−1 に対して以下を実行 step(a) 𝐴 𝑘−1 　の最初の𝑖個のノードからなる部分経路が 𝐴 𝑗 ,𝑗=1,2,..,𝑘−1の 最初の𝑖個のノードからなる部分経路と一致しているかを調べる。 もしそうであれば、 𝑑 𝑖𝑞 =∞ とする。　ここで 𝑞 は 𝐴 𝑖 の 𝑖+1 番目の ノードである。 そうでなければstep(b)に進む。 step(b) ノード 𝑖 からノード 𝑁 までの最短経路を求める。 ノード(1)からノード(𝑖)までの部分経路を 𝑅 𝑖 𝑘 として、 𝐴 𝑖 𝑘 の𝑟𝑜𝑜𝑡 𝑝𝑎𝑡ℎ と呼ぶ。 ノード(𝑖)からノード(𝑁)までの部分経路を 𝑆 𝑖 𝑘 として、 𝐴 𝑖 𝑘 の𝑠𝑝𝑢𝑟 尾根 と呼ぶ。 もし、ノード(𝑖)からノード(𝑁)までの最小コストの部分経路が複数あるなら 任意に一つを選んで 𝑆 𝑖 𝑘 とする。 step(c) 𝑅 𝑖 𝑘 と 𝑆 𝑖 𝑘 をつなげて 𝐴 𝑖 𝑘 を求める。

12 K shortest path アルゴリズム node1 -> node 31
link,1,node1,1,node2,2,x,0,y,0,type,4,link_type,2,link_length,67 link,2,node1,1,node2,3,x,0,y,0,type,4,link_type,2,link_length,24 link,3,node1,1,node2,4,x,0,y,0,type,4,link_type,2,link_length,78 link,4,node1,2,node2,1,x,0,y,0,type,4,link_type,2,link_length,17 link,5,node1,2,node2,7,x,0,y,0,type,4,link_type,2,link_length,25 link,6,node1,2,node2,5,x,0,y,0,type,4,link_type,2,link_length,94 link,7,node1,2,node2,7,x,0,y,0,type,4,link_type,2,link_length,64 link,8,node1,3,node2,1,x,0,y,0,type,4,link_type,2,link_length,83 link,9,node1,3,node2,39,x,0,y,0,type,4,link_type,2,link_length,32 link,10,node1,4,node2,1,x,0,y,0,type,4,link_type,2,link_length,95 link,11,node1,4,node2,5,x,0,y,0,type,4,link_type,2,link_length,10 link,12,node1,4,node2,17,x,0,y,0,type,4,link_type,2,link_length,90 link,13,node1,5,node2,2,x,0,y,0,type,4,link_type,2,link_length,49 link,14,node1,5,node2,8,x,0,y,0,type,4,link_type,2,link_length,59 link,15,node1,5,node2,4,x,0,y,0,type,4,link_type,2,link_length,86 link,16,node1,5,node2,9,x,0,y,0,type,4,link_type,2,link_length,81 link,17,node1,5,node2,8,x,0,y,0,type,4,link_type,2,link_length,32 link,18,node1,6,node2,9,x,0,y,0,type,4,link_type,2,link_length,14 link,19,node1,7,node2,2,x,0,y,0,type,4,link_type,2,link_length,88 link,20,node1,7,node2,2,x,0,y,0,type,4,link_type,2,link_length,1 link,21,node1,7,node2,11,x,0,y,0,type,4,link_type,2,link_length,54 link,22,node1,7,node2,12,x,0,y,0,type,4,link_type,2,link_length,76 link,23,node1,8,node2,5,x,0,y,0,type,4,link_type,2,link_length,13 link,24,node1,8,node2,5,x,0,y,0,type,4,link_type,2,link_length,80 link,25,node1,8,node2,17,x,0,y,0,type,4,link_type,2,link_length,12 link,26,node1,9,node2,5,x,0,y,0,type,4,link_type,2,link_length,39 link,27,node1,9,node2,6,x,0,y,0,type,4,link_type,2,link_length,46 link,28,node1,9,node2,10,x,0,y,0,type,4,link_type,2,link_length,5 link,29,node1,9,node2,11,x,0,y,0,type,4,link_type,2,link_length,28 link,30,node1,10,node2,9,x,0,y,0,type,4,link_type,2,link_length,40 link,31,node1,10,node2,23,x,0,y,0,type,4,link_type,2,link_length,0 link,32,node1,10,node2,15,x,0,y,0,type,4,link_type,2,link_length,70 link,33,node1,11,node2,7,x,0,y,0,type,4,link_type,2,link_length,49 link,34,node1,11,node2,9,x,0,y,0,type,4,link_type,2,link_length,98 link,35,node1,12,node2,7,x,0,y,0,type,4,link_type,2,link_length,26 link,36,node1,12,node2,34,x,0,y,0,type,4,link_type,2,link_length,47 link,37,node1,12,node2,13,x,0,y,0,type,4,link_type,2,link_length,44 link,38,node1,12,node2,40,x,0,y,0,type,4,link_type,2,link_length,31 link,39,node1,13,node2,12,x,0,y,0,type,4,link_type,2,link_length,10 link,40,node1,13,node2,14,x,0,y,0,type,4,link_type,2,link_length,87 link,41,node1,13,node2,33,x,0,y,0,type,4,link_type,2,link_length,55 link,42,node1,13,node2,31,x,0,y,0,type,4,link_type,2,link_length,76 link,43,node1,14,node2,13,x,0,y,0,type,4,link_type,2,link_length,58 link,44,node1,14,node2,32,x,0,y,0,type,4,link_type,2,link_length,26 link,45,node1,14,node2,29,x,0,y,0,type,4,link_type,2,link_length,97 link,46,node1,14,node2,40,x,0,y,0,type,4,link_type,2,link_length,67 link,47,node1,15,node2,10,x,0,y,0,type,4,link_type,2,link_length,88 link,48,node1,15,node2,20,x,0,y,0,type,4,link_type,2,link_length,87 link,49,node1,16,node2,17,x,0,y,0,type,4,link_type,2,link_length,75 link,50,node1,16,node2,18,x,0,y,0,type,4,link_type,2,link_length,10 link,51,node1,16,node2,19,x,0,y,0,type,4,link_type,2,link_length,15 link,52,node1,17,node2,4,x,0,y,0,type,4,link_type,2,link_length,32 link,53,node1,17,node2,8,x,0,y,0,type,4,link_type,2,link_length,41 link,54,node1,17,node2,16,x,0,y,0,type,4,link_type,2,link_length,88 link,55,node1,18,node2,16,x,0,y,0,type,4,link_type,2,link_length,77 link,56,node1,18,node2,39,x,0,y,0,type,4,link_type,2,link_length,85 link,57,node1,18,node2,19,x,0,y,0,type,4,link_type,2,link_length,80 link,58,node1,18,node2,21,x,0,y,0,type,4,link_type,2,link_length,2 link,59,node1,19,node2,16,x,0,y,0,type,4,link_type,2,link_length,52 link,60,node1,19,node2,18,x,0,y,0,type,4,link_type,2,link_length,67 link,61,node1,19,node2,20,x,0,y,0,type,4,link_type,2,link_length,32 link,62,node1,20,node2,15,x,0,y,0,type,4,link_type,2,link_length,58 link,63,node1,20,node2,19,x,0,y,0,type,4,link_type,2,link_length,44 link,64,node1,20,node2,22,x,0,y,0,type,4,link_type,2,link_length,68 link,65,node1,20,node2,24,x,0,y,0,type,4,link_type,2,link_length,67 link,66,node1,21,node2,18,x,0,y,0,type,4,link_type,2,link_length,1 link,67,node1,21,node2,22,x,0,y,0,type,4,link_type,2,link_length,47 link,68,node1,21,node2,39,x,0,y,0,type,4,link_type,2,link_length,35 link,69,node1,22,node2,20,x,0,y,0,type,4,link_type,2,link_length,63 link,70,node1,22,node2,21,x,0,y,0,type,4,link_type,2,link_length,3 link,71,node1,22,node2,25,x,0,y,0,type,4,link_type,2,link_length,76 link,72,node1,23,node2,24,x,0,y,0,type,4,link_type,2,link_length,18 link,73,node1,23,node2,26,x,0,y,0,type,4,link_type,2,link_length,86 link,74,node1,24,node2,20,x,0,y,0,type,4,link_type,2,link_length,30 link,75,node1,24,node2,23,x,0,y,0,type,4,link_type,2,link_length,76 link,76,node1,24,node2,25,x,0,y,0,type,4,link_type,2,link_length,64 link,77,node1,23,node2,10,x,0,y,0,type,4,link_type,2,link_length,19 link,78,node1,25,node2,22,x,0,y,0,type,4,link_type,2,link_length,34 link,79,node1,25,node2,24,x,0,y,0,type,4,link_type,2,link_length,27 link,80,node1,25,node2,26,x,0,y,0,type,4,link_type,2,link_length,91 link,81,node1,26,node2,23,x,0,y,0,type,4,link_type,2,link_length,47 link,82,node1,26,node2,25,x,0,y,0,type,4,link_type,2,link_length,54 link,83,node1,26,node2,35,x,0,y,0,type,4,link_type,2,link_length,37 link,84,node1,26,node2,27,x,0,y,0,type,4,link_type,2,link_length,65 link,85,node1,27,node2,26,x,0,y,0,type,4,link_type,2,link_length,41 link,86,node1,27,node2,28,x,0,y,0,type,4,link_type,2,link_length,8 link,87,node1,27,node2,29,x,0,y,0,type,4,link_type,2,link_length,90 link,88,node1,27,node2,30,x,0,y,0,type,4,link_type,2,link_length,37 link,89,node1,28,node2,27,x,0,y,0,type,4,link_type,2,link_length,39 link,90,node1,28,node2,31,x,0,y,0,type,4,link_type,2,link_length,16 link,91,node1,29,node2,14,x,0,y,0,type,4,link_type,2,link_length,79 link,92,node1,29,node2,27,x,0,y,0,type,4,link_type,2,link_length,30 link,93,node1,29,node2,31,x,0,y,0,type,4,link_type,2,link_length,47 link,94,node1,30,node2,27,x,0,y,0,type,4,link_type,2,link_length,14 link,95,node1,31,node2,13,x,0,y,0,type,4,link_type,2,link_length,96 link,96,node1,31,node2,28,x,0,y,0,type,4,link_type,2,link_length,96 link,97,node1,31,node2,29,x,0,y,0,type,4,link_type,2,link_length,85 link,98,node1,31,node2,32,x,0,y,0,type,4,link_type,2,link_length,77 link,99,node1,32,node2,14,x,0,y,0,type,4,link_type,2,link_length,22 link,100,node1,32,node2,31,x,0,y,0,type,4,link_type,2,link_length,87 link,101,node1,32,node2,33,x,0,y,0,type,4,link_type,2,link_length,69 link,102,node1,33,node2,13,x,0,y,0,type,4,link_type,2,link_length,43 link,103,node1,33,node2,31,x,0,y,0,type,4,link_type,2,link_length,73 link,104,node1,34,node2,12,x,0,y,0,type,4,link_type,2,link_length,48 link,105,node1,35,node2,26,x,0,y,0,type,4,link_type,2,link_length,62 link,106,node1,35,node2,37,x,0,y,0,type,4,link_type,2,link_length,12 link,107,node1,36,node2,37,x,0,y,0,type,4,link_type,2,link_length,2 link,108,node1,37,node2,35,x,0,y,0,type,4,link_type,2,link_length,54 link,109,node1,37,node2,36,x,0,y,0,type,4,link_type,2,link_length,57 link,110,node1,37,node2,38,x,0,y,0,type,4,link_type,2,link_length,53 link,111,node1,38,node2,37,x,0,y,0,type,4,link_type,2,link_length,45 link,112,node1,39,node2,3,x,0,y,0,type,4,link_type,2,link_length,61 link,113,node1,39,node2,18,x,0,y,0,type,4,link_type,2,link_length,98 link,114,node1,39,node2,21,x,0,y,0,type,4,link_type,2,link_length,37 link,115,node1,40,node2,12,x,0,y,0,type,4,link_type,2,link_length,32 link,116,node1,40,node2,14,x,0,y,0,type,4,link_type,2,link_length,45 node1 -> node 31

13 K shortest path　アルゴリズム 50 shortest path

14 K shortest path アルゴリズム 課題：k個の経路を列挙しただけで良いか？ マクロな視点で典型的なルートを抽出できないか？
何らかのクラスタリングが必要

15 K shortest path アルゴリズム レポート： K shortest path の論文を読んで要約しなさい。
提出期限　　8月7日（金）