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

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

♦ Изначально ни один из участников не имеет пары. Допустим, неженатый муж- чина 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

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