algorithm - ハミルトン閉路からの還元アルゴリズム

Question

ハミルトン閉路問題は次のように要約できると思います。

無向グラフを考えると、ハミルトン閉路は、一度だけのすべての頂点を通過G = (V, E)するツアーです。GG

さて、私がやりたいのは、私の問題をこれに減らすことです。私の問題は：

の重み付き無向グラフG、整数k、および頂点u, v の両方が与えられた場合、合計の重みが少なくともであるからへGの単純なパスはありますか？Guvk

したがって、ハミルトン閉路問題がNP完全であることを知っているので、この問題をハミルトニアンに還元することにより、この問題もNP完全であることが証明されます。私の問題は、それをハミルトニアンに還元する関数です。

（1）については、総重量がk未満の単純なパスをすべて取り出したグラフを通過する線に沿って考えています。（2）の場合、これは実際には問題ではないと思います。ハミルトン閉路がある場合、uからvへの単純なパスを切り取ることができるからです。

だから、私の本当の質問は次のとおりです。

私の解決策は私に正しい答えを与えるつもりですか？
はいの場合、実際のソリューションでこれらのエッジの1つが必要になる可能性に影響を与えることなく、総重量がk未満の単純なパスを生成するエッジをどのように取り除くことができますか？エッジeがEのサブセットに対して重み<kの単純なパスを生成するために取り出された場合でも、エッジの異なる組み合わせを使用して重み>=kのパスを生成する単純なパスで使用できます。

ありがとう！

score 6 · Accepted Answer

あなたの削減は間違った方向にあります。問題がNP完全であることを示すには、ハミルトン閉路をそれに還元する必要があります。これは非常に簡単です。つまり、すべてのハミルトン閉路問題は、問題の変形の観点から表現できることを示しています。

score 4 · Accepted Answer

答えよりもヒント：

重み付けされていないグラフは、各エッジに重みがある重み付けされたグラフとして解釈できます1。そのようなグラフでは、ハミルトン閉路のコストはどのくらいになるでしょうか？

score 2 · Accepted Answer

サイクルとパスの不一致に関する部分は正しく、解決する必要のある問題です。基本的に、ハミルトン閉路問題もNP完全であることを証明する必要があります（サイクル問題への比較的単純な縮小）

他の部分に関しては、あなたは間違った方向に物事をやっています。より複雑な問題がハミルトン閉路問題を解決できることを示す必要があります（したがって、NP困難です）。これを行うには、基本的に、ユニットコストエッジの特殊なケースを使用する必要があります。

3 に答える 3