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

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

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

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

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

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

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

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