「某社の採用試験は迷路の最短経路探索プログラム」記事へのコメント

矩形壁迷路限定

[nodocuments (12199)]

0pass目でマップ全体を読み込んでS,G,壁をマーク。
1pass目で壁が3方向にある通路(行き止まり)をマーク
2pass目で壁が2方向未満の通路(分岐)をマーク
3pass目で、1pass目でマークした位置から2pass目でマークした位置に当たるまでを壁としてマーク。もし、SやGに当たったら経路なし迷路で終了。
1pass目に戻す。
1pass目の結果が0で2pass目が2以下(SとGのみ)なら、通路として残った経路が最短距離。2pass目が3以上なら残った通路に対してSからの距離をマークしていく。
つまりokky氏やTarZ氏のやりかたです。

経路が一つしかない場合や、経路が存在しない場合はこれが最速だと思います。

Re:矩形壁迷路限定

[GeoJ (32542)]

okky氏やTarZ氏の方法は各マス（文字）をノードとした時のダイクストラ法です。
通路単位での処理はしていませんので、アルゴリズムとしては異なるのではないでしょうか？

ところで、okky氏やTarZ氏を含め距離を記録するためにメモリを使おうとされていますが、
ダイクストラ法で各マス（文字）をノードとするとリンクの重みがすべて等しくなるので、
実際には処理したノードを「これまで」、「現在」、「次」の三種類に分類してそれぞれに
最短経路方向を記録できればよく、「未処理」、壁と始終端を合わせて16通りで表現できます。
なので、入力イメージを出力用に保持するなら、その空白部分を使うだけでできてしまいます。

この場合、手順としては全ての「現在」について、隣接する「未処理」を「現在」に向いた
「次」としてマークします。これが終わったら全ての「現在」を「これまで」に、全ての
「次」を「現在」に書き換えます。他はokky氏やTarZ氏と同じです。

なお、途中で「現在」と「次」の全探査が必要です。盤面をすべて捜索すると実装は楽ですが、
処理オーダーはノード数の二乗に比例するため他の処理よりも大きくなってしまいます。
元記事の著者がその前の記事でキューやリストの使用について言及していましたが、リスト等で
「現在」と「次」を保持すると、この捜索の処理オーダーをノードに比例する量に削減できます。
もちろんこれはメモリとのトレードオフですが、リストのサイズの最大値はノード数ではなく
盤面の辺長に比例するだけなので、大きさが巨大になる場合には有効です。
本当に問題が巨大で、盤面を圧縮する必要がある場合も、「現在」と「次」をリストに保持すると
ノードは8通りになるので、16通りから1ビット減らせたりします。
ま、3時間の解答時間ではその辺に手をつけることはないでしょうが。