NP完全問題の可能性はありますか?

Question

次の問題が NP 完全であるかどうか、あるいは単純な総当たりの組み合わせチェックよりも優れた/簡単な解決策が実際に存在するかどうかを誰かに検証してもらいたいのです。

私たちのソフトウェアには一種のリソース割り当ての問題があり、それを例を挙げて説明します。

日勤中に 4 人が出勤する必要があるとします。この数字と、それが「日勤」であるという事実は、データベースに記録されます。

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

この 4 人のうち、2 人は看護師、1 人は医師でなければならないとします。

医師の 1 人も特定のチームの一員として働かなければなりません。

したがって、次の情報セットが得られます。

日勤：4
医師1名
医師 1 名、チーム A で働く必要がある
看護師1名

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

たとえば、ジェームズ、ジョン、アースラ、メアリーを仕事に選んだとしましょう。ジェームズとアースラは医師、ジョンとメアリーは看護師です。

ウルスラもチームAで働いています。

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

たとえば、リストを下って最初にウルスラを選択すると、彼女を「医師 1 人」の基準と一致させることができます。次に、ジェームズにたどり着きますが、彼はチーム A で働いていないため、「医師 1 名、チーム A で働く必要がある」という他の基準を彼で満たすことはできないことに気付きます。他の2人は看護師なので、その基準にも当てはまらないでしょう。

そこで私たちは話を戻して、まずジェームズを試してみると、彼も最初の基準を満たすことができ、その後ウルスラもそのチームに必要な基準を満たすことができるでしょう。

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

これが唯一の解決策ですか、誰かもっと良い解決策を思いつきませんか?

---

編集:いくつかの説明。

この質問へのコメントでは、この少数の人々では総当たりで行くべきだと述べています。私も同意します。それがおそらく私たちにできることであり、ある種の最適化がサイズを調べるのと同じレーンでそれを行う可能性さえあります。データのサイズが小さい場合は、初期オーバーヘッドが少ない別の並べ替えアルゴリズムが選択されます。

しかし問題は、これが名簿計画システムの一部であり、「日勤には X 人が必要です」と「Y 人のプールがある」の両方で、かなりの数の人が関与する可能性があることです。 「それはそれを行うでしょう」というだけでなく、「この Y 人と何らかの方法でマッチングする必要がある X 人に対する Z 基準のリストがあります」という大規模な可能性も考えられます。さらに、次のような事実が追加されます。リーダーが名簿を調整するのにリアルタイムで同じ計算を行うには何日もかかるため、迅速な解決策の必要性が生じました。

基本的に、リーダーは、日勤全体で何人がまだ行方不明であるか、さまざまな基準を満たしている人数、および実際に何人であるかを示すライブ合計情報を画面上で確認します。私たちが持っているものに加えてね。この表示は、リーダーが「ジェームズがアースラの代わりに日勤をとり、アースラが夜勤をとったらどうなるか」で名簿を調整している間、半ライブで更新する必要があります。

しかし、これまでにこれに答えてくれた人々のおかげで、制約充足問題は私たちが進むべき道のように思えますが、ここですべてのリンクとアルゴリズム名を注意深く調べることは間違いありません。

これが私が StackOverflow を愛する理由です :)

Answer 1

あなたは制約充足問題ではあり持っている何か。彼らは多項式時間ソリューションに扱いやすいですつまり、NP完全ではないことが多い通常NPしかしだからNPとの関係は、興味深いものです。

EBOはコメントで述べたように、それは正確な被覆問題として定式化することができますように

、あなたの状況は、/ <聞こえますA>、あなたはに KnuthのアルゴリズムX を適用することができました。あなたはこのタックを取る場合、私たちはそれはあなたのためにどのように動作するか教えてくださいます。

Answer 2

あなたは制約充足問題を持っているように見えない。

あなたのケースでは、私は、特に第1の制約伝播手法を見てしまう - あなたは管理可能なサイズにそのように問題を軽減できることがあります。

誰もが基準に適合しない場合は、

はどうなりますか？

Answer 3

あなたが説明しているのは、「ルームメイト問題」で軽く説明されています。 この論文.

もう少し待ってください。より良いリンクを探しています。

編集

これがまたかなり密度の高いものです 論文.

Answer 4

私として私が最も可能性が高い二部グラフマッチングの問題への削減を見つけようとします。また、その問題を証明するために、通常ははるかに複雑あなたは、多項式解決策を見つけることができません滞在よりNPされている。

Answer 5

私はあなたの問題は、それはそのように臭いがしませんが、私はあなたが少数の人々以来、最も具体的な最初のを埋めるためにしようとするような位置のための要件を注文するだろうだった場合、私はどうなるのか、NPであることを確認していませんこれらの位置を埋める利用可能であるので、あなたは多くのことをバックトラックする必要がある可能性が低いでしょう。あなたは、アルゴリズムX、純粋クヌースネスのアルゴリズムと組み合わせるない理由はありません。

Answer 6

私の数学に精通したがそれほど大きくないので、私は、他の人に理論を残しておきますが、あなたは、制約充足問題として宣言あなたの問題を表現するヒクイドリ/ Cassowary.netまたはNSolverのようなツールが役立つし、その後解決することがあり制約ます。

このようなツールは、制約伝播と組み合わせシンプレックス法はしばしば決定的解空間を減少させ、その後、費用関数所定の最適解を見つけるために使用されます。 （指定した問題の大きさには適用していないようだ）大きなソリューションスペースの場合、時折、遺伝的アルゴリズムが採用されています。

私の記憶が正しければ、

、NSolverもサンプルコードで博士チョンは香港での仕事を実際の看護師・rostering問題の簡素化を含んでいます。そして、彼がやった仕事上の紙があります。に

Answer 7

あなたは非常に簡単になり、分離問題のカップルが解決しなければならないように、

それは私に聞こえるます：

- チームAから1人の医師を選択 - どのチームから別の医師を選択 - 2人の看護師を選択し、

あなたは、3つの独立した問題を抱えているので。

明確化は、しかし、次の2人の医師（指定されたチームの1）と2人の看護師、または指定されたチームから1人の医師、看護師2、および医師または看護師のいずれかになります他のものを持っていなければならないのですか？

Answer 8

いくつかの質問：

1. 制約を満たすことが目標である その通り, 、またはのみ 約 （でも可能な限り）？
2. 一人の人が複数のチームのメンバーになることはできますか?
3. 考えられるすべての制約は何ですか?(たとえば、複数のチームのメンバーである医師が必要になる可能性はありますか?)

制約を満たしたい場合 その通り, 、次に、制約を厳密さに従って降順に並べます。つまり、達成するのが最も難しい制約です(例:上記の例では医師とチーム A) をチェックする必要があります 初め!

制約を満たしたい場合 約, 、それなら話は別ですが…正確に一致できず、いくつかの選択肢から選択できる場合に、何を選択するかを決定する、ある種の重み付け/重要度関数を指定する必要があります。

Answer 9

あなたは、いくつかのまたは多くの制約がある場合は、

は、 Droolsのプランナーを見てみましょうする （オープンソースのJava）。

のブルートフォースの、の分岐限定のと同様の技術は、長い間に連れて行きます。そのようなのように決定的アルゴリズムは、最初の最大のシフトを埋めるは非常に最適ではありません。メタヒューリスティクスは、これに対処するための非常に良い方法です。

のDroolsプランナーの実世界での看護師rostering例では、特定のを見てみましょう。それは、このような「若い看護師は、土曜日の夜に動作したくない」または「いくつかの看護師が行に多くの日に仕事をしたくない」など、多くの制約を、簡単に追加することもできます。