«Проблема списков ожидания»

Question

Некоторые студенты хотят попасть в разделы для класса, некоторые уже записаны в один раздел, но хотят изменить раздел, поэтому все они попадают в списки ожидания. Студент может попасть в новый раздел, только если кто-то пропустит этот раздел. Никто из студентов не хочет оставлять раздел, в котором они уже находятся, если только он не может быть уверен, что попал в раздел, который их ждет. Список ожидания для каждого раздела «первым пришел - первым обслужен».

Соберите как можно больше студентов в желаемые секции.

Заявленная проблема может быстро перейти в сценарий тупиковой ситуации. Мой вопрос есть известные решения этой проблемы?

---

Одним из тривиальных решений было бы взять каждый раздел по очереди и заставить первого ученика из списка ожидания войти в раздел, а затем проверить, выпадает ли кто-то из учеников, когда что-то решается (O (n) или более по числу раздел). В некоторых случаях это будет работать, но я думаю, что могут быть более удачные варианты, включающие принудительное включение более одного студента в секцию (O (n) или более на счетчике студентов) и / или одновременное использование нескольких секций (O (плохо): -)

Answer 1

Хорошо, давайте попробуем. У нас 8 студентов (1..8) и 4 секции. Каждый студент находится в секции, и в каждой секции есть место для 2 учеников. Большинство студентов хотят переключиться, но не все.

В таблице ниже мы видим учащихся, их текущий раздел, их обязательный раздел и позицию в очереди (если есть).

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

Мы можем представить эту информацию в виде графика:

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

Мы пытаемся найти раздел с вакансией, но мы не находим ни одного. Так как все разделы заполнены, нам нужен подвох. Итак, давайте возьмем случайный раздел с непустой очередью. В этом случае раздел А и предположим, что он имеет дополнительную позицию. Это означает, что студент 5 может войти в раздел A, оставив вакансию в разделе C, которую занимает студент 7. Это оставляет вакансию в разделе D, которую занимает студент 2. Теперь у нас есть вакансия в разделе A. Но мы предполагали, что раздел А имеет дополнительную позицию, поэтому мы можем убрать это предположение и получить более простой график.

Если путь никогда не возвращался в секцию A, отмените ходы и отметьте A как недопустимую начальную точку. Повторите попытку с другим разделом. Если действительных разделов не осталось, мы закончили.

Сейчас у нас следующая ситуация:

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

Мы повторяем трюк с другим случайным сечением, и это решает график.

Если вы начинаете с нескольких учеников, которые в настоящее время не назначены, вы добавляете дополнительный фиктивный раздел в качестве отправной точки. Конечно, это означает, что в любых разделах должны быть вакансии, или проблема не решаема.

Обратите внимание, что из-за порядка в очереди может оказаться, что решения не существует.

Answer 2

Ну, это просто сводится к нахождению циклов в ориентированном графе классов, верно? каждая ссылка - это учащийся, который хочет перейти с одного узла на другой, и каждый раз, когда вы находите цикл, вы удаляете его, потому что эти учащиеся могут решить свои потребности друг с другом. Вы закончили, когда у вас закончились циклы.

Answer 3

Это на самом деле проблема с графиком. Вы можете думать о каждой из этих зависимостей списка ожидания как о ребрах на ориентированном графе. Если у этого графика есть цикл, то у вас есть одна из ситуаций, которые вы описали. После того как вы определили цикл, вы можете выбрать любую точку, чтобы «разорвать» цикл, «переполнив» один из классов, и вы будете знать, что все устроится правильно, потому что в графике был цикл.