Проектирование алгоритма

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

Рассмотрим некоторые базовые идеи, заложенные в основу алгоритма.

♦ Изначально ни один из участников не имеет пары. Допустим, неженатый муж- чина m выбирает женщину w с наивысшей оценкой в его списке предпочтений и делает ей предложение. Можно ли немедленно объявить, что пара (m, w) войдет в итоговое устойчивое паросочетание? Не обязательно; в какой-то мо- мент в будущем мужчина m’, более предпочтительный с точки зрения женщины w, может сделать ей предложение. С другой стороны, для w будет рискованно немедленно отказывать m; она может не получить ни одного предложения от участника с более высокой оценкой в ее списке предпочтений. Таким образом, возникает естественная идея перевести пару (m, w) в промежуточное состояние помолвки.

♦ Допустим, в текущем состоянии некоторые мужчины и женщины свободны (то есть не помолвлены), а другие участвуют в помолвке. Следующий шаг мо- жет выглядеть примерно так: произвольный свободный мужчина m выбирает женщину с наивысшей оценкой w, которой он еще не делал предложение, и об- ращается к ней с предложением. Если женщина w тоже свободна, то m и w всту- пают в состояние помолвки. В противном случае w уже помолвлена с другим мужчиной m’; тогда она определяет, кто из m и m’ имеет более высокую оценку в ее списке предпочтений; этот мужчина вступает в помолвку с w, а другой ста- новится свободным.

♦ Наконец, алгоритм в какой-то момент должен определить, что ни одного сво- бодного участника не осталось; тогда все помолвки объявляются окончатель- ными и возвращается полученное идеальное паросочетание.

Ниже приводится конкретное описание алгоритма Гейла-Шепли; его проме- жуточное состояние изображено на рис. 1.2.

В начальном состоянии все m e M и w e W свободны.

Пока существует свободный мужчина m, который еще не успел сделать предложение каждой женщине

Выбрать такого мужчину m.

Выбрать w - женщину с наивысшей оценкой в списке предпочтений m, которой m еще не делал предложения.

Если w свободна, то

пара (m, w) вступает в состояние помолвки.

Иначе w в настоящее время помолвлена с m’.

Если w предпочитает m’ мужчине m, то m остается свободным.

Иначе w предпочитает m мужчине m'

пара (m, w) вступает в состояние помолвки. m` становится свободным.

Конец Если Конец Если Конец Пока

Вернуть множество S помолвленных пар

Рис. 1.2. Промежуточное состояние алгоритма Гейла-Шепли: свободный мужчина m делает предложение женщине w


Хотя формулировка алгоритма Гейла-Шепли выглядит достаточно просто, на первый взгляд не очевидно, что он возвращает устойчивое паросочетание — или хотя бы идеальное паросочетание. Сейчас мы докажем устойчивость результата через серию промежуточных фактов.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Проектирование алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Этапы социокультурного проектирования
  12. ЛЕКЦИЯ 18 3.2.2.2. Методы социокультурного проектирования
  13. Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕДАГОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ