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

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

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

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

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

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

10
задан neo 10 June 2011 в 15:04
поделиться