アルゴリズムc 第5回

ダイクストラ法の改善

ダイクストラ法(PFSでも)は、始点の近くから次々に最短距離を 決定していく方法でした。 しかし、たとえば、東京から大阪へ行くのに、名古屋経由と 仙台経由を同列に扱っていいのでしょうか？

経由地から目的地までの距離も考慮に入れようとする考え方が 「A*アルゴリズム」(「エースター」と読みます)です。


A* アルゴリズム

以下では「コスト」というのは「道のり」のことです。

始点からノードnを経由して目的地までたどり着くときの 最短経路を考えます。最短経路のコストをf(n)とおくと、 「始点からノードnまでの最小コスト」g(n)と 「ノードnから目的地までの最小コスト」h(n)を使って 

    f(n) = g(n) + h(n)
と書けます。 もしg(n)の値とh(n)の値が既に知られていれば全体の 最短経路f(n)はすぐに求めることができます。 しかし、一般にはg(n)とh(n)はわかりません。

そこで、「始点からノードnまでの最小コストの推定値」g*(n)と 「ノードnから目的地までの最小コストの推定値」h*(n)を使って 次のような推定値f*(n)を考えることにします。 

    f*(n) = g*(n) + h*(n)
g*(n)は探索の過程で適切な推定値を順次決めていくことができます (ダイクストラ法を思い出して下さい)。 しかしh*(n)を推定することはできません。

そこでh*(n)に適当な推定値を与え、g*(n)は探索の過程で適宜更新 しながら最短経路を求める方法が考えられます。 これを A* アルゴリズムといいます。 全てのノードnについて 0≦h*(n)≦h(n)であれば正しい最短経路が 求まることが保証されています。

ダイクストラ法は、A*アルゴリズムにおいてh*(n)=0とした 場合に相当します。

考え方

以下の最短距離を求める問題において、 h*(n)として「ノードnから目的地までの直線距離」を使ってみましょう。 直線距離ならば実際の道のりよりも小さいことは確実ですので条件を満たしています。


例題: 最短経路を求める

いくつかの都市と、それらの都市をつなぐ道路の距離が与えられている。 出発地点と目的地点が与えられたとき、最短経路を探すプログラムを作りなさい。 ただし、都市の位置も与えられているものとする。

入力形式

N
0     X1 Y1
1     X2 Y2
...
i     Xi Yi
...
(N-1) XN YN
M
T1,1 T1,2 L1
T2,1 T2,2 L2
...
Tj,1 Tj,2 Lj
...
TM,1 TM,2 LM
S D

Nは都市の総数であり、2以上100000以下の自然数である。 続くN行は、各都市の番号iと、位置 Xi, Yiである。 iは整数で、Xi, Yiは実数である(0≦i≦N-1)。 Mは都市を結ぶ道の総数であり、1以上100000以下の自然数である。 続くM行は、 都市 Tj,1と都市Tj,2との間に 長さLjの道路があることを表す(1≦j≦M)。 Tj,1, Tj,2は整数であり、Ljは実数である (0≦Tj,1≦N-1, 0≦Tj,2≦N-1, Lj≧0)。 S, Dは整数であり、それぞれ始点と目的地の都市番号を表す。

与えられたデータに対し、始点から目的地までの最短距離を求めるプログラムを作成せよ。

出力

始点から目的地までの最短道のりを出力しなさい。 もしも目的地まで到達できない場合は -1 と出力すること。

プログラム












RunAStar.javaの実行例
$ javac RunAStar.java
$ java RunAStar <astardata01.txt
45.0
checked node = 6       <-- 課題5aの変更を加えた場合に出力される
$ java RunAStar -n <astardata01.txt
45.0
checked node = 7      <-- 課題5aの変更を加えた場合に出力される
$ java RunAStar <JapanAStarData.txt
795.4155121540113
checked node = 652    <-- 課題5aの変更を加えた場合に出力される
$ java RunAStar -n <JapanAStarData.txt
795.4155121540113
checked node = 1968      <-- 課題5aの変更を加えた場合に出力される






astardata01.txt
7
0 0.0 0.0
1 5.0 1.0
2 2.0 5.0
3 5.0 5.0
4 10.0 0.0
5 0.0 10.0
6 20.0 20.0
10
0 1 30
0 3 10
0 2 15
1 3 25
1 4 60
2 3 40
2 5 20
3 6 35
4 6 20
5 6 30
0 6





ここで使ったデータは以下のURLにあります。





http://http://ynitta.com/class/algoC/JapanAStarData.txt

を入力データとして計算した結果を、日本地図と重ねた図を以下に示します。
図中で、マゼンダの線が都市の間を結ぶ道路を表し、丸は都市を表しています。
都市は色によって


という状態を表しています。
A*アルゴリズムの方がダイクストラ法よりも計算が少なくて済むことが
よくわかります。




Dijkstra法








A*アルゴリズム










アルゴリズムc 演習






作成したプログラムが正しく動作することを確認したら、それぞれの
提出先に提出しなさい。





提出した後は、正しく提出されていることを

http://ynitta.com/class/algoC/local/handin/

で必ず確認しておいて下さい。





課題提出〆切は次回の講義の開始時刻です。




課題5a





提出ファイルRunAStar.java


コメント欄:

実行時オプションによる「変更ノードの数」の倍率。
JapanAStarData2.txt と
JapanAStarData3.txt
を入力としたときについてそれぞれ答えること。


提出先:
「宿題提出Web:アルゴリズムB：課題5a」

http://ynitta.com/class/algoC/local/handin/up.php?id=kadai5a








RunAStar.javaのmainメソッド終了時点において、配列nodes[]の要素のうち
nodes[i].valuesの値がDouble.MAX_VALUEでないものの個数を
「変更ノードの数」と定義する。
「変更ノードの数」を表示するようにプログラムを変更しなさい。





「変更ノードの数」が、プログラムを起動するときのオプションによって
どう変わるか調べなさい。
「-nを指定した場合(単なるPriority First Search=ダイクストラ法)」/
「-nを指定しない場合(A*)」を答えること。




たとえば、上記のJapanAStarData.txtを入力とした場合は
1968/652 を計算するので 3.0184 と答えることになります。





入力データは

http://ynitta.com/class/algoC/JapanAStarData2.txt

と

http://ynitta.com/class/algoC/JapanAStarData3.txt

の2種類について調べること。