Классическая формулировка: даны два равномощных непересекающихся множества, или, проще говоря, N мужчин и N женщин. Для каждого мужчины известен рейтинг женщин в порядке убывания предпочтительности в качестве невесты, для каждой женщины известен рейтинг женихов. Требуется переженить их (то есть соединить элементы множеств) так, чтобы не нашлось такой пары М и Ж, что они не женаты, но являются друг для друга взаимно более предпочтительными партнерами, чем те, кого они имеют в качесве супругов сейчас. Тогда женитьба называется стабильной.

Решение: решается итеративно путем эвристического перебора. Пока есть хоть один свободный мужчина, просматриваем его рейтинг невест, начиная с наиболее предпочтительной. Если невеста свободна, женим их, помечаем как занятых. Если невеста уже не свободна, то смотрим в ее рейтинг. Если ее нынешний жених для нее предпочтительнее, чем наш кандидат - что ж, не получилось, предлагаем руку и сердце следующей в списке даме. Если же наш кандидат лучше для нее, то предыдущий жених становится свободным, а нашего кандидата женим. Начинаем новую итерацию.
Такое решение будет male-optimal. Чтобы найти female-optimal решение, просматриваем сначала свободных женщин.

Псевдокод:

function stableMatching {
   Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman
       if w is free
           (m, w) become engaged
       else some pair (m', w) already exists
           if w prefers m to m'
               (m, w) become engaged
               m' becomes free
           else
               (m', w) remain engaged
    }
}

Почему это важно? К этой задаче можно свести многие другие. Помните задачу про зонтики в Перми? Это тоже задача о женитьбе. Кстати, Саня придумал для нее решение, но никто ему не поверил.
Задачу Ants c NEERC 2007 помните? Тот же подход - сначала соединяем колонии и деревья как попало. Потом берем пару отрезков - если пересекаются, меняем дорожки местами. Процесс стабилизируется очень быстро, задача таким методом хорошо решается, Accepted выдается. Вообще любую задачу на установление однозначного соответсвия можно свести к Stable Marriage Problem, кроме тех случаев, когда нужно найти соотвествие с минимальной ценой. Тогда это будет Minimal Cost Assignment Problem и решаться будет Венгерским алгоритмом, который я пока так и не вкурил.

Отредактировано Ikari (2009-01-08 10:52:26)