Решение
Перед нами один из таких случаев. Мы покажем, что устойчивое паросочета- ние существует всегда, даже в более общей модели с запрещенными парами, и для этого мы адаптируем алгоритм Гейла-Шепли. Мы рассмотрим, почему исходный алгоритм Гейла-Шепли не может использоваться напрямую. Конечно, сложность связана с тем, что алгоритму Гейла-Шепли ничего не известно о запретных парах и условие цикла Пока:
Пока существует свободный мужчина т, который еще не успел сделать предложение каждой женщине
не сработает; т не должен делать предложение женщине w, для которой пара (m, w) является запрещенной.
Рассмотрим модификацию алгоритма Гейла-Шепли, в которую будет внесено только одно изменение: мы изменим условие цикла Пока и приведем его к виду:
Пока существует свободный мужчина т, который еще не успел сделать предложение каждой женщине w, для которой (т, w) ⅜ F
А теперь приведем полный алгоритм:
В начальном состоянии все т е м и w e W свободны.
Пока существует свободный мужчина т, который еще не успел сделать предложение каждой женщине w, для которой (т, w) ⅜ F Выбрать такого мужчину т.
Выбрать w - женщину с наивысшей оценкой в списке предпочтений т, которой т еще не делал предложения.
Если w свободна, то
пара (т, w) вступает в состояние помолвки.
Иначе w в настоящее время помолвлена с т'.
Если w предпочитает т' мужчине т, то т остается свободным.
Иначе w предпочитает т мужчине т'
пара (т, w) вступает в состояние помолвки.
т' становится свободным.Конец Если Конец Если Конец Пока
Вернуть множество S помолвленных пар
Сейчас мы докажем, что этот алгоритм дает устойчивое паросочетание в соот- ветствии с новым определением устойчивости.
Прежде всего, утверждения (1.1), (1.2) и (1.3) из текста остаются истинными (в частности, завершение алгоритма потребует не более n2 итераций). Кроме того, нам не нужно доказывать, что полученное паросочетание S идеально (на самом деле оно может таковым не быть). Также следует обратить внимание на дополни- тельные факты. Если m — мужчина, который не входит в пару из S, то m должен был сделать предложение всем не запрещенным женщинам; и если w — женщина, которая не входит в пару из S, то из этого следует, что ни один мужчина не делал ей предложение.
Наконец, осталось доказать последнее утверждение:
(1.9) В отношении возвращаемого паросочетания S не существует неустойчи- вости.
Доказательство. Наше общее определение неустойчивости состоит из четырех частей, таким образом, нам нужно убедиться в том, что не встречается ни одно из четырех нежелательных явлений.
Для начала предположим, что существует неустойчивость типа (1), состоящая из пар (m, w) и (m', w') в S и обладающая тем свойством, что (m, w') ⅜ F, m пред- почитает w' женщине w, а w' предпочитает m мужчине m'. Из этого следует, что m должен был сделать предложение w'; получается, что w' ему отказала, а значит, она предпочитает своего окончательного партнера m — противоречие.
Далее предположим, что существует неустойчивость типа (1), состоящая из пары (m, w) S и мужчины m' и обладающая тем свойством, что m' не входит ни
в одну пару, (m', w) ⅜ F и w предпочитает m' мужчине m. Из этого следует, что m' должен был сделать предложение w и получить отказ; и снова это означает, что w предпочитает своего окончательного партнера m' — противоречие.
Если существует неустойчивость типа (3), состоящая из пары (m, w) S и жен-
щины w' и обладающая тем свойством, что w' не входит ни в одну пару, (m, w') ⅜ F и m предпочитает w'женщине w. В этом случае ни один мужчина вообще не делал предложения w'; в частности, m не делал предложения w', поэтому он должен пред- почитать w женщине w' — противоречие.
Наконец, предположим, что существует неустойчивость типа (4), состоящая из мужчины m и женщины w, ни один из которых не является частью ни одной пары в паросочетании, так что (m, w') ⅜ F. Но чтобы m не имел пары, он должен был сделать предложение каждой женщине, брак с которой ему не запрещен; в част- ности, он должен был сделать предложение w, но тогда она не была бы одинока — противоречие. ■
Еще по теме Решение:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения