需要予測

最短経路
出発点から数カ所の中継地を経て到着点に
達するとき、
最短距離、最短時間、最小運賃などを求め
る。
方法
◎ ラベル法
◎ 行列和法
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
ラベル法(最短距離)
手順
０．出発点地にラベル［＊，０］を付ける。
ⅰ．出発地を①とし、①に一番距離が近い中継地に①および
出発地からの距離を示したラベルを付ける。［①，２］
ⅱ．既にラベルの付いた中継地と経路で結ばれている中継地
の中から、ラベルに示された距離と経路の距離の和が最小
となる中継地に、前の中継地とその距離の和を示したラベ
ルを付ける。
ⅲ．残りの中継地に関して、ⅱを繰り返す。
ⅳ．全ての中継地にラベルが付けられたならば、出発地①か
らの最短経路はラベルをさかのぼることにより得られる。
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
ラベル法(例４・１)
６
２
２
４
１
４
２
１
４
５
１
４
７
１
３
２
２
2015/9/30
５
©ＡＴＳＵＴＯＮＩＳＨＩＯ
６
ラベル法(0：出発地のラベル)
６
２
２
４
１
４
２
１
４
［＊，０］
５
１
４
７
１
３
２
２
2015/9/30
５
©ＡＴＳＵＴＯＮＩＳＨＩＯ
６
ラベル法(ⅰ：)
①→②：０＋２＝２
［①，２］
①→③：０＋５＝５
６
２
２
４
１
４
２
１
４
［＊，０］
５
１
４
７
１
３
２
２
2015/9/30
５
©ＡＴＳＵＴＯＮＩＳＨＩＯ
６
ラベル法(ⅱ：)
［①，２］
６
［②，８］
２
２
４
１
５
１
［⑥，８］
４
７
１
３
②→③：２＋２＝４［②，４］
2015/9/30
④→③：５＋１＝６
１
４
［＊，０］
①→③：０＋５＝５
４
［③，５］
２
５
２
２
©ＡＴＳＵＴＯＮＩＳＨＩＯ
６
［③ ④，６］
ラベル法(①から⑦に行くためのは)
⑦から①にさかのぼる
⑦→⑥ → ③→②→①
④
［①，２］
２
６
２
４
１
２
５
４
［③，５］
１
４
［＊，０］
５
１
［②，４］
［⑥，８］
４
７
１
３
2015/9/30
［②，８］
２
２
©ＡＴＳＵＴＯＮＩＳＨＩＯ
注意
６
［③ ④，６］
ラベル法(解答)
①→② ：２
①→②→③ ：４
①→②→③→④ ：５
①→②→⑤ ：８
①→②→③→⑥ ：６
①→②→③→④→⑥ ：６
①→②→③→⑥→⑦ ：８
①→②→③→④→⑥→⑦ ：８
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
行列和法 (最短時間)
ラベル法をコンピュータで解くための手法
手順
ⅰ．都市が５都市で、出発地が①のとき、
Ｖ(0)＝［0，∞，∞，∞，∞］
ⅱ．Ｖ(0)のｉ番目の値と表の１列目のｊ番目の値を
加える
ⅲ．ⅱで求めた値の最小値をＶ(1)の１番目に書く
ⅳ．ⅱ～ⅲの操作を２列目で繰り返す。
ⅴ．ⅱ～ⅳの操作を［］内の値が変化しなくなる
まで繰り返す
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
行列和法 (最短経路)
手順
ⅰ．都市が５都市で、出発地が①のとき、
ｒ(1)＝［＊
］
ⅱ．Ｖ(0)からＶ(1)に移ったときに変化した値
の所は、何番目を持ってきたのか、その番
号を記入する。また、変化しなかった所に
は・印を記入する
ⅲ．ｒ(4)までⅱの操作を繰り返す
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
行列和法 (例４・２)
都市①,②,・・・,⑤とその間を行くのに必要とする時間
２
２
１
４
∞
∞
１
∞
１
３
３
４
∞
１
2015/9/30
©ＡＴＳＵＴＯＮＩＳＨＩＯ
∞
５
２

Download Report