グラフ内のすべてのノードを再訪しないでください。

Question

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

：

map example http://img220.imageshack.us/img220/3488/mapq.png

下の黄色のタイルが出発点である場合には、少なくともリピートを有するすべてのタイルを訪問するための最良のパスは次のとおりです。

path example http://img222.imageshack.us/img222/7773/mapd.png

二つがあります。このパスで再訪問します。より悪い方法は、最初のジャンクションで左を取ってから、すでに訪れた3つのタイルにバックトラックすることです。

私は、エンド・ノードを気にしないが、開始ノードが重要です。

ありがとうございました。

編集：

私は私の質問に写真を追加しましたが、それを見たときにそれらを見ることができません。ここで彼らは、次のとおりである分繰り返し= 0は、マップ内のすべてのタイル上のステップに状況があることは決してありませんのために

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

また、グラフに私はこれを必要としますプレイヤーは少なくとも一度は自分のパスを越えなければなりません。

Answer 1

あなたの言葉遣いが悪いです - それはNP完全問題に低減することができます。繰り返し訪問を最小限に抑えることができた場合は、0にプッシュしてHamiltonian Cycleにすることができます。 solvableですが、難しいです。

Answer 2

これは、巡回セールスマン問題にマッピングすることができように聞こえる...ので、おそらく完全と全く効率的な決定論的なアルゴリズムが知られていないNPなってしまいます。経路を見つける

が前方かなりまっすぐである - サブツリースパニング（又は最小値）を検索し、深度/幅優先トラバーサルを行います。最適なルートを見つけることは本当に難しいことです。

あなたは試してみて、かなり良い解に収束する動的な最適化手法のいずれかを使用することができます。

そこに最高のパスを生成するために使用することができ最小全域部分木のいくつかの属性がある...しかし、私は、そのための十分なグラフ理論を覚えていない場合を除き。