私はC ++プログラムをやろうとしています.私はポイントの数がある問題をやろうとしています. 次に、すべてのポイントを通過するパスを見つける必要があります。これは実際には TSP ではありません。TSP に関する私の知識によれば、すべてのポイントから他のすべてのポイントに移動できるからです。しかし、私の場合、ポイント間のパスネットワークは固定されており、すべてのポイントが他のすべてのポイントに接続されていない可能性があるという条件で、すべてのポイントを通過する適切なパスを見つける必要があります。
2 に答える
1
グラフをトラバースする方法を探しているようですか? その場合は、幅優先検索http://en.wikipedia.org/wiki/Breadth-first_searchまたは深さ優先検索http://en.wikipedia.org/wiki/Depth-first_searchを試して、グラフをトラバースしましたか。
于 2012-12-02T02:42:33.030 に答える
1
グラフのハミルトニアン パスを見つけたいとします。
グラフ理論の数学分野では、ハミルトニアン パス (または追跡可能なパス) は、各頂点を 1 回だけ訪れる無向グラフ内のパスです。ハミルトニアン サイクル (またはハミルトン サーキット) は、サイクルであるハミルトン パスです。このようなパスとサイクルがグラフに存在するかどうかを判断するのが、NP 完全なハミルトニアン パス問題です。
存在するいくつかのテクニック：
あります！与えられた n-頂点グラフ (および完全なグラフ) のハミルトニアン パスである可能性のある頂点のさまざまなシーケンス。そのため、考えられるすべてのシーケンスをテストするブルート フォース検索アルゴリズムは非常に遅くなります。より高速なアプローチがいくつかあります。フランク ルービンによる検索手順では、グラフのエッジを 3 つのクラスに分けます。つまり、パスにある必要があるもの、パスにあることができないもの、未決定のものです。検索が進むにつれて、一連の決定規則によって未決定のエッジが分類され、検索を停止するか続行するかが決定されます。アルゴリズムは、グラフを個別に解決できるコンポーネントに分割します。また、Bellman、Held、および Karp の動的計画法アルゴリズムを使用して、時間 O(n2 2n) で問題を解くことができます。この方法では、
Andreas Björklund は、包摂と排除の原理を使用して、ハミルトニアン サイクルの数をカウントする問題を、特定の行列行列式を計算することで解決できるサイクル カバーをカウントする、より単純なカウント問題に減らす代替アプローチを提供しました。この方法を使用して、彼は時間 O(1.657n) でモンテカルロ アルゴリズムによって任意の n-頂点グラフのハミルトニアン サイクル問題を解く方法を示しました。二部グラフの場合、このアルゴリズムは時間 O(1.414n) までさらに改善できます。
最大次数 3 のグラフの場合、注意深いバックトラッキング検索により、時間 O(1.251n) でハミルトニアン サイクル (存在する場合) を見つけることができます。
于 2012-12-02T02:45:32.227 に答える