Решение

Алгоритм Гейла-Шепли в высшей степени надежен по отношению к вариациям задачи устойчивого паросочетания. Итак, если вы имеете дело с новой разновид- ностью задачи и не можете найти контрпример для устойчивости, часто бывает полезно проверить, действительно ли прямая адаптация алгоритма Гейла-Шепли породит устойчивое паросочетание.

Перед нами один из таких случаев. Мы покажем, что устойчивое паросочета- ние существует всегда, даже в более общей модели с запрещенными парами, и для этого мы адаптируем алгоритм Гейла-Шепли. Мы рассмотрим, почему исходный алгоритм Гейла-Шепли не может использоваться напрямую. Конечно, сложность связана с тем, что алгоритму Гейла-Шепли ничего не известно о запретных парах и условие цикла Пока:

Пока существует свободный мужчина т, который еще не успел сделать предложение каждой женщине

не сработает; т не должен делать предложение женщине 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, но тогда она не была бы одинока — противоречие. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения