Изменения

== Паросочетание в двудольном графеОсновная задача == Есть 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(неформально это означает потенциальную возможность измены)

|iddefinition=Устойчивое паросочетание (stable matching) - паросочетание без неустойчивых пар.}} Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений. == Агоритм Гейла-Шепли == Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи). === Интуитивное описание ===matching_def|definition# мужчины делают предложение наиболее предпочитаемой женщине;# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент. === Описание в псевдокоде ===   Изначально все мужчины и все женщины не женаты (не замужем) '''Паросочетаниеwhile''' Существует m <tex>M- некоторый свободный мужчина, не делавший предложения всем женщинам w </tex> в двудольном графе — произвольное множество ребер двудольного графа- первая женщина из списка m, такое что никакие два ребра которой m еще не имеют общей вершины.}}делал предложения '''if''' w свободна{{Определение помечаем m и w помолвленными|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''else if'покрытыми''w предпочитает m своему "текущему" жениху m' помечаем m и w помолвленными, а неинцидентные — m' - свободным '''свободнымиelse'''. w отказывает m === Доказательство корректности === {{Утверждение|id=observation1|about=Наблюдение 1|statement=Мужчины делают предложения женщинам в порядке убывания симпатии}}  {{ОпределениеУтверждение|id=observation2|definitionabout=Наблюдение 2|statement= '''Чередующаяся цепь''' — путь в двудольном графеКак только женщина была помолвлена, она не может стать непомолвленной, для любых двух соседних ребер которого верноона может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)}} Для начала покажем, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое неталгоритм завершит свою работу.}} {{ОпределениеЛемма|id=lemma1|definitionabout=Лемма 1|statement= Алгоритм завершается после максимум n^2 итераций цикла '''Дополняющая цепьwhile''' — чередующаяся цепь|proof= На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.}} Теперь покажем, у которой оба конца свободнычто по завершении алгоритма задача будет решена. {{Лемма|id=lemma2|about=Лемма 2|statement= Все мужчины и женщины будут заняты.|proof= 1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.  2. Тогда некоторая женщина, Антонина не замужем  3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения  4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат  5. Получаем противоречие 6.Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано}}

{{ТеоремаЛемма|id=theorem1lemma3|about=Лемма 3

Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи Нет неустойчивых пар.

<tex 1. Предположим A-b (A, B - мужчины; a, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли  2. Рассмотрим два случая:  2.1. A не делал предложения b  =>\Rightarrow</texA находит a более привлекательной, чем b  =>A-b - устойчивая пара  2.2. A делал предложение b  => b отказала A (сразу или на одной из последующих итераций)  => b находит B более привлекательным, чем A  => A-b - устойчивая пара}}  === Асимптотика алгоритма ===

Пусть в двудольном графе Покажем, как реализовать внутреннюю часть цикла while за <tex>GO(1)</tex> с максимальным паросочетанием предпроцессингом не более, чем за <tex>MO(n^2)</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть тогда итоговая ассимптотика очевидно будет <tex>MO(n^2)</tex> не являлось максимальным. Противоречие.

Будем поддерживать два одномерных массива: 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 может быть реализован следующим образом:{{Определение|definition '''while''' not free.isEmpty() m = free.pop() w = mp[m][count[m]++] m' = husband[w] '''if'Увеличивающая цепь''m' — чередующаяся цепь, у которой оба конца свободны.}}== 0{{Определение husband[w] = m|definition wife[m] = w '''else if'Уменьшающая цепь''wp[w][m] < wp[w][m' — чередующаяся цепь, у которой оба конца покрыты.}}] husband[w] = m{{Определение wife[m] = w|definition wife[m'] = 0 free.push(m') ''Сбалансированная цепь'else'' — чередующаяся цепь' free.push(m) === Анализ полученного алгоритмом паросочетания === Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, у которой один конец свободенкакими свойствами обладает решение, а другой покрытнайденное алгоритмом. {{Лемма|id=lemma4|about=Лемма 4 (man-optimality)|statement= Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).}}

Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>{{Лемма|Mid=lemma5|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам about=Лемма 5 (одному из <tex>M</tex> и одному из <tex>M'</tex> woman-pessimality), т.е. имеет степень не более двух. В таком графе каждая компонента связности |statement= Из всех возможных решений алгоритмом Гейла- путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>Шепли будет найдено решение, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепьюнаихудшее для женщин.

Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-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> фиктивных мужчин, Расин Вкоторые являются наименее привлекательными с точки зрения каждой из женщин. ВТогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем. — Дискретная математика Также интересна задача о выборе учебного заведения: Графывместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, матроидыподающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, алгоритмыкоторое университет может принять. '''ISBN 978Задача очевидно сводится к основной добавлением <tex>(K-51)</tex> "филиалов" для каждого университета (<tex>K</tex> -8114квота). И добавлением фиктивного увниерситета (поступление в который означает, что кандидату придется попробовать поступить через год). == Применения в реальной жизни == Задача о нахождении устойчивого паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:* Распределение студентов по коллеждам в США* Распределение интернов по больницам* Распределение донорских органов по нуждающимся в них людям Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году. == Ссылки == * [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-1068-2''matching.pdf Stable matching, Prinston lecture'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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]