ウィキでTSPについて読んだ後、DPはTSP問題の正確なアルゴリズムであると述べていることがわかりましたが、問題の正確なアルゴリズムがある場合でも、問題はNPCとして分類されるべきでしょうか？どんな答えでも大歓迎です。wikiTSPページ
質問する
1622 次
1 に答える
2
Nitin Gurram のコメントは完全に間違っています。
NP完全問題は正確なアルゴリズムを持つことができます（実際にそうしています）が、現在知られているそのような正確なアルゴリズムはすべて、最悪の場合、指数時間で実行されます。巡回セールスマン問題の素朴だが正確なアルゴリズムは、すべての可能な巡回セールスマン ルートを列挙し、それぞれの長さを計算し、最小のものを選択することです。しかし、このようなパスの数は都市の数に応じて指数関数的に増加するため、アルゴリズムの実行には指数関数的な時間がかかります。あなたが指しているウィキペディアのページは同じことを言っています。
動的計画法のアプローチは単純なアプローチほど悪くはなく、別の正確なアルゴリズムですが、最悪の場合でも指数時間で実行されます。
NP 完全性は、正確なアルゴリズムが存在しないとは言いません。これは、既知の正確な多項式時間アルゴリズムが存在しないことを意味し、その他の技術的な複雑性理論の要件もあります。
(補足として、NP-Complete は NP と同じ複雑さのクラスではありません。すべての NP は、解が与えられたときに多項式時間検証アルゴリズムがあることを意味します。NP-Complete は、前述のように、そのセットのサブセットです。他のいくつかの技術的要件。)
于 2012-12-01T18:46:04.230 に答える