8

特定のNP完全問題を解決するために存在する最速のアルゴリズムは何ですか？たとえば、巡回セールスマンの素朴な実装はO（n！）ですが、動的計画法ではO（n ^ 2 * 2 ^ n）で実行できます。実行時間がより良い、おそらく「より簡単な」NP完全問題はありますか？

近似ではなく、正確な解に興味があります。

4

3 に答える 3

4

[...]動的計画法では、O（n ^ 2 * 2 ^ n）で実行できます。実行時間がより良い、おそらく「より簡単な」NP完全問題はありますか？

ある種。多項式的に大きな入力で同じ解をエンコードする人工的な問題を作成することにより、多項式の因数分解を取り除くことができます。入力が多項式的に大きいだけである限り、結果として生じる問題はNP完全です。複雑さは、定義上、入力サイズを実行時間にマップする関数であるため、入力サイズが大きくなると、関数はより低いOクラスに入ります。

したがって、入力にn ^ 2の役に立たないビットが埋め込まれたTSPで実行される同じアルゴリズムは、複雑さO（1 * 2 ^ sqrt（n））になります。

于 2009-11-23T17:06:29.410 に答える
4

NP 完全問題の特徴は、NP のどの問題も、せいぜい多項式時間で任意の NP 完全問題に機械的に変換できることです。

したがって、任意の NP 完全問題の最適な解が何であれ、それは自動的に他の NP 問題の同様に優れた解になります。

動的計画法が巡回セールスマン問題を 2^n 時間と 2^n 空間で解決できることを考えると、同じことが他のすべての NP 問題にも当てはまります [まあ、変換を適用する時間に加えて、2^ になる可能性があります。 (n+1)]。

于 2009-11-22T02:05:42.303 に答える
0

一般に、すべての組み合わせを試さない限り、一般的な巡回セールスマンの問題の最適な解を見つけることはできません(負の距離などがある場合があります)。

制限を追加し、最適なソリューションを得るための要件を緩和することで、作業をかなりスピードアップできます。

たとえば、問題の距離が「A から C から B に移動するよりも、A から B に直接移動する方が長くない」(つまり、近道は決して長くない) に従う場合、多項式の実行可能時間を取得できます。結果は最大で最適値の 1.5 倍になります。http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSPを参照してください

于 2010-11-28T01:12:46.273 に答える