すべての都市への道を見つけるアルゴリズム

Question

私は、この問題の解決方法としてはすでにまっすぐ進むアルゴリズムがあると思っていますが、このタイプの問題が何であるか、そして解決策を探すべきかは不明です。 それはいくつかの方法で旅行セールスマンの問題に似ていますが、私はそれがはるかに簡単にすべきだと思います。 問題の主な違いは、都市の間で接続が限定されている（都市ごとに3〜6）です。 パスは、開始に戻る必要はありません、それだけは各都市を一度だけ訪問します。 の接続もすべて同じ長さなので、絶対パスの長さは常に同じです（最短距離問題ではありません）。 84件の引用があり、最終的な経路は常に87単位になります。 基本的に私はランダムなスタートからあらゆる解決策を探しています。私は秩序に見えない "ランダムな"ソリューションを期待しています。 このタイプの問題が何のために呼び出され、どのようなアルゴリズムが見つかるかについてのアドバイス。おかげさまで

Answer 1

あなたはHamiltonian Pathを探しています。残念ながら、この問題はNP完全ですが、グラフの頂点が限られているため、扱いやすさが向上しません。この問題の解決方法の詳細は、リンク先のWikipediaのページまたはthis answerにあります。