3

3つのNP完全問題を埋め込みたい（そのうちの2つはNP完全であることがわかっており、1つは私自身の考えです）。私は「この質問」を見て、埋め込みの問題を理論的に再解釈することについて考えました。

  • ウェイターは泥棒です。
  • テーブルは店です。
  • 食品は重量の異なる大切なものです。
  • 泥棒は強盗の前にすべてのアイテムの価格と重量を知っています。
  • 彼の目標は、最も効率的な強盗（使用されるナップザックの最大容量、最も価値のあるアイテムを入手）であり、すべての店舗を強盗（少なくとも1つのアイテムを入手）します（強盗ツアーを完了するための最短の方法、各店舗を1回訪問します）。

この部分は2つのNP完全問題を埋め込んでいます。

私の考えは、アイテムが多いほどバッグの重量が増えるということです。バッグの重量が増えると、泥棒は指数関数的に遅くなります。したがって、泥棒のもう1つの標的は、できるだけ早く強盗を終わらせることです。

現時点では、私のアイデアが実際にNP完全であるかどうかはわかりません。たぶん、「重力」はNP完全問題だけではありません。しかし、おそらくそれは巡回セールスマン問題とナップサック問題のこの文脈にあります。

だから私の質問は：

  1. 泥棒のNP完全問題の減速も完了していますか？

  2. これらの3つの埋め込まれた問題を単純なNP完全問題に減らすことは可能ですか？

4

5 に答える 5

2

わかりました、それに従うのは少し難しかったですが、要点を理解していると思います。

XKCD 漫画は、実際の問題を NP 完全にすることがいかに簡単かを示しています。(もちろん、ほとんどのメニューは品数が少なく、値段も一律なので、些細な答えがあることを示すのも簡単です。)

あなたが言及していると思うNP完全問題を「埋め込む」という考えは、ポリ時間の削減を見つけることです。私はそれをSOの他の場所でかなり完全に書きました。

于 2009-02-12T16:20:11.103 に答える
1

これは少し紛らわしいですが、考えられるいくつかの質問に対する私の回答を次に示します。

2 つの NP 完全問題を組み合わせると、NP 完全になります。実際、NP完全問題と他の問題の組み合わせは、NP完全になります。

重力問題が単独で NP 完全であるかどうかを評価する方法がわかりません。ポイント間の時間が距離とバックパックの重量に依存する場合、巡回セールスマン問題の一部であるため、NP 完全です。そうでない場合、正しい解決策は、最も軽いものから最も重いものへと持ち上げることです。

複合問題は、2 つの問題 (どのオブジェクトを盗むか、どのルートを取るか) を組み合わせたものであり、一方を気にせずに一方を解決できるため、2 つを別々にするよりも興味深いとは思えません。重量依存の遅延を追加すると、問題が結合されて独立しなくなる可能性がありますが、最適な盗難をコミットできる速さ以外の評価関数が必要です (最適な盗難はそれ自体の問題であり、それは単なる変更された TSP です)。

また、問題を取り上げ、それらを結合し、複雑にしてから、一般的なより単純な問題を作成することもできません。

于 2009-02-12T17:06:32.647 に答える
0

有益なコメントをありがとう、Cartoonは私に埋め込みの問題についてのアイデアを与えてくれました。書いているときは少し急いでいたので、たくさんの書き間違いをしました。私の主な言語も英語ではないので、編集者は私の質問をより理解しやすくしました。また、ブレインストーミングについて別のコメントが必要です。

チャーリー・マーティン、あなたのリンクに感謝します。

于 2009-02-12T16:29:38.773 に答える
0

余分な重量を運ぶコストはそれ自体では問題ではなく、巡回セールスマン問題のエッジウェイトのパラメーター化です。

この問題の決定バージョンはまだNP完全です。これは、a）特定のツアーのコストがk未満であるかどうかをすばやく確認できるため、NPに含まれているためです。削減では、すべてのエッジの重みを1に設定し、すべての運送費を0に設定します）。

言い換えれば、運送費がTSPを難しくしただけなので、それでもNP困難です（そしてNP完全問題を解決するために使用できます）が、提案された解決策をすばやく確認できないほど難しくはありませんでした決定問題：「このツアーの費用はc未満ですか？」なので、NP完全です。

ナップサック問題の（NP完全）決定バージョンは独立しており、TSP問題で順次解決できます。

したがって、問題全体はNP完全であり、TSP問題とナップサック問題をSATに還元すると（通常、この方向では還元は行われませんが、理論的には可能です）、2つを1つのSATインスタンスとして一緒にエンコードできます。 。

于 2009-02-12T18:27:15.090 に答える
0

正直なところ、あなたが何を求めているのかわかりません。しかし、ある問題を別の NP 完全問題に変換して NP 完全を証明する方法を尋ねているかもしれません。

これに対する答えは、問題を既知の NP 完全問題に変換するために多項式時間で実行されるアルゴリズムを作成し、次に別の多項式アルゴリズムを作成して解を元に戻すことです。

詳細については、まともな教科書を読むか、ウィキペディアのページを参照してください。

于 2009-02-12T16:18:02.670 に答える