El problema de las "Listas de espera"

Question

Un número de estudiantes quiere entrar en secciones para una clase, algunos ya están registrados en una sección pero quieren cambiar la sección, para que todos entren en la lista de espera. Un estudiante puede ingresar a una nueva sección solo si alguien abandona esa sección. Ningún alumno está dispuesto a dejar una sección en la que ya se encuentra, a menos que pueda estar seguro de ingresar en la sección que está esperando. La lista de espera para cada sección se entrega primero en primer lugar.

Obtenga tantos estudiantes en las secciones que desee como pueda.

El problema establecido puede pasar rápidamente a un escenario de bloqueo. Mi pregunta es; ¿hay soluciones conocidas para este problema?

---

Una solución trivial sería tomar cada sección a su vez y forzar el primer estudiante de la lista de espera en la sección a continuación, compruebe si alguien terminan abandonando cuando las cosas se resuelven (O (n) o más en el número de sección). Esto funcionaría para algunos casos, pero creo que podría haber mejores opciones que impliquen forzar a más de un estudiante a una sección (O (n) o más en el recuento de estudiantes) y/u operar en más de una sección a la vez (O (malo) :-)

Answer 1

Bueno, esto solo se reduce a encontrar ciclos en el gráfico dirigido de las clases ¿no? cada enlace es un estudiante que quiere ir de un nodo a otro, y cada vez que encuentras un ciclo, lo borras, porque esos estudiantes pueden resolver sus necesidades entre ellos. Has terminado cuando estás fuera de ciclos.

Answer 2

Esto es en realidad un problema de gráfico. Puede pensar en cada una de estas dependencias de lista de espera como bordes en un gráfico dirigido. Si este gráfico tiene un ciclo, entonces tiene una de las situaciones que describió. Una vez que haya identificado un ciclo, puede elegir cualquier punto para "romper" el ciclo "sobreabasteciendo" una de las clases, y sabrá que las cosas se resolverán correctamente porque había un ciclo en el gráfico.

Answer 3

Ok, vamos a intentarlo. Tenemos 8 estudiantes (1..8) y 4 secciones. Cada estudiante está en una sección y cada sección tiene espacio para 2 estudiantes. La mayoría de los estudiantes quieren cambiar pero no todos.

En la tabla a continuación, vemos a los estudiantes su sección actual, su sección requerida y la posición en la cola (si la hay).

+------+-----+-----+-----+ 
| 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 | 
+------+-----+-----+-----+ 

Podemos presentar esta información en un gráfico:

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

tratamos de encontrar una sección con una vacante, pero no encontramos ninguna. Entonces, como todas las secciones están llenas, necesitamos un truco sucio. Así que vamos a tomar una sección aleatoria con una cola no vacía. En este caso, la sección A y supongamos que tiene una posición extra. Esto significa que el estudiante 5 puede ingresar a la sección A, dejando una vacante en la sección C que toma el estudiante 7. Esto deja una vacante en la sección D que toma el estudiante 2. Ahora tenemos una vacante en la sección A. Pero supusimos que esa sección A tiene una posición extra, por lo que podemos eliminar esta suposición y obtener un gráfico más simple.

Si la ruta nunca volvió a la sección A, deshaga los movimientos y marque A como punto de inicio no válido. Vuelve a intentar con otra sección. Si no quedan secciones válidas, hemos terminado.

En este momento tenemos la siguiente situación:

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

Repetimos el truco con otra sección al azar, y esto resuelve el gráfico.

Si comienza con varios estudiantes actualmente no asignados, agrega una sección ficticia adicional como punto de partida. Por supuesto, esto significa que debe haber vacantes en cualquier sección o que el problema no se puede resolver.

Tenga en cuenta que debido al orden en la cola, es posible que no haya solución.