問題タブ [np-complete]

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

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

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

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

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

だから私の質問は：

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

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

ブール値の充足可能性がNP完全であることは知っていますが、ブール式の最小化/単純化です。これは、特定の式を記号形式で取得し、同等であるが単純化された式を記号形式で生成することを意味します.NP完全ですか？充足可能性から最小化への減少があるかどうかはわかりませんが、おそらくあると思います。誰かが確かに知っていますか？

NP完全性は、ほとんどが理論上のものであり、通常の作業環境で遭遇するようなものではないものの1つに似ているように思えます。

ですから、誰かが仕事でNP完全であることが判明し、それに対応するために設計を変更する必要があるという問題に遭遇したことがあるかどうか、私はちょっと興味がありますか？

番号のリストがあります。
このリストは、合計の差が最小限になるように、同じサイズの 2 つのリストに分割されます。合計を印刷する必要があります。

場合によっては、次のコード アルゴリズムにエラーがありますか?

これを最適化および/またはPython化するにはどうすればよいですか?

質問はhttp://www.codechef.com/problems/TEAMSEL/からです

次の問題がNP完全であるかどうか、または単純なブルートフォースの組み合わせチェックよりも実際に優れた/簡単な解決策があるかどうかを誰かに確認してもらいたいのです。

ソフトウェアにある種のリソース割り当ての問題があります。例を挙げて説明します。

日中は4人で仕事をする必要があるとしましょう。この数と、それが「デイシフト」であるという事実は、私たちのデータベースに記録されています。

ただし、これらのスポットを埋めるのに誰もが必要なわけではありません。法案に合わせるために満たす必要のある要件がいくつかあります。

それらの4つのうち、2つは看護師でなければならず、1つは医師でなければならないとしましょう。

医師の1人も特定のチームの一員として働く必要があります。

したがって、次の一連の情報があります。

デイシフト：4
   1人の医師
   1人の医師、チームAで働く必要がある
   1人の看護師

上記は問題ではありません。問題は、私たちが日勤で働く人々を選び始め、これまでに選んだ人々が実際に基準を満たすことができるかどうかを理解しようとするときに起こります。

たとえば、James、John、Ursula、Maryを選んで仕事をするとします。ここで、JamesとUrsulaは医師、JohnとMaryは看護師です。

UrsulaはチームAでも働いています。

さて、私たちが法案に適合させようとする順序によっては、さまざまな組み合わせを試し始めない限り、適切な人材がいるかどうかを推測してしまう可能性があります。

たとえば、リストを下に移動して最初にUrsulaを選択すると、彼女を「1人の医師」の基準に一致させることができます。次に、ジェームズに行きます。彼はチームAで働いていないため、「1人の医師、チームAで働く必要がある」に関する他の基準を彼で満たすことができないことに気付きました。他の2人は看護師であるため、その基準にも適合しません。

したがって、最初にジェームズをバックトラックして試してみると、彼も最初の基準に適合でき、次にウルスラはそのチームを必要とする基準に適合できます。

したがって、すべてを試すまでさまざまな組み合わせを試す必要があるため、問題が発生します。この場合、動作しているヘッドの総数が合計と同じであっても、まだ満たされていない基準がいくつかあります。必要なヘッドの数、または機能する組み合わせを見つけました。

これが唯一の解決策ですか、誰もがより良い解決策を考えることができますか？

編集：いくつかの説明。

この質問へのコメントは、この少数の人々と一緒に、力ずくで行くべきであると述べています、そして私は同意します、それはおそらく私たちができることであり、ある種の最適化がデータサイズが小さい場合は、データを選択し、初期オーバーヘッドが少ないさまざまなソートアルゴリズムを選択します。

ただし、問題は、これが名簿計画システムの一部であり、「当日シフトにはX人が必要」と「このY人のプールがある」の両方で、かなりの数の人が関与する可能性があることです。それはそれを行うでしょう」、そして大きな「私たちはこれらのY人と何らかの形で一致しなければならないそれらのX人のためのZ基準のこのリストを持っています」の可能性と同様に、そしてあなたは私たちが持っているという事実に追加しますリーダーが名簿を調整するのと同じ計算をリアルタイムで行うのに何日もかかり、その後、迅速な解決策の必要性が出てきました。

基本的に、リーダーには、日中シフト全体でまだ行方不明になっている人の数、さまざまな基準に適合している人の数、実際に何人の人がいるかを示すライブ合計情報が画面に表示されます。私たちが持っているものに加えて、ned。この表示は、リーダーが「ジェームズがウルスラの代わりにデイシフトを取り、ウルスラがナイトシフトを行う場合」で名簿を調整している間、セミライブを更新する必要があります。

しかし、これまでにこれに答えてくれた人々のおかげで、制約充足問題は私たちが進むべき道のように聞こえますが、ここではすべてのリンクとアルゴリズム名を確実に調べます。

これが私がStackOverflowが大好きな理由です:)

この質問は純粋に好奇心からです。私は夏の間学校を休んでおり、楽しみのためにこれを解決するアルゴリズムを実装するつもりでした。それが上記の質問につながりました。この問題はどれくらい難しいですか?

問題: 正の整数のリスト、一連の数学演算子、および等号 (=) が与えられます。整数 (同じ順序で) と演算子 (何回でも) を使用して有効な数式を作成できますか?

例は、質問を明確にする必要があります。

指定: {2, 3, 5, 25} , {+, -, *, /} , {=}
出力: はい

式（私が思うのは1つだけ）は（2 + 3）* 5 = 25です。YES / NOを出力するだけで済みます。

問題はNPにあると思います。これは決定問題 (YES/NO の答え) であり、それを決定する非決定論的ポリ時間アルゴリズムを見つけることができるためです。

を。整数の間に配置する一連の演算子を非決定論的に選択します。
b. 答えが有効な数式であることを確認してください (これは一定の時間で行うことができます)。

この場合、大きな問題はこれです: 問題は P にありますか? (つまり、それを決定する決定論的なポリ時間アルゴリズムはありますか?) または問題の NP は完全ですか? (つまり、既知の NP 完全問題をこれに還元できますか? または同等に、すべての NP 言語のポリ時間はこの問題に還元できますか?) またはどちらでもない? (つまり、NP に問題がありますが、NP 完全ではありません)

注: この問題文は、P が NP と等しくないことを前提としています。また、スタック オーバーフローは初めてですが、homework タグには慣れています。これは確かに単なる好奇心であり、宿題ではありません:)

むしろ、組み合わせアルゴリズムと線形アルゴリズムの定義は何ですか?

明らかに最初の応答者が質問を誤解したため、明確にするために: 私は、線形時間と非線形時間で実行されるアルゴリズムの定義を探しているわけではありません。線形アルゴリズムは、線形最適化問題の解を見つけたり近似したりする手法である線形計画法に何らかの形で関連しています。

NP 困難な問題は非常に難しいため、近似解を見つけようとする分野全体があります。たとえば、巡回セールスマンの問題には、多項式時間で実行され、最良の解の特定の境界内にある解を生成するいくつかの近似解があります。

これらの近似アルゴリズムには、線形アルゴリズムと呼ばれるものもあれば、組み合わせアルゴリズムと呼ばれるものもあります。後者が好まれているようです（なぜですか？）。これらは、私が理解したい2つの概念です。

シミュレーテッドアニーリングを使用して、NP完全リソーススケジューリング問題を解決しています。タスクの候補の順序ごとに、いくつかの異なるコスト（またはエネルギー値）を計算します。いくつかの例は次のとおりです（詳細はおそらく質問とは無関係ですが）：

• global_finish_time：スケジュールがまたがる合計日数。
• split_cost：他のタスクによる中断のために各タスクが遅延する日数（これは、タスクが開始された後の中断を阻止するためのものです）。
• deadline_cost：各期限を過ぎた日数の2乗の合計。

従来の受け入れ確率関数は次のようになります（Pythonの場合）。

これまでのところ、最初の2つのコストを1つにまとめて、結果をにフィードできるようにしていacceptance_probabilityます。しかし、私が本当に望んでいるのはdeadline_cost、常にを優先しglobal_finish_time、global_finish_timeを優先することsplit_costです。

したがって、Stack Overflowに対する私の質問は、複数のエネルギーを考慮に入れながら、常に最初のエネルギーが2番目のエネルギーよりも重要であると見なす受け入れ確率関数を設計するにはどうすればよいかということです。言い換えれば、私はいくつかのコストのタプルとして渡して、賢明な値を返しold_costたいと思います。new_cost

編集：提案されたソリューションを数日間実験した後、私にとって十分に機能する唯一の方法は、異なる単位を持つコストコンポーネントで他の多くの問題を引き起こすにもかかわらず、MikeDunlaveyの提案であると結論付けました。私は実際にリンゴとオレンジを比較することを余儀なくされています。

そこで、値を「正規化」することに少し力を入れました。まず、deadline_costは平方和であるため、指数関数的に増加し、他のコンポーネントは線形に増加します。これに対処するために、平方根を使用して同様の成長率を取得します。次に、コストの線形結合を計算する関数を開発しましたが、これまでに見られた最も高いコスト要素に従って係数を自動調整します。

たとえば、最も高いコストのタプルが（A、B、C）であり、入力コストベクトルが（x、y、z）である場合、線形結合はBCx + Cy+zです。そうすれば、zがいくら高くなっても、xの値が1よりも重要になることはありません。

これにより、新しい最大コストが検出されるため、コスト関数に「ジャギー」が作成されます。たとえば、Cが上がると、BCxとCyは両方とも、特定の（x、y、z）入力に対して高くなり、コスト間の差も大きくなります。コスト差が大きいということは、温度が突然1ステップ下がったかのように、受け入れ確率が低下することを意味します。実際には、これは問題ではありません。最大コストは最初は数回しか更新されず、後で変更されないためです。コストがより低い値に向かって収束することがわかっているので、これは理論的に正しい結果に収束することさえ証明できると思います。

まだ少し混乱しているのは、最大コストが1.0以下、たとえば0.5の場合にどうなるかということです。最大ベクトルが（0.5、0.5、0.5）の場合、これにより線形結合0.5 * 0.5 * x + 0.5 * y + zが得られます。つまり、優先順位が突然逆になります。これに対処する最善の方法は、最大ベクトルを使用してすべての値を指定された範囲にスケーリングすることです。これにより、係数は常に同じになります（たとえば、100x + 10y + z）。しかし、私はまだそれを試していません。

これが私が会計システムで作業しているように見える問題です。

私は一連のトランザクションを持っていますが、それらの合計は、経理部門がそうすべきだと考える金額と等しくありません。彼らは数学に疑問を投げかけているのではなく、含まれているのはトランザクションだけです：p

合計が特定の金額と一致するために、セット内のどのトランザクションを含めるべきでないかを判断するのに役立つアルゴリズムはありますか？

編集： セットに含まれるトランザクションは100未満です。XKCDの質問でNP完全問題を解くことに関するものがないので、誰かがC＃の例を持っていますか？

男、私はCSの学位を取得する必要がありました。

さまざまなサイズのファイルの組み合わせを、たとえばほぼ同じサイズの「n」個のグループにグループ化するのに役立つアルゴリズムを見つけようとしています。

これを達成する方法についてのアイデアはありますか？