|
|
| Строка 1: |
Строка 1: |
| − | == Основная задача == | + | == Паросочетание в двудольном графе== |
| − | | |
| − | Есть 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
| |
| − | (неформально это означает потенциальную возможность измены)
| |
| | | | |
| | {{Определение | | {{Определение |
| − | |definition=Устойчивое паросочетание (stable matching) - паросочетание без неустойчивых пар. | + | |id=matching_def |
| − | }} | + | |definition= '''Паросочетание''' <tex>M</tex> в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}} |
| − | | + | {{Определение |
| − | Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.
| + | |definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}} |
| − | | + | {{Определение |
| − | == Агоритм Гейла-Шепли == | + | |definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} |
| | + | {{Определение |
| | + | |definition= '''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}} |
| | | | |
| − | Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
| + | == Теорема о максимальном паросочетании и дополняющих цепях == |
| | | | |
| − | === Интуитивное описание ===
| + | {{Теорема |
| − | | + | |id=theorem1 |
| − | # мужчины делают предложение наиболее предпочитаемой женщине;
| |
| − | # каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
| |
| − | # мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
| |
| − | # если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
| |
| − | # шаги 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= | | |statement= |
| − | Алгоритм завершается после максимум n^2 итераций цикла '''while'''
| + | Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи. |
| | |proof= | | |proof= |
| − | На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
| + | <tex>\Rightarrow</tex> |
| − | }}
| |
| | | | |
| − | Теперь покажем, что по завершении алгоритма задача будет решена.
| + | Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие. |
| | | | |
| − | {{Лемма
| + | <tex>\Leftarrow</tex> |
| − | |id=lemma2
| |
| − | |about=Лемма 2
| |
| − | |statement=
| |
| − | Все мужчины и женщины будут заняты.
| |
| − | |proof=
| |
| − | 1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.
| |
| | | | |
| − | 2. Тогда некоторая женщина, Антонина не замужем
| + | В доказательстве используются несколько новых понятий: |
| − | | + | {{Определение |
| − | 3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения
| + | |definition= '''Увеличивающая цепь''' — чередующаяся цепь, у которой оба конца свободны.}} |
| − | | + | {{Определение |
| − | 4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат
| + | |definition= '''Уменьшающая цепь''' — чередующаяся цепь, у которой оба конца покрыты.}} |
| − | | + | {{Определение |
| − | 5. Получаем противоречие
| + | |definition= '''Сбалансированная цепь''' — чередующаяся цепь, у которой один конец свободен, а другой покрыт}} |
| − |
| |
| − | 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
| + | Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью. |
| − | | |
| − | => A-b - устойчивая пара
| |
| − | | |
| − | 2.2. A делал предложение b
| |
| − | | |
| − | => b отказала A (сразу или на одной из последующих итераций)
| |
| − | | |
| − | => b находит B более привлекательным, чем A
| |
| − | | |
| − | => A-b - устойчивая пара
| |
| | }} | | }} |
| | | | |
| − | | + | ==Литература== |
| − | === Асимптотика алгоритма === | + | * Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' |
| − | | |
| − | Покажем, как реализовать внутреннюю часть цикла 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=
| |
| − | Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
| |
| − | }}
| |
| − | | |
| − | {{Лемма
| |
| − | |id=lemma5
| |
| − | |about=Лемма 5 (woman-pessimality)
| |
| − | |statement=
| |
| − | Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
| |
| − | }}
| |
| − | | |
| − | Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу 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> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.
| |
| − | | |
| − | Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением <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 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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]
| |
| − | | |
| | | | |
| | | | |
| | [[Категория: Алгоритмы и структуры данных]] | | [[Категория: Алгоритмы и структуры данных]] |
| | [[Категория: Задача о паросочетании]] | | [[Категория: Задача о паросочетании]] |
