迷路問題を解くバックトラッキング法

はじめに

最近、leetcode でいくつかのアルゴリズムの質問を読みました。その中には非常に単純で一般的に使用されているように見えましたが、次のような問題を一度に解決する方法がわかりませんでした。もちろん、高度な数学が苦手な方にとっては、一見簡単な問題を初めて解くのは難しいでしょう。今日お話しするのは、そのような問題です。この問題を解決する方法 バックトラックの考え方に関しては、この考え方を理解していないと、少し複雑な問題の多くは解決することが困難になります。 实现sqrt函数,求数组的排列

問題の説明

この問題は、本当にどこにあるのか思い出せません。

<code>1   1   1   1

0   1   0   1

0   1   0   1

0   1   1   1</code>

上部は迷路、左上隅が入り口、右下隅が出口です。シャオメン (そう、正しく読んでください。草のあるシャオミンです) が入り口から入って、そこから逃げます。出口（1時間以内に逃げられない） モンスターに食べられます

この質問は非常に単純で、答えはすぐにわかりますが、考えをコードに変換するときにどこから始めればよいかわかりません。

解決方法

この問題に対する 1 つの解決策は、バックトラッキング手法です。バックトラッキング手法の定義 (Baidu Encyclopedia) を見てみましょう:

バックトラッキング手法 (探索およびバックトラッキング手法) は、最適化の手法です。ヒューリスティック手法と呼ばれ、目的を達成するために最適な条件に従って検索を進めます。しかし、探究が一定の段階に達し、最初の選択が最適ではない、または目標を達成できないことがわかった場合、一歩下がって別の選択をします。うまくいかなかった場合は、戻って再試行するというテクニックです。バックトラック方法と、バックトラック条件を満たす特定の状態にある点を「バックトラックポイント」と呼びます。

私のアイデア:

上の迷路を左上隅が(0,0)、右下隅が(3,3)で、その他の点が座標系に点在しています
• 
  
より( 0, 0) 開始
• 
  
与えられた座標点から開始し、まず右方向に検索し、1であれば継続、0であれば下方向に検索し、検索前に検索した座標を記録します
• 
  
座標は (3,3 ) に等しいので、この時点で戻ることもできます
• 
  
境界を越えない限り、3 番目のステップを繰り返します

私の PHP 実装を見てください:

リーリー

上記では、関連する側面を含めて迷路の問題を解決するためのバックトラッキング方法を紹介しました。PHP チュートリアルに興味のある友人に役立つことを願っています。