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

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

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

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

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

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

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