Задача об устойчивом паросочетании — различия между версиями
(→Анализ полученного алгоритмом паросочетания) |
м (rollbackEdits.php mass rollback) |
||
(не показано 46 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
+ | {{Определение | ||
+ | |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='''Устойчивое паросочетание''' (англ. ''stable matching'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар. | ||
Строка 4: | Строка 11: | ||
{{Задача | {{Задача | ||
|definition= | |definition= | ||
− | Найти полное устойчивое паросочетание между элементами двух множеств размера <tex> | + | Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>n</tex>, имеющими свои предпочтения.}} |
== Основная задача == | == Основная задача == | ||
Строка 18: | Строка 25: | ||
Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] | Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] | ||
в МЖ. | в МЖ. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Алгоритм Гейла-Шепли == | == Алгоритм Гейла-Шепли == | ||
− | Решение задачи было описано в 1962 году математиками Девидом Гейлом ( | + | Решение задачи было описано в <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>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи). | <ref>https://ru.wikipedia.org/wiki/American_Mathematical_Monthly American Mathematical Monthly 69, 9-14, 1962.</ref>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи). | ||
Строка 37: | Строка 37: | ||
# Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают. | # Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают. | ||
# Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть». | # Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть». | ||
− | # Шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент. | + | # Шаги <tex>1</tex>-<tex>4</tex> повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент. |
=== Описание в псевдокоде === | === Описание в псевдокоде === | ||
− | + | <font color="green">// Изначально все мужчины не женаты и все женщины незамужние.</font> | |
− | + | '''while''' существует свободный мужчина | |
− | + | M = некоторый свободный мужчина | |
− | + | w = первая женщина из текущего списка M | |
− | + | '''if''' w свободна | |
− | + | помечаем M и w помолвленными | |
− | + | '''else if''' w предпочитает M своему текущему жениху M' | |
− | + | помечаем M и w помолвленными | |
− | + | вычёркиваем w из списка предпочтений M' | |
+ | помечаем M' свободным | ||
+ | '''else''' | ||
+ | вычёркиваем w из списка предпочтений M | ||
+ | |||
+ | Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>, где <tex>n</tex> равно размеру каждого из данных множеств. | ||
=== Доказательство корректности === | === Доказательство корректности === | ||
Строка 55: | Строка 60: | ||
{{Утверждение | {{Утверждение | ||
|id=observation1 | |id=observation1 | ||
− | |about=Наблюдение 1 | + | |about=Наблюдение <tex>1</tex> |
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии. | |statement=Мужчины делают предложения женщинам в порядке убывания симпатии. | ||
}} | }} | ||
Строка 61: | Строка 66: | ||
{{Утверждение | {{Утверждение | ||
|id=observation2 | |id=observation2 | ||
− | |about=Наблюдение 2 | + | |about=Наблюдение <tex>2</tex> |
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату). | |statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату). | ||
}} | }} | ||
Строка 69: | Строка 74: | ||
{{Лемма | {{Лемма | ||
|id=lemma1 | |id=lemma1 | ||
− | |about=Лемма 1 | + | |about=Лемма <tex>1</tex> |
|statement= | |statement= | ||
Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла <tex>\mathrm{\mathbf{while}}</tex>. | Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла <tex>\mathrm{\mathbf{while}}</tex>. | ||
Строка 80: | Строка 85: | ||
{{Лемма | {{Лемма | ||
|id=lemma2 | |id=lemma2 | ||
− | |about=Лемма 2 | + | |about=Лемма <tex>2</tex> |
|statement= | |statement= | ||
Все мужчины и женщины будут заняты. | Все мужчины и женщины будут заняты. | ||
|proof= | |proof= | ||
− | Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда некоторая женщина (<tex>a</tex>) | + | Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда и некоторая женщина (<tex>a</tex>) незамужняя. По [[#observation2|наблюдению <tex>2</tex>]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты. |
− | Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина | + | Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию. |
}} | }} | ||
− | |||
{{Лемма | {{Лемма | ||
|id=lemma3 | |id=lemma3 | ||
− | |about=Лемма 3 | + | |about=Лемма <tex>3</tex> |
|statement= | |statement= | ||
После завершения алгоритма не будет неустойчивых пар. | После завершения алгоритма не будет неустойчивых пар. | ||
|proof= | |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>\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>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>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> — устойчивая пара. |
}} | }} | ||
− | |||
− | |||
− | |||
− | |||
=== Анализ полученного алгоритмом паросочетания === | === Анализ полученного алгоритмом паросочетания === | ||
Строка 116: | Строка 116: | ||
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения). | Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения). | ||
|proof= | |proof= | ||
+ | Докажем от противного, что для каждого мужчины не существует устойчивого паросочетания, в котором его супругой была бы более желанная для него женщина. | ||
+ | |||
+ | Предположим, для мужчины <tex>A</tex> это свойство не выполняется. Так как он оказался женат не на лучшей из кандидатур, то существует женщина <tex>a</tex>, которая предпочла ему другого, более привлекательного мужчину <tex>B</tex>, при этом женщина <tex>a</tex> для мужчины <tex>B</tex> стоит на первом месте в его текущем списке. Предположим, существует устойчивое паросочетание, содержащее <tex>\langle A, a\rangle</tex>. По определению, в устойчивом паросочетании нет неустойчивых пар. Пара <tex>\langle B, a\rangle</tex> станет неустойчивой, если <tex>B</tex> будет предпочитать <tex>a</tex> своей супруге. Значит, <tex>B</tex> женат на ком-то, кто лучше, чем <tex>a</tex>. Но такое невозможно, так как <tex>a</tex> стоит для него на первом месте. Таким образом, если женщина <tex>a</tex> вычёркивается из списка предпочтений мужчины <tex>A</tex>, то любое паросочетание, содержащее <tex>\langle A, a\rangle</tex>, неустойчиво. | ||
+ | |||
}} | }} | ||
Строка 126: | Строка 130: | ||
Пусть <tex>A</tex>, <tex>B</tex> — мужчины; <tex>c</tex>, <tex>d</tex> — женщины; <tex>A</tex> женат на <tex>d</tex>, <tex>B</tex> женат на <tex>c</tex>. | Пусть <tex>A</tex>, <tex>B</tex> — мужчины; <tex>c</tex>, <tex>d</tex> — женщины; <tex>A</tex> женат на <tex>d</tex>, <tex>B</tex> женат на <tex>c</tex>. | ||
− | Предположим, | + | Предположим, <tex>\langle A, c\rangle</tex> — стабильная пара в паросочетании <tex>S'</tex>, найденном алгоритмом Гейла-Шепли, но <tex>A</tex> не самый худший выбор для <tex>c</tex>. Тогда существует стабильная пара в паросочетании <tex>S</tex>, в которой <tex>c</tex> замужем за <tex>B</tex>, который менее привлекателен, чем <tex>A</tex>. Тогда пусть мужем <tex>d</tex> будет <tex>A</tex> в паросочетании <tex>S</tex>. Получается <tex>A</tex> считает <tex>c</tex> более привлекательной, чем <tex>d</tex>. Соответственно <tex>\langle A, c\rangle</tex> {{---}} нестабильная пара в паросочетании <tex>S</tex>. То есть для <tex>c</tex> есть мужчина, который более привлекателен, чем её муж. |
}} | }} | ||
− | |||
− | |||
== Обобщения задачи == | == Обобщения задачи == | ||
− | Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть) | + | Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть) <ref>https://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате Задача о соседях по комнате</ref>. |
− | |||
− | Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются | + | Случай же, когда у нас есть <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> — квота). И добавлением фиктивного университета (поступление в который означает, что кандидату придется попробовать поступить через год). | Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин — множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> — квота). И добавлением фиктивного университета (поступление в который означает, что кандидату придется попробовать поступить через год). | ||
Строка 148: | Строка 149: | ||
* Распределение донорских органов по нуждающимся в них людям | * Распределение донорских органов по нуждающимся в них людям | ||
− | Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году. | + | Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в <tex>2012</tex> году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в <tex>2008</tex> году. |
== Примечания == | == Примечания == | ||
Строка 161: | Строка 162: | ||
* [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://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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)] | * [http://ge.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)] | ||
− | + | * [http://kek.ksu.ru/eos/Lerner/KnuthRu.pdf Устойчивость супружеских пар и другие комбинаторные задачи - Казанский государственный университет] | |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о паросочетании]] | [[Категория: Задача о паросочетании]] |
Текущая версия на 19:05, 4 сентября 2022
Определение: |
Пара
| называется неустойчивой (англ. unstable pair), если:
Определение: |
Устойчивое паросочетание (англ. stable matching) — паросочетание без неустойчивых пар. |
Задача: |
Найти полное устойчивое паросочетание между элементами двух множеств размера | , имеющими свои предпочтения.
Основная задача
Есть
мужчин и женщин. Они обладают следующими особенностями:- Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны);
- Каждый мужчина может отсортировать женщин от наименее привлекательной к наиболее привлекательной, причем его предпочтения не меняются (у каждого мужчины своя функция оценки);
- Каждая женщина может отсортировать мужчин от наименее привлекательного к наиболее привлекательному, причем её предпочтения не меняются (у каждой женщины своя функция оценки).
Очевидным образом по такому определению строится полный двудольный граф (левая доля — мужчины, правая — женщины), назовем его МЖ.
Рассмотрим некоторое паросочетание в МЖ.
Алгоритм Гейла-Шепли
Решение задачи было описано в [1]. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
году математиками Девидом Гейлом (Университет Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical MonthlyИнтуитивное описание
- Мужчины делают предложение наиболее предпочитаемой женщине.
- Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ).
- Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
- Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
- Шаги - повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Описание в псевдокоде
// Изначально все мужчины не женаты и все женщины незамужние. while существует свободный мужчина M = некоторый свободный мужчина w = первая женщина из текущего списка M if w свободна помечаем M и w помолвленными else if w предпочитает M своему текущему жениху M' помечаем M и w помолвленными вычёркиваем w из списка предпочтений M' помечаем M' свободным else вычёркиваем w из списка предпочтений M
Время работы алгоритма —
, так как количество итераций цикла не превосходит , где равно размеру каждого из данных множеств.Доказательство корректности
Утверждение (Наблюдение | ):
Мужчины делают предложения женщинам в порядке убывания симпатии. |
Утверждение (Наблюдение | ):
Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату). |
Для начала покажем, что алгоритм завершит свою работу.
Лемма (Лемма | ):
Алгоритм завершается после максимум итераций цикла . |
Доказательство: |
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более | предложений.
Теперь покажем, что по завершении алгоритма задача будет решена.
Лемма (Лемма | ):
Все мужчины и женщины будут заняты. |
Доказательство: |
Предположим, что некоторый мужчина (наблюдению , не получала предложений. Но сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты. Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию. ) не женат по завершении алгоритма. Тогда и некоторая женщина ( ) незамужняя. По |
Лемма (Лемма | ):
После завершения алгоритма не будет неустойчивых пар. |
Доказательство: |
Предположим (где , — мужчины; , — женщины; женат на , женат на ) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Возможны два случая:
|
Анализ полученного алгоритмом паросочетания
Алгоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом.
Лемма (man-optimality): |
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения). |
Доказательство: |
Докажем от противного, что для каждого мужчины не существует устойчивого паросочетания, в котором его супругой была бы более желанная для него женщина. Предположим, для мужчины это свойство не выполняется. Так как он оказался женат не на лучшей из кандидатур, то существует женщина , которая предпочла ему другого, более привлекательного мужчину , при этом женщина для мужчины стоит на первом месте в его текущем списке. Предположим, существует устойчивое паросочетание, содержащее . По определению, в устойчивом паросочетании нет неустойчивых пар. Пара станет неустойчивой, если будет предпочитать своей супруге. Значит, женат на ком-то, кто лучше, чем . Но такое невозможно, так как стоит для него на первом месте. Таким образом, если женщина вычёркивается из списка предпочтений мужчины , то любое паросочетание, содержащее , неустойчиво. |
Лемма (woman-pessimality): |
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин. |
Доказательство: |
Пусть Предположим, , — мужчины; , — женщины; женат на , женат на . — стабильная пара в паросочетании , найденном алгоритмом Гейла-Шепли, но не самый худший выбор для . Тогда существует стабильная пара в паросочетании , в которой замужем за , который менее привлекателен, чем . Тогда пусть мужем будет в паросочетании . Получается считает более привлекательной, чем . Соответственно — нестабильная пара в паросочетании . То есть для есть мужчина, который более привлекателен, чем её муж. |
Обобщения задачи
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть) [2].
Случай же, когда у нас есть
мужчин и женщин ( ) легко сводится к описанной выше задаче. Рассмотрим ( аналогично). Добавим фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, то это будет означать, что она на самом деле осталась без пары.Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин — множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением
"филиалов" для каждого университета ( — квота). И добавлением фиктивного университета (поступление в который означает, что кандидату придется попробовать поступить через год).Применения в реальной жизни
Задача о нахождении устойчивого паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:
- Распределение студентов по коллеждам в США
- Распределение интернов по больницам
- Распределение донорских органов по нуждающимся в них людям
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в
году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в году.Примечания
- ↑ https://ru.wikipedia.org/wiki/American_Mathematical_Monthly American Mathematical Monthly 69, 9-14, 1962.
- ↑ https://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате Задача о соседях по комнате