2

ハミルトン経路がグラフに存在するかどうかを見つける問題はNP完全であり、ダイクストラの最短経路アルゴリズムは多項式時間で実行されるため、最短ハミルトン経路を見つけるために変更できないことを読みました。（このロジックは有効ですか？）

しかし、無向グラフ (すべてのエッジが非負のコストを持つ) に 2 つのノード (A と Z など) が与えられ、与えられたノード (A と Z) を持つハミルトニアン パスが少なくとも 1 つあると仮定するとどうなるでしょうか。エンドポイントとして。これらの仕様が与えられた場合、Dijkstra のアルゴリズムを変更して、A と Z を終点とする最短のハミルトニアン パスを見つけることができるでしょうか? (多項式時間)

注: 特に 2 つのノードから最短のハミルトニアン パスを見つけることにのみ関心があります。たとえば、26 個のノード (A から Z までのラベルが付いている) を含むグラフがある場合、すべての点を通過するが、A で始まり Z で終わる最短のパスは何ですか? (異なるエンドポイント、A と Z のみ)

追加の質問: 答えが「いいえ」で、これを解決するために使用できる別のアルゴリズムがある場合、それはどのアルゴリズムで、その時間計算量はどれくらいですか?

(注: この質問にはタグとして「hamiltonian-cycle」が含まれています。タグ「hamiltonian-path」を作成するのに十分な担当者がいないため、Hamiltonian PATH を探しています。ただし、A と Z としましょう。がちょうど 1 つのエッジで接続されている場合、最短のハミルトニアン サイクルを見つけてから、A と Z を接続するエッジを削除することで、最短のハミルトニアン パスを見つけることができます)。

4

2 に答える 2

1

しかし、無向グラフ (すべてのエッジが非負のコストを持つ) に 2 つのノード (A と Z など) が与えられ、与えられたノード (A と Z) を持つハミルトニアン パスが少なくとも 1 つあると仮定するとどうなるでしょうか。エンドポイントとして。これらの仕様が与えられた場合、Dijkstra のアルゴリズムを変更して、A と Z を終点とする最短のハミルトニアン パスを見つけることができるでしょうか? (多項式時間)

どのように変更することを提案しますか? これは、A と Z の間に単一のパスがあり、グラフ上の他のすべてのポイントを訪問する場合にのみ機能します。そうしないと、ダイクストラは、ノードの一部のサブセットのみを訪問する短いパスを終了します。A と Z の間にハミルトニアン パスがある場合、最長パスの問題を解くことができますが、これも NP 困難です。

于 2014-06-25T04:59:56.710 に答える
1

いいえ、これは不可能です。単純化された問題はまだ NP 困難です。巡回セールスマンからの削減:

与えられたグラフ(V, E)で、それぞれを 1 回だけ訪れる最短経路を見つけますv in V。任意の頂点を取るv in V。vとの 2 つの頂点v_sourceに分割しv_sinkます。Pアルゴリズムを使用して、からv_sourceへの最短ハミルトニアン パスを見つけますv_sink。は、がそれぞれPにアクセスする開始時刻と終了時刻の最短サイクルです。はサイクルであるため、「開始」頂点は関係ありません。したがって、巡回セールスマン問題の解決策でもあります。vv in VPP

削減は明らかに多項式時間(実際には定数)であるため、問題は NP 困難です。

于 2014-06-25T05:33:16.320 に答える