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

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

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

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

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

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

Ответы

Ответ 1

По возможности, поместите все в свой первый курс.

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Обновление:

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

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

Ответ 3

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