Алгоритм назначения курса

Question

Мне нужно назначить n человек на m курсов, где каждый человек указал свое первое и второе предпочтение, и в каждом курсе максимальное количество человек. Каждый человек может посещать только один курс. Алгоритм должен найти одно решение, где

1. максимальное количество людей, которым назначен один курс, является максимальным
2. максимальное количество людей, которым предоставлен первый выбор, максимально (с учетом 1, который имеет более высокий приоритет).

Я догадался, что это не редкая проблема, но поиск не дал ничего слишком полезного, поэтому я решил свернуть свой. Это то, что я дошел до сих пор:

1. Для курсов, в которых предпочтения меньше, чем у максимального числа посещающих людей, назначьте всех этих людей на курс
2. Для других курсов: включите в курс случайных людей, которые выбрали этот курс в качестве первого, пока курс не будет заполнен
3. Для курсов, у которых меньше вторые предпочтения, чем у свободных мест, назначьте всех этих лиц на курс
4. Для других курсов: включите в курс случайных людей, которые выбрали этот курс в качестве второго, пока курс не будет заполнен
5. Для каждого человека без курса: При первом (затем втором) предпочтении обратите внимание на человека, который выбрал другой курс, где места еще свободны (если найдено более одного, возьмите тот, который выбрал курс с наибольшим свободные места), переместите этого человека на второй выбор и назначьте пропавшего без вести

Я все еще не думаю, что этот алгоритм найдет оптимальное решение проблемы из-за последнего шага. Есть идеи, как сделать это лучше? Есть ли другой алгоритм, который решает эту проблему?

Answer 1

Поместите всех на курс первого выбора, если это возможно.

Если есть кто-то, кто не получил его, поставьте его на второй выбор.

Теперь у нас могут быть те, кто не получил ни одного из своих выборов. («проигравшие».)

Найдите человека, который получил свой первый выбор курса, который также является вторым выбором «неудачника». Этот парень будет переназначен на его второй выбор, в то время как "неудачник" заберет свой слот. Если такого человека нет, то ваша проблема неразрешима.

Обратите внимание, что это максимизирует количество людей, которые получили свой первый выбор:

Если у вас есть второй выбор, то это означает либо:

• кто-то уже получил ваш первый выбор в качестве своего первого выбора
• кто-то другой получил ваш первый выбор как его второй выбор, но только потому, что его первый выбор был выбран как чей-то второй выбор, и чей первый выбор был заполнен студентами первого выбора.

(Возможно, последним битом немного сложно следовать, поэтому вот переписывание:)

Для человека X с первым выбором A и вторым выбором B:

Если X получил выбор B, то:

• Y взял ячейку X в A, а Y выбрал A.
• Y взял слот X в A, и второй выбор Y - A. Первый выбор Y - C, но все слоты C заполнены другими студентами, чей первый выбор также C.

Answer 2

Это похоже на проблему стабильного брака .

Дано n мужчинам и n женщинам, где каждый человек оценил всех членов противоположный пол с уникальным номером от 1 до n в порядке предпочтение, жениться на мужчинах и женщинах вместе так, что нет двух люди противоположного пола, которые оба лучше друг друга, чем их текущие партнеры. Если таких нет люди, все браки "Стабильный".

Обновление:

Принимая во внимание комментарии @bdares и тот факт, что курсы имеют ограниченную емкость, было бы трудно назвать проблему стабильным соответствием.

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

Answer 3

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

Answer 4

Первая проблема может быть смоделирована как проблема согласования двухчастичного максимального количества элементов. Вторая проблема может быть смоделирована как взвешенная проблема двойного соответствия (также известная как проблема присваивания).