search - グラフ内のすべてのノードを訪問し、繰り返し訪問が最も少ない

Question

いくつかのタイルが壁で、他のタイルが歩きやすいタイルベースのマップがあります。歩きやすいタイルは、経路計画で使用したいグラフを構成します。私の質問は、グラフ内のすべてのノードを訪問し、繰り返しの訪問を最小限に抑えるパスを見つけるための優れたアルゴリズムはありますか?

例えば：

一番下の黄色のタイルが開始点である場合、繰り返しが最も少ないすべてのタイルにアクセスするための最適なパスは次のとおりです。

このパスには 2 回の再訪があります。悪い道は、最初のジャンクションで左折し、すでに訪れた 3 つのタイルを引き返すことです。

終了ノードは気にしませんが、開始ノードは重要です。

ありがとう。

編集：

質問に写真を追加しましたが、表示時にそれらを見ることができません。どうぞ：

さらに、グラフでは最小繰り返し数 = 0 という状況は決してないため、これが必要です。つまり、マップ内のすべてのタイルを踏むには、プレイヤーは自分のパスを少なくとも 1 回横断する必要があります。

score 1 · Accepted Answer

あなたの言い回しは悪いです-それはNP完全問題への還元を可能にします。繰り返しの訪問を最小限に抑えることができれば、それらを 0 にプッシュできれば、ハミルトニアンサイクルが得られます。これは解決可能ですが、難しいです。

score 0 · Accepted Answer

これは、巡回セールスマン問題にマッピングできるように思えます...そのため、最終的に NP 完全になる可能性が高く、効率的な決定論的アルゴリズムは知られていません。

パスを見つけるのはかなり簡単です。(または最小の) スパニングサブツリーを見つけてから、深さ/幅優先のトラバーサルを実行します。最適なルートを見つけることは、本当に難しいことです。

動的最適化手法の 1 つを使用して、かなり優れたソリューションに収束しようとすることができます。

最適なパスを生成するために使用できる最小スパニングサブツリーの属性がない限り...しかし、そのための十分なグラフ理論を覚えていません。

2 に答える 2