Ich habe mich umgesehen, um zu sehen, ob etwas Ähnliches schon einmal gemacht wurde, aber ich habe nichts mit gespiegelten Bedingungen gesehen. Um das Problem ein wenig verständlicher zu machen, werde ich es im Zusammenhang mit dem Auffüllen des Kaders einer Baseballmannschaft anwenden.
Die vorgegebene Dienstplanstruktur ist wie folgt aufgebaut: C, 1B, 2B, 3B, SS, 2B/SS (entweder oder), 1B/3B, OF, OF, OF, OF, UT (kann jede Position sein)
Jeder Spieler hat mindestens eine der Nicht-Backup-Positionen (Positionen, die mehr als eine Position zulassen), auf denen er wählbar ist, und in vielen Fällen mehr als eine (z. B. ein Spieler, der 1B und OF spielen kann, usw.). Nehmen wir an, Sie sind Manager eines Teams, das bereits einige Spieler hat, und Sie möchten sehen, ob Sie auf einer Ihrer Positionen Platz für einen bestimmten Spieler haben oder ob Sie einen oder mehrere Spieler versetzen können, um eine Position freizumachen, auf der er spielberechtigt ist.
Meine anfänglichen Versuche bestanden darin, eine bedingte Permutation zu verwenden und alle möglichen einzigartigen "Aufstellungen" für jeden Spieler in einer Liste zu sammeln und die offenen Plätze zu aktualisieren, bevor ich zum nächsten Spieler überging. Dies erforderte auch (da die Reihenfolge, in der der Spieler verschoben wurde, sich darauf auswirkte, welche Positionen für den nächsten Spieler verfügbar waren), dass die Liste, die in einer Schleife durchlaufen wurde, neu geordnet und dann erneut durchlaufen wurde. Ich bin immer noch der Meinung, dass dies der richtige Weg ist, aber es gibt eine Reihe von Fallstricken, an denen die Funktion hängen geblieben ist.
Die Daten zum Starten der Schleife, die Sie als gegeben annehmen, sind: 1. Liste der Positionen, die der ausgewertete Spieler einnehmen kann (derjenige, der geprüft wird, ob er passen kann) 2. Liste der Spieler, die derzeit im Dienstplan stehen, und die Positionen, für die jeder von ihnen in Frage kommt (ich speichere derzeit eine Liste von Listen und verwende den Listenindex als eindeutigen Bezeichner des Spielers) 3. Eine Liste der offenen Positionen, wie sie derzeit im Dienstplan stehen
Das hat mir mehr Kopfzerbrechen bereitet, als ich ursprünglich erwartet hatte. Ein Kollege schlug mir sogar vor, dass die Situation, die ich habe (die in viel größerem Umfang bedingte Zuweisungen für jedes Objekt beinhaltet) NP-komplett ist. Ich bin mir sicher, dass dies nicht der Fall ist, denn sobald ein Spieler in einer bestimmten Aufstellung, die getestet wird, neu positioniert wurde, sollte es nicht notwendig sein, den gesamten Dienstplan erneut zu iterieren, sobald ein anderer Spieler gewechselt hat. Das ist die Kurzfassung des Problems, und ich habe mich schließlich entschlossen, es in den Foren zu veröffentlichen.
Vielen Dank für jede Hilfe, die ich erhalten kann. Aufgrund von Beschränkungen kann ich keine Teile des Codes veröffentlichen (einige davon sind veraltet). Es wird jedoch in .NET (derzeit C#) übersetzt. Wenn zusätzliche Informationen erforderlich sind, werde ich versuchen, einige der kurzen Teile der Funktion neu zu schreiben und zu posten.
Joseph G.
BEARBEITET 07/24/2010 Herzlichen Dank für die Antworten. Ich habe tatsächlich die Verwendung eines genetischen Algorithmus in Erwägung gezogen, aber letztendlich verworfen, weil der Arbeitsaufwand für die Ermittlung der ordinalen Ergebnisse überflüssig war. Das eigentliche Ziel des Tests ist es, festzustellen, ob es tatsächlich ein Szenario gibt, das ein positives Ergebnis liefert. Es besteht keine Notwendigkeit, den relativen Nutzen jeder Arbeitslösung zu bestimmen.
Ich bin dankbar für die Rückmeldung, dass ich wahrscheinlich nicht mit dem Kontext vertraut bin, in dem ich das Problem dargestellt habe. Das eigentliche Modell besteht in der Verteilung von Build-Befehlen auf mehrere plattformspezifische Build-Server. Es ist zugänglich, aber ich möchte lieber nicht darauf eingehen, warum bestimmte Build-Aufgaben nur auf bestimmten Systemen ausgeführt werden können und warum bestimmte Systeme nur bestimmte Arten von Build-Befehlen ausführen können.
Es scheint, dass Sie das Wesentliche meiner Ausführungen verstanden haben, aber hier ist ein anderes Modell, das ein wenig weniger spezifisch ist. Es gibt eine Reihe von diskreten Positionen in einer geordneten Reihe von Listen (ich bezeichne sie als "Positionen"):
((2), (2), (3), (4), (5), (6), (4, 6), (3, 5), (7), (7), (7), (7), (7), (2, 3, 4, 5, 6, 7))
Außerdem gibt es ein ungeordnetes Listenfeld (ich nenne es "Mitarbeiter"), das nur dann einen der Plätze belegen kann, wenn sein Feld ein gemeinsames Mitglied mit der geordneten Liste hat, der es zugewiesen werden würde. Wenn nach den anfänglichen Zuweisungen ein zusätzlicher Mitarbeiter hinzukommt, muss ich feststellen, ob er eine der offenen Stellen besetzen kann, und wenn nicht, ob die aktuellen Mitarbeiter so umgeordnet werden können, dass eine der Stellen, die der Mitarbeiter besetzen KANN, verfügbar gemacht werden kann.
Brute Force möchte ich vermeiden, denn bei einer Größenordnung von 40 - 50 Objekten (und bald mehr) sind einzelne Festlegungen zur Laufzeit sehr aufwendig zu berechnen.
