algorighm c

アルゴリズムc 第4回

Priority First Search

先週は経路の探索を行うダイクストラ法を学習しました。

ダイクストラ法において、疎なグラフ(つまりノード数に比べてエッジの数が少ないグラフ)を扱う場合には、ノード間の接続関係を隣接行列で表現するよりも隣接リストで表現すると、計算量のオーダーは変わりませんが、実際の計算速度が速くなることが期待されます。

すなわち、ダイクストラ法において

ノードの接続を表すデータ構造として、隣接行列ではなく隣接リストを使う
未確定のノードを保持するのにPriority Queue(ヒープ)を使う。

という工夫をすることによって、計算効率を上げることができます (計算量のオーダーは変わりませんが)。このアルゴリズムは Priority First Search (順位優先探索)と呼ばれることがあります。

Priority Queueは「ヒープ」と呼ばれる、「特定のデータへのアクセスがO(log n)で可能」なデータ構造です。

JavaではPriorityQueueクラスが標準ライブラリにありますので、これを使ってPriority First Searchを記述してみましょう。

ノードの数が多い疎なグラフ routedata12.txt に対して、実行させた例を示します。ここで用いた routedata12.txt は http://ynitta.com/class/algoC/routedata12.txt から入手できます。

routedata12.txt(一部)

19500 39126
0 1 5
0 150 8
1 2 9
1 151 1
2 3 4

RunPFSearch.javaの実行例

$ time (java RunDijkstra < routedata12.txt)
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at RunDijkstra.doInput(RunDijkstra.java:16)
        at RunDijkstra.main(RunDijkstra.java:7)

real    0m0.520s  ←途中で例外が起きているのでこの値には意味がありません
user    0m0.031s
sys     0m0.015s

$ time (java -Xmx4300M RunDijkstra < routedata12.txt) 
693.0

real	...省略...  ←正しく測れています
user	0m16.462s
sys	0m2.680s

$ time (java RunPFSearch < routedata12.txt) 
node#19499[19349,693.0]

real	...省略...
user	0m1.946s
sys	0m0.104s

RunDijkstra.java ではノードの接続関係を隣接行列で表現しているので、メモリを多く使い、しかも実行時間が遅くなっています。 java処理系のデフォルトのヒープの大きさでは最後まで計算できないので、 4.0Gバイトまで拡張して計算させています。計算にはかなり時間が掛かりました。

Priority First Searchを用いたRunPFSearch.java では、ノードの接続関係を隣接リストで表現し、未確定ノードの探索に高速化を施しているので使用メモリも少く、実行時間も高速になっています。デフォルトのヒープ(=ここでの「ヒープ」という用語は「プログラムが実行中にデータを置くために確保したメモリ領域」のことです。「ヒープ」という用語には２種類の異なる意味があるので注意が必要です。) の大きさで計算が可能で、しかも実行時間は高速です。

アルゴリズムc 演習

以下の演習で routedata11.txtやroutedata12.txt を入力として RunDijkstra.javaを実行する場合は、 java のヒープの大きさを広げて下さい。

[実行例] time (java -Xmx4300M RunDijkstra < routedata11.txt)

また、プログラムの実行時間の表示に関してですが、 Mac上のtimeコマンドでは次のような表示となります。

real   0m1.611s  ←この値を採用して下さい
user   0m0.015s
system 0m0.000s

このように3種類の値が表示されるはずですが、realとして表示されている値を採用して下さい。mは分、sは秒を表していますので、上の例では 1.611秒ということになります。

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

提出した後は、正しく提出されていることを http://ynitta.com/class/algoC/local/handin/ で必ず確認しておいて下さい。

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

課題4a

提出ファイル	PFSearch.java
コメント欄:	routedata11.txt, routedata12.txt をそれぞれ入力ファイルとしたときの、RunDijkstra.javaとRunPFSearch.javaの実行時間の比
提出先:	「宿題提出Web:アルゴリズムc：課題4a」 http://ynitta.com/class/algoC/local/handin/up.php?id=kadai4a

PFSearch.javaの欠けている部分に適切なコードを書きなさい。

RunDijkstra.javaを http://ynitta.com/class/algoC/routedata11.txt および http://ynitta.com/class/algoC/routedata12.txt に対して動作させて time コマンドで時間を測って下さい(これをaとします)。ヒープ領域を広げないと「メモリが足りない」という例外が起きて計算が途中で終了してしまい実行時間が正しく計測できないので注意して下さい。

さらに、RunPFSearch.javaを http://ynitta.com/class/algoC/routedata11.txt および Http://ynitta.com/class/algoC/routedata12.txt に対して動作させて time コマンドで実行時間を測って下さい(これをbとします)。ここで、「実行時間」とはtimeコマンドの出力行の最初の値 (realの左に表示されている値)とします。

RunPFSearchはRunDijkstraの何倍速いですか? 自分で測定した結果から、同じ入力に対する a/b をそれぞれ計算して答えて下さい。