Изменения

Перейти к: навигация, поиск

Задача об устойчивом паросочетании

188 байт добавлено, 12:15, 20 марта 2018
Доказательство корректности
{{Определение
|definition =
Пара <tex>\langle A, b\rangle</tex> называется '''неустойчивой''' (англ. ''unstable pair''), если:
# В паросочетании есть пары <tex>\langle A, a\rangle</tex> и <tex>\langle B, b\rangle</tex> (<tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>);
# <tex>A</tex> предпочитает <tex>b</tex> элементу <tex>a</tex>;
# <tex>b</tex> предпочитает <tex>A</tex> элементу <tex>B</tex>.
}}
{{Определение
|definition='''Устойчивое паросочетание''' (англ. ''stable matching'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар.
{{Задача
|definition=
Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>Nn</tex>, имеющими свои предпочтения.}}
== Основная задача ==
Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]]
в МЖ.
{{Определение
|definition =
Пара <tex>\langle A, b\rangle</tex> называется '''неустойчивой''' (англ. ''unstable pair''), если:
# В паросочетании есть пары <tex>\langle A, a\rangle</tex> и <tex>\langle B, b\rangle</tex> (<tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>)
# <tex>A</tex> считает <tex>b</tex> ''привлекательней'', чем <tex>a</tex>
# <tex>b</tex> считает <tex>A</tex> ''привлекательней'', чем <tex>B</tex>
}}
== Алгоритм Гейла-Шепли ==
Решение задачи было описано в <tex>1962</tex> году математиками Девидом Гейлом (Университета Университет Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly
<ref>https://ru.wikipedia.org/wiki/American_Mathematical_Monthly American Mathematical Monthly 69, 9-14, 1962.</ref>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
# Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
# Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
# Шаги <tex>1</tex>-<tex>4 </tex> повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
=== Описание в псевдокоде ===
<font color="green">// Изначально все мужчины не женаты и все женщины незамужние.</font> '''while''' Существует m <- существует свободный мужчина M = некоторый свободный мужчина, не делавший предложения всем женщинам w <- = первая женщина из текущего списка m, которой m ещё не делал предложенияM '''if''' w свободна помечаем m M и w помолвленными '''else if''' w предпочитает m M своему "текущему" жениху mM' помечаем m M и w помолвленными, m вычёркиваем w из списка предпочтений M' помечаем M' свободным '''else''' вычёркиваем w отказывает mиз списка предпочтений M
Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>, где <tex>n</tex> равно размеру каждого из данных множеств.
=== Доказательство корректности ===
Все мужчины и женщины будут заняты.
|proof=
Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда и некоторая женщина (<tex>a</tex>) незамужняя. По [[#observation2|наблюдению <tex>2</tex>]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты.
Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
|proof=
Предположим <tex>\langle A, b\rangle</tex> (где <tex>A</tex>, <tex>B</tex> — мужчины; <tex>a</tex>, <tex>b</tex> — женщины; <tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Возможны два случая:
# <tex>A</tex> не делал предложения предложение <tex>b</tex>. Значит, <tex>A</tex> находит <tex>a</tex> более привлекательной, чем <tex>b</tex>. Но чтобы рассматриваемая пара была неустойчивой, необходимо, чтобы <tex>b</tex> для <tex>A</tex> была более привлекательна, чем <tex>a</tex>. Следовательно, <tex>\langle A, b\rangle</tex> — устойчивая пара.
# <tex>A</tex> делал предложение <tex>b</tex>. Тогда был такой момент, когда <tex>b</tex> отказала <tex>A</tex>, значит, <tex>b</tex> находит <tex>B</tex> более привлекательным, чем <tex>A</tex>. Снова получается, что <tex>\langle A, b\rangle</tex> — устойчивая пара.
* Распределение донорских органов по нуждающимся в них людям
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в <tex>2012 </tex> году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в <tex>2008 </tex> году.
== Примечания ==
Анонимный участник

Навигация