次の問題が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が大好きな理由です:)