Das "Wartelistenproblem"

Question

Eine Reihe von Studenten möchte in Abschnitte für eine Klasse kommen, einige sind bereits für einen Abschnitt angemeldet, wollen aber den Abschnitt wechseln, damit alle auf die Wartelisten kommen. Ein Student kann nur dann in einen neuen Bereich kommen, wenn jemand aus diesem Bereich aussteigt. Keine Schüler sind bereit, einen Abschnitt, in dem sie sich bereits befinden, fallen zu lassen, es sei denn, sie können sicher sein, in einen Bereich zu gelangen, auf den sie warten. Die Warteliste für jede Sektion ist "first come first serve".

Holen Sie so viele Schüler in ihre gewünschten Abschnitte wie Sie können.

Das angegebene Problem kann schnell zu einem festgefahrenen Szenario führen. Meine Frage ist; Gibt es bekannte Lösungen für dieses Problem?

---

Eine triviale Lösung jeden Abschnitt wiederum und zwingt den ersten Student aus der Warteliste in den Abschnitt und dann überprüfen, um zu nehmen wäre, wenn jemand herausfallen am Ende, wenn die Dinge (O (n) oder mehr gelöst werden auf der Nummer des Abschnitts). Dies würde in einigen Fällen funktionieren, aber ich denke, dass es bessere Möglichkeiten geben könnte, mehr als einen Schüler in einen Abschnitt zu zwingen (O (n) oder mehr auf die Schüleranzahl) und/oder mehr als einen Abschnitt gleichzeitig zu bearbeiten (O (schlecht) :-)

Answer 1

Nun, das kommt nur auf die Suche nach Zyklen in der gerichteten Grafik der Klassen oder? Jeder Link ist ein Student, der von einem Knoten zum anderen wechseln möchte, und jedes Mal, wenn Sie einen Zyklus finden, löschen Sie ihn, weil diese Schüler ihre Bedürfnisse miteinander lösen können. Du bist fertig, wenn du keine Zyklen mehr hast.

Answer 2

Dies ist eigentlich ein Grafikproblem. Sie können sich jede dieser Wartelistenabhängigkeiten als Kanten eines gerichteten Graphen vorstellen. Wenn dieser Graph einen Zyklus hat, haben Sie eine der Situationen, die Sie beschrieben haben. Sobald Sie einen Zyklus identifiziert haben, können Sie einen beliebigen Punkt wählen, um den Zyklus durch Überfüllen einer der Klassen zu "brechen", und Sie werden wissen, dass sich die Dinge korrekt einstellen, weil im Diagramm ein Zyklus vorlag.

Answer 3

Ok, lass es uns versuchen. Wir haben 8 Studenten (1..8) und 4 Sektionen. Jeder Schüler ist in einer Abteilung und jede Abteilung hat Platz für 2 Studenten. Die meisten Schüler wollen wechseln, aber nicht alle.

In der folgenden Tabelle sehen Sie die Schüler ihren aktuellen Abschnitt, ihren erforderlichen Abschnitt und die Position in der Warteschlange (falls vorhanden).

+------+-----+-----+-----+ 
| stud | now | req | que | 
+------+-----+-----+-----+ 
| 1 | A | D | 2 | 
| 2 | A | D | 1 | 
| 3 | B | B | - | 
| 4 | B | A | 2 | 
| 5 | C | A | 1 | 
| 6 | C | C | - | 
| 7 | D | C | 1 | 
| 8 | D | B | 1 | 
+------+-----+-----+-----+ 

Wir können diese Informationen in einem Diagramm darstellen:

+-----+   +-----+   +-----+ 
| C |---[5]--->1| A |2<---[4]---| B | 
+-----+   +-----+   +-----+ 
    1    | |    1 
^    | |    ^
    |    [1] [2]    | 
    |    | |    | 
    [7]    | |    [8] 
    |    V V    | 
    |    2 1    | 
    |    +-----+    | 
    \--------------| D |--------------/ 
        +-----+ 

Wir versuchen, einen Abschnitt mit einer Vakanz zu finden, aber wir finden keine. Weil alle Abschnitte voll sind, brauchen wir einen schmutzigen Trick. Nehmen wir also einen zufälligen Abschnitt mit einer nicht leeren Warteschlange. In diesem Fall Abschnitt A und annehmen, hat es eine zusätzliche Position. Dies bedeutet, dass Student 5 in Sektion A eintreten kann und eine freie Stelle in Sektion C hinterlässt, die von Student 7 belegt wird. Es bleibt eine Vakanz in Sektion D, die von Student 2 belegt wird. Wir haben nun eine Vakanz in Sektion A. Aber wir haben diese Sektion angenommen A hat eine zusätzliche Position, so dass wir diese Annahme entfernen können und eine einfachere Grafik erhalten haben.

Wenn der Pfad nicht zu Abschnitt A zurückkehrt, machen Sie die Bewegungen rückgängig und markieren Sie A als ungültigen Startpunkt. Versuchen Sie es mit einem anderen Abschnitt. Wenn keine gültigen Abschnitte mehr übrig sind, sind wir fertig.

Im Moment haben wir folgende Situation:

+-----+   +-----+   +-----+ 
| C |   | A |1<---[4]---| B | 
+-----+   +-----+   +-----+ 
        |     1 
        |     ^
        [1]     | 
        |     | 
        |     [8] 
        V     | 
        1     | 
        +-----+    | 
        | D |--------------/ 
        +-----+ 

Wir wiederholen den Trick mit einem anderen zufälligen Abschnitt, und dies löst das Diagramm.

Wenn Sie mit mehreren derzeit nicht zugewiesenen Schülern beginnen, fügen Sie einen zusätzlichen Dummy-Abschnitt als Startpunkt hinzu. Das bedeutet natürlich, dass in allen Bereichen freie Stellen vorhanden sein müssen oder das Problem nicht lösbar ist.

Beachten Sie, dass aufgrund der Reihenfolge in der Warteschlange möglicherweise keine Lösung vorhanden ist.