Ich möchte nur, dass jemand überprüft, ob das folgende Problem NP-vollständig ist oder ob es tatsächlich eine bessere/einfachere Lösung als einfache Brute-Force-Kombinationsprüfung gibt.Mögliches NP-vollständiges Problem?
Wir haben in unserer Software ein Problem bei der Ressourcenverteilung, und ich werde es mit einem Beispiel erklären.
Sagen wir, wir brauchen 4 Leute, die während der Tagschicht arbeiten. Diese Nummer und die Tatsache, dass es sich um eine "Tagesschicht" handelt, ist in unserer Datenbank gespeichert.
Wir benötigen jedoch nicht nur irgendjemanden, um diese Stellen zu füllen, es gibt einige Anforderungen, die erfüllt werden müssen, um die Rechnung zu erfüllen.
Von diesen 4, sagen wir 2 von ihnen muss eine Krankenschwester sein, und 1 von ihnen muss Ärzte sein.
Einer der Ärzte muss auch als Teil eines bestimmten Teams arbeiten.
So haben wir diesen Satz von Informationen:
Tagschicht: 4
1 Arzt
1 Arzt, müssen im Team arbeiten A
1 Krankenschwester
Das Obige ist nicht das Problem. Das Problem tritt auf, wenn wir anfangen, Leute auszuwählen, um die Tagesschicht zu arbeiten und herauszufinden, ob die Leute, die wir bisher ausgewählt haben, tatsächlich die Kriterien erfüllen können.
Nehmen wir zum Beispiel, wir wählen James, John, Ursula und Mary zu arbeiten, wo James und Ursula sind Ärzte, John und Mary sind Krankenschwestern.
Ursula arbeitet auch im Team A.
nun je nach Auftrag, den wir versuchen, die Rechnung zu passen, könnten wir herzuleiten am Ende, dass wir die richtigen Leute haben, oder nicht, es sei denn, wir verschiedene Kombinationen starten versuchen.
Zum Beispiel, wenn Sie in der Liste nach unten gehen und Ursula zuerst auswählen, können wir sie mit den Kriterien "1 Arzt" abgleichen. Dann kommen wir zu James, und wir stellen fest, dass, da er nicht in Team A arbeitet, die anderen Kriterien über "1 Doktor, müssen in Team A arbeiten" nicht mit ihm erfüllt werden können. Da die anderen beiden Personen Krankenschwestern sind, werden sie auch diese Kriterien nicht erfüllen.
Also gehen wir zurück und versuchen James zuerst, und auch er kann die ersten Kriterien erfüllen, und dann kann Ursula die Kriterien erfüllen, die dieses Team braucht.
So sieht das Problem für uns aus, wie wir verschiedene Kombinationen versuchen müssen, bis wir entweder alle ausprobiert haben, in diesem Fall haben wir einige Kriterien, die noch nicht gefüllt sind, auch wenn die Gesamtzahl der Köpfe arbeitet Genauso wie die Gesamtzahl der benötigten Köpfe, oder wir haben eine Kombination gefunden, die funktioniert.
Ist dies die einzige Lösung, kann jemand an einen besseren denken?
bearbeiten: Einige Klarstellung.Die Kommentare zu dieser Frage erwähnen, dass wir mit diesen wenigen Leuten mit roher Gewalt gehen sollten, und ich stimme zu, dass wir das wahrscheinlich tun könnten, und wir könnten das sogar tun, in der gleichen Richtung, in der einige Optimierungen aussehen bei der Größe der Daten und wählt verschiedene Sortieralgorithmen mit weniger Anfangsaufwand aus, wenn die Datengröße klein ist.
Das Problem ist jedoch, dass dies Teil eines Dienstplansystems ist, in das Sie möglicherweise eine ganze Reihe von Leuten involviert haben, sowohl als "Wir brauchen X Leute auf der Tagesschicht" als auch "Wir haben das Pool von Y-Leuten, die es tun werden ", sowie Potenzial für ein großes" Wir haben diese Liste von Z-Kriterien für die X-Leute, die irgendwie mit diesen Y-Leuten übereinstimmen müssen ", und dann fügst du dem Fakt hinzu dass wir eine Anzahl von Tagen haben werden, um die gleiche Berechnung in Echtzeit durchzuführen, wenn der Leiter den Dienstplan anpasst, und dann ist die Notwendigkeit für eine schnelle Lösung gekommen.
Grundsätzlich wird der Leiter eine Live-Summen-Information auf dem Bildschirm sehen, die angibt, wie viele Personen immer noch vermisst werden, sowohl in der Tagesschicht insgesamt, als auch wie viele Personen die verschiedenen Kriterien erfüllen und wie viele Menschen haben wir zusätzlich zu denen, die wir haben. Diese Anzeige muss halb live aktualisiert werden, während der Anführer den Dienstplan mit "Was ist, wenn James statt Ursula die Tagesschicht übernimmt und Ursula die Nachtschicht übernimmt".
Aber ein riesiges Dankeschön an die Leute, die das bisher beantwortet haben, das Problem der Constraint-Zufriedenheit klingt nach dem Weg, den wir gehen müssen, aber wir werden auf jeden Fall alle Link- und Algorithmusnamen genau hinsehen. Diese
ist, warum ich lieben :) Stackoverflow
Mit Zahlen wie 4 und 2, sehe ich nicht warum * nicht * die einfachste Brute-Force-Suche verwenden. – ShreevatsaR
Ich stimme zu, Sie sollten es einfach brutal erzwingen, wenn es immer klein sein wird. Wenn nicht, müssen Sie eine Heuristik verwenden. Meine Vermutung ist, dass es eine Variante des Knapsack-Problems ist. Ich weiß nicht, warum diese Antwort aus dieser Frage entfernt wurde. –
Ich stimme zu, ich werde die Frage bearbeiten, aber ich denke, die gegebenen Antworten werden uns einen Weg geben, einen Vorsprung zu bekommen. –