動画で間違ったこと言っている

某プログラミング入門番組で迷路の脱出アルゴリズムで、右手法（右手を壁に付き、それに沿って進んでいく）を使えば、必ずゴールができる。出来ないものはインチキ迷路である

と言っているのですが、これは迷路内の壁が全てつながっている場合ではないのでしょうか？

No.4 ベストアンサー 回答者： fakeflake 回答日時： 2018/05/08 15:40

> 最短経路は幅優先探索で求めればよいですか？

そういうことになります。ただそれは一歩先に進んだアルゴリズムなので、最初に一番単純な右手法を実装し、右手法の欠点を理解した後にじゃあどんな改良案があるのか？ってなってから登場するものですね。

No.3 回答者： fakeflake 回答日時： 2018/05/08 10:21

右手法にしても左手法にしても、やっていることは一緒で、迷路内のすべての通路を例外なく通ることで出口を探すアルゴリズムです。

なんですが、インチキっていうかスタート地点がこの画像みたいな迷路だと、赤い矢印のところから右手法で進んでも永久ループになるだけです。つまりこの場合は左にしないといけない。No.1さんの回答で言っているのはそういうことでしょうね。これをインチキって言うのは負け惜しみだろって思いますけど、アルゴリズム学習ではこういう迷路は最初は避け、次の段階の課題になるかなあと。

これに対応する方法としては、今いる地点のX,Yと進んだ手順（方向と距離）を覚えておいて、同じ手順で同じ地点に2度来たらループだと判断して左右を替える…みたいな感じになりそうです。

後これは完全に余談なんですけど、迷路の正解の厳密定義は「スタートとゴールを最短距離で結ぶ経路を言う」なので、右手法だけでは脱出はできても正解とは呼べないことになっちゃいますね。見つけた経路を最適化しないといけない。

この回答へのお礼

最短経路は幅優先探索で求めればよいですか？

お礼日時：2018/05/08 13:55

No.2 回答者： yambejp 回答日時： 2018/05/07 22:26

実際に書いてみればわかるが「脱出」するのであれば可動式の壁でない限り

かならずつながっているので、とくにプログラム入門ということであれば
極端な例外を論じる必要はないので、ロジックとしてはあっているはず。

どちらかといえばいきどまりから分岐までを塗りつぶすほうが迷路はときやすい

No.1 回答者： don_go 回答日時： 2018/05/07 22:12

ゴールやスタートが迷路中央部に存在する場合には、右手法では

脱出できない場合が有ります。
＃立体的な迷路でも役には立いません。