Проектирование алгоритма
Рассмотрим некоторые базовые идеи, заложенные в основу алгоритма.
♦ Изначально ни один из участников не имеет пары. Допустим, неженатый муж- чина 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
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Этапы социокультурного проектирования
- ЛЕКЦИЯ 18 3.2.2.2. Методы социокультурного проектирования
- Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕДАГОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ