19
правок
Изменения
Новый конспект
== Основная задача ==
Есть N мужчин и N женщин. Они обладают следующими особенностями:
# Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны)
# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной", причем его предпочтения не меняются
# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются
Очевидным образом по такому определению строится полный двудольный граф (левая доля - мужчины, правая - женщины), назовем его МЖ.
Рассмотрим некоторое паросочетание в МЖ. Пара Ab называется неустойчивой, если:
# В паросочетании есть пары Aa и Bb (A женат на a, B женат на b)
# A считает b привлекательней, чем a
# b считает A привлекательней, чем B
(неформально это означает потенциальную возможность измены)
{{Определение
|definition=Устойчивое паросочетание - паросочетание без неустойчивых пар.
}}
Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.
== Агоритм Гейла-Шепли ==
Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American texematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
=== Интуитивное описание ===
# мужчины делают предложение наиболее предпочитаемой женщине;
# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
=== Описание в псевдокоде ===
Изначально все мужчины и все женщины не женаты (не замужем)
'''while''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам
w <- первая женщина из списка m, которой m еще не делал предложения
'''if''' w свободна
помечаем m и w помолвленными
'''else if''' w предпочитает m своему "текущему" жениху m'
помечаем m и w помолвленными, m' - свободным
'''else'''
w отказывает m
=== Доказательство корректности ===
{{Утверждение
|id=observation1
|about=Наблюдение 1
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии
}}
{{Утверждение
|id=observation2
|about=Наблюдение 2
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)
}}
Для начала покажем, что алгоритм завершит свою работу.
{{Лемма
|id=lemma1
|about=Лемма 1
|statement=
Алгоритм завершается после максимум n^2 итераций цикла '''while'''
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
}}
Теперь покажем, что по завершении алгоритма задача будет решена.
{{Лемма
|id=lemma2
|about=Лемма 2
|statement=
Все мужчины и женщины будут заняты.
|proof=
1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.
2. Тогда некоторая женщина, Антонина не замужем
3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения
4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат
5. Получаем противоречие
6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано
}}
{{Лемма
|id=lemma3
|about=Лемма 3
|statement=
Нет неустойчивых пар.
|proof=
1. Предположим A-b (A, B - мужчины; a, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли
2. Рассмотрим два случая:
2.1. A не делал предложения b
=> A находит a более привлекательной, чем b
=> A-b - устойчивая пара
2.2. A делал предложение b
=> b отказала A (сразу или на одной из последующих итераций)
=> b находит B более привлекательным, чем A
=> A-b - устойчивая пара
}}
=== Ассимптотика алгоритма ===
Не представляет проблемы реализовать внутренний цикл while за <tex>O(1)</tex> (с предварительным предпроцессингом не более, чем за <tex>O(n^2)</tex>). Таким образом, итоговая асимптотика составляет O(n^2).
=== Анализ полученного алгоритмом паросочетания ===
Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом.
{{Лемма
|id=lemma4
|about=Лемма 4 (man-optimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
}}
{{Лемма
|id=lemma5
|about=Лемма 5 (woman-pessimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
}}
Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5)
== Обобщения задачи ==
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. Задача о соседях по комнате)
Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.
Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидна сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> - квота). И добавлением фиктивного увниерситета (поступление в который означает, что кандидату придется попробовать поступить через год).
== Применения в реальной жизни ==
Задача о нахождении устойчивого паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:
* Распределение студентов по коллеждам в США
* Распределение интернов по больницам
* Распределение донорских органов по нуждающимся в них людям
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году.
Есть N мужчин и N женщин. Они обладают следующими особенностями:
# Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны)
# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной", причем его предпочтения не меняются
# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются
Очевидным образом по такому определению строится полный двудольный граф (левая доля - мужчины, правая - женщины), назовем его МЖ.
Рассмотрим некоторое паросочетание в МЖ. Пара Ab называется неустойчивой, если:
# В паросочетании есть пары Aa и Bb (A женат на a, B женат на b)
# A считает b привлекательней, чем a
# b считает A привлекательней, чем B
(неформально это означает потенциальную возможность измены)
{{Определение
|definition=Устойчивое паросочетание - паросочетание без неустойчивых пар.
}}
Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.
== Агоритм Гейла-Шепли ==
Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American texematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
=== Интуитивное описание ===
# мужчины делают предложение наиболее предпочитаемой женщине;
# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
=== Описание в псевдокоде ===
Изначально все мужчины и все женщины не женаты (не замужем)
'''while''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам
w <- первая женщина из списка m, которой m еще не делал предложения
'''if''' w свободна
помечаем m и w помолвленными
'''else if''' w предпочитает m своему "текущему" жениху m'
помечаем m и w помолвленными, m' - свободным
'''else'''
w отказывает m
=== Доказательство корректности ===
{{Утверждение
|id=observation1
|about=Наблюдение 1
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии
}}
{{Утверждение
|id=observation2
|about=Наблюдение 2
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)
}}
Для начала покажем, что алгоритм завершит свою работу.
{{Лемма
|id=lemma1
|about=Лемма 1
|statement=
Алгоритм завершается после максимум n^2 итераций цикла '''while'''
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
}}
Теперь покажем, что по завершении алгоритма задача будет решена.
{{Лемма
|id=lemma2
|about=Лемма 2
|statement=
Все мужчины и женщины будут заняты.
|proof=
1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.
2. Тогда некоторая женщина, Антонина не замужем
3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения
4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат
5. Получаем противоречие
6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано
}}
{{Лемма
|id=lemma3
|about=Лемма 3
|statement=
Нет неустойчивых пар.
|proof=
1. Предположим A-b (A, B - мужчины; a, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли
2. Рассмотрим два случая:
2.1. A не делал предложения b
=> A находит a более привлекательной, чем b
=> A-b - устойчивая пара
2.2. A делал предложение b
=> b отказала A (сразу или на одной из последующих итераций)
=> b находит B более привлекательным, чем A
=> A-b - устойчивая пара
}}
=== Ассимптотика алгоритма ===
Не представляет проблемы реализовать внутренний цикл while за <tex>O(1)</tex> (с предварительным предпроцессингом не более, чем за <tex>O(n^2)</tex>). Таким образом, итоговая асимптотика составляет O(n^2).
=== Анализ полученного алгоритмом паросочетания ===
Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом.
{{Лемма
|id=lemma4
|about=Лемма 4 (man-optimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
}}
{{Лемма
|id=lemma5
|about=Лемма 5 (woman-pessimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
}}
Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5)
== Обобщения задачи ==
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. Задача о соседях по комнате)
Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.
Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидна сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> - квота). И добавлением фиктивного увниерситета (поступление в который означает, что кандидату придется попробовать поступить через год).
== Применения в реальной жизни ==
Задача о нахождении устойчивого паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:
* Распределение студентов по коллеждам в США
* Распределение интернов по больницам
* Распределение донорских органов по нуждающимся в них людям
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году.
