Изменения

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

Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях

11 764 байта убрано, 23:44, 17 ноября 2014
Товарищ Georgeee видимо торопился перед экзаменом и переписал конспект "Задача об устойчивом паросочетании" поверх существующего.
== Основная задача Паросочетание в двудольном графе== Есть N мужчин и N женщин. Они обладают следующими особенностями:# Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны)# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной", причем его предпочтения не меняются (у каждого мужчины своя функция оценки)# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются (у каждой женщины своя функция оценки)  Очевидным образом по такому определению строится полный двудольный граф (левая доля - мужчины, правая - женщины), назовем его МЖ. Рассмотрим некоторое [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B8_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D1%8F%D1%8E%D1%89%D0%B8%D1%85_%D1%86%D0%B5%D0%BF%D1%8F%D1%85#matching_def паросочетание] в МЖ. Пара A-b называется неустойчивой (unstable pair), если:# В паросочетании есть пары A-a и B-b (A женат на a, B женат на b)# A считает b привлекательней, чем a# b считает A привлекательней, чем B(неформально это означает потенциальную возможность измены)
{{Определение
|id=matching_def|definition=Устойчивое паросочетание (stable matching) - паросочетание без неустойчивых пар'''Паросочетание''' <tex>M</tex> в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}{{Определение|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}}{{ОпределениеЗадача заключается |definition= '''Чередующаяся цепь''' — путь в нахождении полного устойчивого паросочетания по данным спискам предпочтенийдвудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}{{Определение|definition== Агоритм Гейла-Шепли =='''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}}
Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) == Теорема о максимальном паросочетании и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical 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=Лемма 1theorem1
|statement=
Алгоритм завершается после максимум n^2 итераций цикла '''while'''Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.}}<tex>\Rightarrow</tex>
Теперь покажемПусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, что по завершении алгоритма задача будет решенамы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
{{Лемма|id=lemma2|about=Лемма 2|statement= Все мужчины и женщины будут заняты.|proof= 1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.<tex>\Leftarrow</tex>
2. Тогда некоторая женщина, Антонина не замужемВ доказательстве используются несколько новых понятий:{{Определение 3. По [[#observation2|наблюдению 2]]definition= '''Увеличивающая цепь''' — чередующаяся цепь, Антонине никто не делал предложения  4. Но Ян сделал предложения всем женщинам, ту которой оба конца свободны.к. он остался не женат  5. Получаем противоречие 6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано}}  {{ЛеммаОпределение|iddefinition=lemma3'''Уменьшающая цепь''' — чередующаяся цепь, у которой оба конца покрыты.}}|about=Лемма 3{{Определение|statementdefinition= Нет неустойчивых пар.|proof= 1. Предположим A-b (A'''Сбалансированная цепь''' — чередующаяся цепь, B - мужчины; aу которой один конец свободен, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли  2. Рассмотрим два случая:  2.1. A не делал предложения bа другой покрыт}}
=Рассмотрим паросочетание <tex> A находит a более привлекательнойM</tex> в графе <tex>G</tex> и предположим, чем b  =что <tex>M</tex> A-b не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - устойчивая пара  2другое паросочетание и <tex>|M'|>|M|</tex>.2Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. A делал предложение b  =В графе <tex> b отказала A H</tex> каждая вершина инцидентна не более чем двум ребрам (сразу одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или на одной цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из последующих итераций)  =<tex>M'</tex> b находит B более привлекательнымсодержится больше, чем A  =ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> A-b - устойчивая параэтот путь является увеличивающей (дополняющей) цепью.
}}
 === Асимптотика алгоритма =Литература== Покажем, как реализовать внутреннюю часть цикла while за <tex>O(1)</tex> с предпроцессингом не более, чем за <tex>O(n^2)</tex>, тогда итоговая ассимптотика очевидно будет <tex>O(n^2)</tex>* Асанов М. Все мужчины и женщины нумеруются числами от 1 до NО. Будем поддерживать два одномерных массива: wife, husband (wife[m] - id жены мужчины m или 0, если мужчина не женат; husband[w] - id мужа женщины w или 0, если женщина не замужем) Также нам нужен список свободных мужчин free, для этого можно использовать и, например, очередь или стек. Предпочтения каждого мужчины будем хранить списком, в котором женщины отсортированы от самой привлекательной к наименее привлекательной (такой список можно построить из любого другого представления не более чем за <tex>O(n^2)</tex>, при необходимости сортировать можно сортировкой подсчетом)Баранский В. Соответствующий двумерный массив обозначим за mp (men preference)А. Для навигации по спискам предпочтений нам понадобится массив count, count[m] - количество женщин, которым делал предложение мужчина m. Для женщин создадим массив wp (women preference), который аналогичен инверсии аналогичной структуры для мужчинРасин В. В частности, wp[w][m] - индекс мужчины m в списке предпочтений женщины w. Очевидно— Дискретная математика: Графы, такой массив может быть построен за время не болеематроиды, чем <tex>O(n^2)</tex>. Тогда цикл while может быть реализован следующим образом:  '''while''' not free.isEmpty() m = freeалгоритмы.pop() w = mp[m][count[m]++] m' = husband[w] '''if''' m' == 0 husband[w] = m wife[m] = w '''else if''' wp[w][m] < wp[w][m'] husband[w] = m wife[m] = w wife[m'] = 0 free.push(m') '''else''' free.push(m) === Анализ полученного алгоритмом паросочетания === Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом. {{Лемма|id=lemma4|about=Лемма 4 (man-optimality)|statement= Из всех возможных решений алгоритмом ГейлаISBN 978-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).}} {{Лемма|id=lemma5|about=Лемма 5 (woman-pessimality)|statement= Из всех возможных решений алгоритмом Гейла8114-Шепли будет найдено решение, наихудшее для женщин.}} Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable1068-matching.pdf (с.5) == Обобщения задачи == Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. [http://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате Задача о соседях по комнате]) Случай же, когда у нас есть <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 году. == Ссылки == * [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf Stable matching, Prinston lecture2'''s presentation]* [http://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem]* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BC%D0%B0%D1%80%D1%8C%D1%8F%D0%B6%D0%B5 Задача о марьяже]* [http://ge.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)] 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
Dmitriy D.
223
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/40869»

Навигация