algorithm - グリッド内の最長パス

Question

グリッド G を指定します。各セルには、[0 - 9] の数字または大文字のアルファベット (Z など) を含めることができます。左上隅から始めることができます。次に、現在のセル番号が a の場合、セルを正確に上下左右に移動できます。アルファベット文字に到達するまで停止します。これらのルールを考慮して、最初からグリッドから出るまでの最大パスを見つけたいと考えています。パスが無限の場合は、「-1」を出力します。

Answer 1

わかりました、動的計画法を使用して解決するには、問題にこれらの重要なプロパティが必要です-

1. 最適な部分構造 - 最適なソル。より小さな問題に最適なソルにつながります。もっと大きな問題に。
2. サブ問題の重複 - 回答を保存して再利用できます (これにより、動的プログラミングの効率が向上します。そうしないと、複雑さが指数関数的に増加します)。

それは、迷路の問題に戻って、いくつかの理論でした。最初から最後までの最大パスが必要なので。これはNP 困難な問題であり、多項式の解は存在しません。正の重みを持つグラフの一般的な最大経路問題は、巡回セールスマンの問題と同じくらい単純です。最長経路にはすべての頂点が含まれるため、目的地に到達する前にすべてのノードを訪問します。

したがって、あなたが取るアプローチはこれです（wikiリンクにも記載されています）-

1. 迷路をグラフと考えてください。その上で DFS を実行すると、DFS ツリーが生成されます。
2. 深さ優先検索ツリーのルートからリーフへのパスのシーケンスを、検索によってトラバースされた順序で使用して、パス幅ダイを使用してグラフのパス分解を構築します。この DFS ツリーをトラバースすると、1 つのパスは次のようになります。から始まり、aで終わる根から葉までそこにありますz。
3. このパス分解に動的計画法を適用して、最長パスを見つけます。