Mögliches NP-vollständiges Problem?

StackOverflow https://stackoverflow.com/questions/956699

Frage

Ich mag nur jemand, um zu überprüfen, ob das folgende Problem NP-vollständig ist, oder wenn es tatsächlich eine bessere / einfachere Lösung zu bieten als einfache Brute-Force-Kombination zu überprüfen.

Wir haben eine sorte der Ressourcenallokation Problem in unserer Software, und ich werde es mit einem Beispiel erklären.

Nehmen wir an, wir brauchen 4 Personen bei der Arbeit während der Tagschicht zu sein. Diese Zahl, und die Tatsache, dass es sich um eine „Tagschicht“ wird in unserer Datenbank.

Wir sind jedoch nicht nur jemand verlangen, um die Flecken zu füllen, gibt es einige Anforderungen, die um gefüllt werden muss, um die Rechnung zu passen.

Von diesen 4, sagen wir mal 2 von ihnen hat eine Krankenschwester zu sein, und 1 von ihnen hat die Ärzte sein.

Einer der Ärzte hat auch als Teil eines bestimmten Team zu arbeiten.

So haben wir diesen Satz von Informationen:

  

Tag-Verschiebung: 4
  1 Arzt
  1 Arzt, müssen in Team A
arbeiten   1 Krankenschwester

Die oben ist nicht das Problem. Das Problem kommt, wenn wir Menschen beginnen Kommissionierung der Tagschicht zu arbeiten und versuchen, herauszufinden, ob die Leute, die wir bisher aufgenommen haben, können die Kriterien tatsächlich füllen.

Zum Beispiel, sagen wir, wir James, John, Ursula und Mary holen, zu arbeiten, wo James und Ursula Ärzte, John und Mary sind Krankenschwestern.

Ursula arbeitet auch in 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 beginnen wollen.

Zum Beispiel, wenn die Liste nach unten gehen und holt Ursula ersten, könnten wir sie mit den „1 Arzt“ Kriterien entsprechen. Dann kommen wir zu James, und wir bemerken, dass, da er nicht Team A funktioniert in, die anderen Kriterien über „1 Arzt, müssen Team A arbeiten in“ kann nicht mit ihm gefüllt werden. Da die beiden anderen Personen Krankenschwestern sind, werden sie diese Kriterien entweder nicht passen.

So

wir ansetzen und versuchen, James zuerst, und er kann auch die ersten Kriterien passen, und dann kann Ursula die Kriterien passen, die dieses Team braucht.

So ist das Problem für uns sieht aus, als wir verschiedene Kombinationen ausprobieren müssen, bis wir haben entweder versucht, sie alle, in diesem Fall werden wir einige Kriterien, die noch nicht gefüllt sind, auch wenn die Gesamtzahl der Köpfe arbeiten, ist die gleiche als die Gesamtzahl der Köpfe erforderlich, oder wir haben eine Kombination gefunden, die funktioniert.

Ist dies die einzige Lösung, jemand eines besseren denken kann?

Bearbeiten . Einige Klarstellung

Kommentare zu dieser Frage erwähnt, dass mit diesen wenigen Menschen, wir mit Brute-Force gehen sollten, und ich stimme zu, das ist wahrscheinlich das, was wir tun könnten, und wir könnten sogar das tun, in der gleichen Spur, die eine Art Optimierungen zu buchen und die Größe der Daten nimmt verschiedene Sortieralgorithmen mit weniger anfänglichen Aufwand, wenn die Datengröße klein ist.

Das Problem ist aber, dass dies Teil eines Roster Planungssystem ist, in dem Sie eine recht geringe Anzahl von Menschen beteiligt haben könnten, die beide als „Wir brauchen X Leute auf der Tagschicht“ sowie „Wir haben diesen Pool von Y Menschen, die es“, sowie Potenzial für eine große‚Wir haben diese Liste der Z Kriterien für die X Menschen, die irgendwie zusammenpassen müssen mit diesen Y Menschen‘, und fügen Sie dann zu der Tatsache, tun werden, dass wir werden eine Anzahl von Tagen haben die gleiche Berechnung für, in Echtzeit zu tun, als der Führer den Dienstplan paßt, und dann wird die Notwendigkeit für eine rasche Lösung kommen.

Grundsätzlich wird der Anführer einer Live-Summeninformation auf dem Bildschirm sehen, der sagt, wie viele Menschen noch vermisst werden, sowohl auf der Tagschicht als Ganzes, sowie wie viele Menschen, um die verschiedenen Kriterien passend, und wie viele Menschen, die wir tatsächlich zusätzlich zu denen, ned wir haben. Diese Anzeige muss halb Live aktualisieren, während der Führer den Dienstplan mit „Was ist, wenn James die Tagschicht statt Ursula nimmt, und Ursula nimmt die Nachtschicht“ einstellt.

Aber großer Dank an die Menschen, die dies bisher der Constraint Satisfaction Problem klingt wie die Art und Weise beantwortet hatwir gehen müssen, aber wir werden hier auf jeden Fall hart an alle Links und Algorithmus Namen suchen.

Das ist, warum ich liebe Stackoverflow:)

War es hilfreich?

Lösung

Was haben Sie gibt es eine Constraint Satisfaction Problem rel="nofollow; ihre Beziehung zu NP ist interessant, weil sie in der Regel NP sind aber oft nicht NP-vollständig, das heißt, sie zu polynomialzeit-Lösungen lenkbar sind.

Wie ebo in den Kommentaren erwähnt, Ihre Situation klingt wie es als ein genaue Abdeckung Problem formuliert werden kann, , die Sie anwenden können, Knuth-Algorithmus X . Wenn Sie diese tack nehmen, lassen Sie es uns wissen, wie es für Sie funktioniert.

Andere Tipps

Es sieht wie Sie ein Constraint Satisfaction Problem rel="nofollow haben.

In Ihrem Fall würde ich besonders Blick auf Constraint-Propagation-Techniken zuerst - Sie in der Lage sein, das Problem auf eine überschaubare Größe, die Art und Weise zu reduzieren.

Was passiert, wenn niemand die Kriterien erfüllt?

Was Sie beschreiben das 'Mitbewohner Problem' ist, wird es leicht beschrieben in diese These .

Bär mit mir, ich bin auf der Suche nach besseren Verbindungen.

Bearbeiten

Hier ist ein weiterer ziemlich dicht These rel="nofollow.

Wie bei mir, ich würde am ehesten zu finden Reduktion auf zweiteilige Graphen passende Problem. Auch dieses Problem zu beweisen, ist NP in der Regel ist viel komplizierter, als zu bleiben Sie können nicht Polynom Lösung finden.

Ich bin nicht sicher, ob Ihr Problem NP ist, es riecht nicht so, aber was ich tun würde, wenn ich Sie wäre, um die Anforderungen für die Positionen so zu anordnen, dass Sie versuchen, die spezifischen ersten, da weniger Menschen zu füllen sein wird, diese Positionen, so dass Sie weniger wahrscheinlich zu haben, um eine Menge Rückzieher zur Verfügung zu füllen. Es gibt keinen Grund, warum diese mit Algorithmus X nicht kombinieren sollte, einen Algorithmus aus reinem Knuth-ness.

Ich werde die Theorie auf anderen verlassen, da mein mathematischen versierten nicht so groß ist, aber Sie können ein Tool wie Kasuar / Cassowary.net oder NSolver nützlich zu repräsentieren Ihr Problem deklarativ als Constraint Satisfaction Problem finden und dann löst die Einschränkungen.

In einem solchen Werkzeugen, die Simplex-Methode mit Constraint-Propagation kombiniert wird häufig den Lösungsraum zu deterministisch zu reduzieren eingesetzt und dann eine optimale Lösung einer Kostenfunktion gegeben finden. Für größere Lösungsräume (die in der Größe Problem, das Sie angeben, gelten nicht scheinen) sind, gelegentlich genetische Algorithmen verwendet werden.

Wenn ich mich richtig erinnere, NSolver enthält auch in Beispielcode eine Vereinfachung einer tatsächlichen Krankenschwester-rostering Problem, dass Dr. Chun in Hong Kong gearbeitet. Und es gibt ein Papier über die Arbeit, die er getan hat.

Es klingt für mich wie Sie ein paar trennbaren Probleme haben, die viel einfacher sein würde, zu lösen:

- wählen Sie einen Arzt aus Team A - wählen Sie einen anderen Arzt von jedem Team - wählen Sie zwei Krankenschwestern

Sie haben also drei unabhängige Probleme.

Eine Klärung aber tun Sie zwei Ärzte haben müssen (einen von dem angegebenen Team) und zwei Krankenschwestern, oder einen Arzt aus dem angegebenen Team, zwei Krankenschwestern und einen anderen, der entweder Arzt oder eine Krankenschwester sein kann?

Einige Fragen:

  1. Ist das Ziel der Zwänge genau oder nur ungefähr (aber so viel wie möglich)?
    2. zu befriedigen
  2. Kann eine Person Mitglied mehrerer Teams sein?
  3. Was sind alle möglichen Einschränkungen? (Zum Beispiel könnten wir brauchen einen Arzt, der ein Mitglied von mehreren Teams ist?)

Wenn Sie die Einschränkungen befriedigen wollen genau , dann würde ich die Zwänge abnehmend durch Strenge bestellen, das heißt, die diejenigen sind, die meisten härtesten zu erzielen (zB Arzt und Team A in Ihrem Beispiel oben ) überprüft werden sollte erster

Wenn Sie die Einschränkungen befriedigen wollen etwa , dann ist es eine andere Geschichte ... Sie haben eine Art von Gewichtung / Bedeutung-Funktion angeben würde, welche bestimmt, was wir lieber haben, wenn wir kann nicht genau übereinstimmen, und mehrere Möglichkeiten zur Auswahl.

Wenn Sie mehrere oder viele Einschränkungen haben, werfen Sie einen Blick auf geifert Planner (Open Source, Java).

Brute-Force Branch and Bound und ähnliche Techniken zu lange dauern. Deterministischen Algorithmen wie füllt die größten Verschiebungen ersten sind sehr suboptimal. Meta-Heuristiken sind ein sehr guter Weg, damit umzugehen.

Nehmen Sie einen spezifischen Blick auf die realen Krankenschwester rostering Beispiel geifert Planner. Es ist einfach, viele Einschränkungen, wie „junge Krankenschwestern wollen nicht die Samstag Nacht arbeiten“ hinzuzufügen oder „einige Krankenschwestern wollen nicht in einer Reihe zu viele Tage arbeiten“.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top