長いパス、特に方形グリッドサブグラフのアルゴリズム

Question

平面の正方形のタイルを取り、タイルの有限の接続された単純に接続されたサブセットDを想像してください。もちろん、Dは、各タイルのノードを取り、隣接ノードを接続することによって、正方形グリッドの特定の部分グラフとして解釈することもできる。

Dの境界にD との両方に開始ノード/タイルAと終了タイルBがあるとします。

AとB間のDで、かなり長い自己回避経路を見つけるための単純で直接的なアルゴリズムはありますか？

私は、最長の絶対パスを見つけることに関連する文献、および非常に優れた外観を非常に複雑にする準最適なアルゴリズムを発見しました。私は、十分にうまくいくようなタイマーアルゴリズムが存在するかどうか疑問に思っていました。

私の唯一のアイデアは、A *の最短経路を計算し、できるだけ多くのスペースを埋めるために横方向に「折りたたむ」ことで歪ませることですが、それが良い考えかどうかは分かりません。

もう1つのアイデアは、AとBの間のスペースを埋めるようにほぼ愚かに簡単な「スキャンライン」パターンがあるかどうかです。したがって、「矩形」のDに対してうまく機能します。これは存在すると思われますが、

Answer 1

2次元以上の正方形グリッドの場合：
最長パスの問題はNP-Hardとみなされます。任意のグラフに対してP = NPでなければ多項式時間で解くことはできません。

これは、各ノードでDFSを実行して、最長のパスを決定することができたということです。これは、グラフが重み付けされていることを前提としています（これはあなたの投稿には表示されていません）。頂点を繰り返さないように注意してください。

DFSの最後に、現在の最長パスと以前に最も長いと見なされているパスとを比較します。この結果を、必要な限り多くの時間で交換してください。

実行時間はあまり長くありません。 exponential

For square grid that is 2-Dimensions