「全検索アルゴリズム入門」は、すごく良い記事で勉強になりました。
その中で・・・
例題1:最短歩数の測定
という例題が提示されていますが、なぜ最短歩数が求められるか？
について説明が不足している気がしたので勝手に捕捉。
- 元記事の移動状況を示す図。
引用(探索状況)
(0) (1) (2) (3)
s 0 0 0 0 s B 0 0 0 s B 0 0 0 s 0 E 0 0
0 0 1 0 0 A 0 1 0 0 0 D 1 0 0 A D 1 0 0
0 1 0 0 0 0 1 0 0 0 C 1 0 0 0 0 1 0 0 0
0 0 g 1 0 0 0 g 1 0 0 0 g 1 0 0 0 g 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0
↑の図に対応する訪問履歴(memo)は、次のように変化していきます。
スタートからの距離
(0) (1) (2) (3)
s 0 0 0 0 s 1 0 0 0 s 1 0 0 0 s 1 2 0 0
0 0 0 0 0 1 0 0 0 0 1 2 0 0 0 1 2 0 0 0
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0
0 0 g 0 0 0 0 g 0 0 0 0 g 0 0 0 0 g 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
つまり、
- sからの移動量が訪問履歴に保持されているのがポイント！
- gに到達した時点で探索は終了するから無駄がないよ！
ってことなんですね。
全検索アルゴリズムを勉強し始めだったので、gに到達した時点で終了するのと、
探索歩数にどういう関係があるんだろう？（ポカーン）
としてたのですが、コレに気が付いてやっと理解できました。
※デバッガで動かしながら変数をwatchしてれば分かるんだろうけど。
例題の解法は幅優先探索でしたが、深さ優先探索も同様にsから一歩ずつ進んで探索するので
同様の考え方で歩数が得られるんですね。
但し、
深さ優先の場合は、sからgまでの経路と移動量を全パターン求め終わって初めて最短経路が判明する。
アルゴリズムを理解してる人にとっては、当然の話なのかもしれませんけど・・・