問題タブ [np-complete]

今日、SOに関する質問がありました。そこでは、作者はインタビュー中にNP完全問題を与えられましたが、明らかにそれが1つであるとは言われていませんでした。

そのような質問をする目的は何ですか？そのようなことを尋ねるとき、インタビュアーはどのような行動を期待しますか？証拠？便利なヒューリスティック？そして、それが誰もが知っておくべきよく知られたNP完全問題ではないかどうかを尋ねることは正当でさえありますか？（それらはたくさんあります）

周りにはたくさんのチェスAIがあり、明らかに、世界で最も優れたプレーヤーの何人かを打ち負かすのに十分なものもあります。

ボードゲーム「囲碁」で成功するAIを書くために多くの試みがなされてきたと聞いていますが、これまでのところ、平均的なアマチュアレベルを超えるものは考えられていません。

Goで任意の時点で最適な動きを数学的に計算するタスクは、NP完全問題である可能性がありますか？

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

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

NP、NP-Complete、NP-Hardの違いは何ですか?

私はウェブ全体に多くのリソースがあることを知っています。あなたの説明を読みたいのですが、その理由は、それらがそこにあるものとは異なるか、または私が認識していない何かがあるからです.

問題 P が NP-Complete であることを証明するには、既知の NPC 問題を P に還元する必要があると思っていましたが、独立集合問題の解を見ると、そうではないようです。

独立集合が NP 完全であることを証明するには、グラフ G を取り、その逆 G' を見つけ、CLIQUE(G') を計算します。しかし、これは逆のことをしています: それが NPC かどうか PI DON'T がわからない問題を取り上げ、それを既知の NPC 問題に減らします。

ソリューションの例を次に示します。

ここで何が欠けていますか？やり方が逆だからまずいんじゃないの？

NP困難/NP完全であるいくつかのスケジューリング問題があることを私は知っています...しかし、それらのどれもこの状況がNPでもあることを示すような方法で述べられていません。

startAfter、startBy、durationに制約された一連のタスクがあり、すべてが単一のリソースを使用しようとしている場合...スケジュールを解決するか、徹底的な検索なしでは解決できないことを特定できますか？

答えが「申し訳ありませんが、これはNP完全です」の場合、使用するのに最適なヒューリスティックは何でしょうか。また、a）スケジュールを解決し、b）解決できないものを特定するのにかかる時間を短縮する方法はありますか。スケジュール。

「最小ウィンドウファースト」ヒューリスティックを実装する再帰を通じて、基本的な競合解決の目標を（プロローグで）実装しました。これは実際にはかなり迅速に解決策を見つけますが、無効なスケジュールを見つけるのは非常に遅いです。これを克服する方法はありますか？

複雑な質問にイェーイ！

申し訳ありませんが、質問のタイトルが明確ではありません。これは、より具体的な例を提供しないと難しい質問です。次のシナリオを検討してください。

私には、誕生日が近い日付 (d1..dn) の友人が何人かいて、コスト (c1..cn) で購入したいギフトをいくつか考え出すことができました。残念ながら、これらのギフトを購入するために 1 日に節約できる金額 (m) は決まっています。私が聞きたい質問は次のとおりです。

友人の誕生日と私が十分なお金を貯めた日付との間の合計偏差を最小限に抑えるために、ギフトごとの貯蓄の理想的な配分 (mi、1..n == m からの mi の合計) は何ですか?そのギフトを購入する。

私が探しているのは、この問題の解決策、またはこの質問に決定論的に答えるために利用できる解決済みの問題へのマッピングです。ご検討いただきありがとうございます。さらに説明できることがあればお知らせください。

この問題は現実の世界で発生しましたが、私はそれをより一般的な「教科書のような」定式化に翻訳しました。NPだと思いますが、名前があるのか​​、よく知られているのか、初めて出会うことはできないと思いますので、特に興味があります。;-)

N人のゲストとの持ち寄りパーティーがあると想像してみてください。各ゲストは、自分の「署名料理」をパーティーに持ち込むことも、何も持ち込まないこともできます。各ゲストは、他のゲストが持ってくる可能性のある各料理を好きか嫌いかのどちらかですが（彼らはすべて古くからの友人なので、これは事前にわかっています！）、彼らはすべて自分の料理が好きです。

すべてのゲストが自分の好みに合わせて少なくとも1つの料理を見つけるという制約を満たす、最小の料理セットを見つけるのに指数関数的な時間をかけない決定論的アルゴリズムはありますか？私は「最小」と言いますが、実際には複数の解決策があるかもしれません。可能であれば、それらすべてを知りたいと思います。

または、より抽象的な方法で、すべての要素が0または1であり、すべての対角要素が1である正方行列を想像してください。セットにゼロはありませんか？（行は料理、列はゲスト、1はゲストが料理を好むことを意味し、対角要素は誰もが自分の料理を好むため1です。）

これは、非正方行列に一般化するか、diagonal = 1ルールを削除することで一般化できます（ただし、後者は常に少なくとも1つの解が存在することを保証します）。しかし、私は今のところそれらのケースを気にしません...

私はすでに全数検索でそれを解決するプログラムを持っており、Nが約20で十分高速ですが、指数関数的な時間がかかります。Nの値を大きくするための十分な解を見つけるには、確率的アルゴリズムを繰り返す必要があるかもしれないと考えています。

追加した

うわー、迅速な回答をありがとう！「セットカバー」、それが私が探していた名前です。:)

まず、これは宿題ではありません（私はAレベルの学生です、これは私たちが問題を解決することに近いものではありません（これははるかに難しいです））が、私が話しかけようとしている問題の多くはプログラミングロジックを改善します。

ランダムな整数の配列があるシナリオを考えました。たとえば、10個の整数です。ユーザーはカウントしたい数値を入力し、アルゴリズムはその合計を計算するために必要な数値を計算しようとします。たとえば、この整数の配列から合計44を作成したい場合は、次のようにします。

出力は次のようになります。

またはそれらの線に沿った何か。私は自分自身を明確にしたいと思います。追加のボーナスとして、必要な合計を作成するためにアルゴリズムができるだけ少ない数を選択するようにするか、指定された数で合計が作成できない場合はエラーを出します。

再帰を使用して配列を反復処理し、合計が満たされるか過ぎてしまうまで数値を何度も追加することを考えました。しかし、私が頭を悩ませることができないのは、アルゴリズムが合計を超えて、配列から選択する数値を選択する必要がある場合にどうするかです。

私は完全なコードや完全なアルゴリズムを探しているのではありません。これをどのように進めるべきかについてあなたの意見を求め、おそらくいくつかのヒントなどを共有します。私はおそらく今夜これに取り組み始めるでしょう。：P

私が言ったように、宿題ではありません。もう少し進んだことをしたいだけです。

あなたが提供することができるどんな助けにも感謝します。:)