693
правки
Изменения
→Алгоритм Гейла-Шепли
== Алгоритм Гейла-Шепли ==
Решение задачи было описано в <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>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
{{Утверждение
|id=observation1
|about=Наблюдение <tex>1</tex>
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии.
}}
{{Утверждение
|id=observation2
|about=Наблюдение <tex>2</tex>
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату).
}}
{{Лемма
|id=lemma1
|about=Лемма <tex>1</tex>
|statement=
Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла <tex>\mathrm{\mathbf{while}}</tex>.
{{Лемма
|id=lemma2
|about=Лемма <tex>2</tex>
|statement=
Все мужчины и женщины будут заняты.
{{Лемма
|id=lemma3
|about=Лемма <tex>3</tex>
|statement=
После завершения алгоритма не будет неустойчивых пар.
