graph - グラフの最小コスト パス

Question

私はこれにドリルダウンする問題に取り組んでいます:

接続された無向グラフがあります。ノードに複数回アクセスせずに、すべてのノードにアクセスする必要があります。任意のノードで開始および終了できます。

これについてどうすればよいですか？可能なすべての開始ノードに同様のアルゴリズムを適用するFloyd-Warshall必要がありますか、それともより良い方法がありますか?

ありがとう。

Answer 1

すべてのノードを 1 回だけ訪れるパスは、ハミルトニアン パスと呼ばれます。ハミルトニアン パスを見つける問題は、ハミルトニアン パス問題と呼ばれます。

まず、この問題は NP-Complete です。実行時間が最大で入力サイズの多項式に比例するアルゴリズムは、多項式アルゴリズムと呼ばれます。たとえば、ほとんどの並べ替えアルゴリズムは O(N logN) 時間を必要とし、これは N^2 未満であるため、多項式になります。

NP 完全問題の場合、既知の多項式時間アルゴリズムはありません。誰もまだ証明できていませんが、おそらく NP 完全問題に対する多項式時間アルゴリズムはありません。その意味は：

1. 思いつくアルゴリズムの実行時間は、入力サイズの指数関数に比例します。(つまり、40 ノードの問題を 1 時間で解決する場合、41 ノードの場合は 2 時間、42 ノードの場合は 4 時間、..) これは非常に悪いニュースです。

2. あなたが考え出すアルゴリズムは、試行錯誤を繰り返すものよりも基本的にはるかに高速ではありません。

入力サイズが小さい場合は、単純なバックトラッキング アルゴリズムから始めます。さらに改善する必要がある場合は、「ハミルトニアン パス」、「最長パス」などの用語を使用した Google 検索で答えが得られる場合があります。最終的に、入力が大きい場合は、期待値を下げる必要があります (たとえば、最適解ではなく近似値で解決するなど)。