Задача о стабильных паросочетаниях: алгоритм Гейла–Шепли за O(n²)
Алгоритм Гейла–Шепли простыми словами: что такое стабильное паросочетание, почему алгоритм всегда завершается, кому он выгоден, как распределяют интернов. Код на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Задача | Разбить «предлагающих» и «принимающих» на пары так, чтобы ни одна пара не захотела сбежать |
| Блокирующая пара | и не вместе, но оба предпочитают друг друга своим текущим партнёрам |
| Алгоритм | Гейл–Шепли (deferred acceptance): свободные делают предложения по списку, принимающие держат лучшего |
| Сложность | по времени и памяти — линейно от размера входа, ведь сами списки предпочтений занимают |
| Главный подвох | Результат оптимален для тех, кто предлагает, и худший из возможных — для тех, кто принимает |
Задача о стабильных паросочетаниях (stable marriage problem) — редкий случай, когда алгоритм из учебника работает в реальной жизни в масштабах целых стран: им распределяют выпускников медвузов по больницам и школьников по школам. На собеседованиях она встречается реже, чем BFS или динамика, зато отлично проверяет, умеете ли вы доказывать корректность, а не только писать код. Разберём постановку, сам алгоритм, доказательство, реализацию и вопросы, которые обычно задают следом.
Постановка задачи
Есть две группы одинакового размера . Классически это «мужчины» и «женщины», но удобнее думать о кандидатах и компаниях, студентах и вузах, интернах и больницах. Каждый участник упорядочил всех участников другой группы от самого желанного к наименее желанному. Ничьих в списках нет.
Паросочетание — разбиение на пар, где в каждой паре по одному представителю от каждой группы.
Блокирующая пара — кандидат и компания , которые сейчас не вместе, но при этом:
- предпочитает своей текущей компании;
- предпочитает своему текущему кандидату.
Такой паре выгодно бросить назначенных партнёров и договориться напрямую. Стабильное паросочетание — паросочетание без блокирующих пар.
Важно, что стабильность — не то же самое, что «все довольны» или «сумма рангов минимальна». Стабильное паросочетание может оставить кого-то с последним вариантом из списка. Гарантия другая: никто не сможет улучшить своё положение, договорившись с кем-то, кому это тоже выгодно.
Если нужна именно минимальная суммарная стоимость назначения, это другая задача — её решает венгерский алгоритм. А если предпочтений нет и нужно просто максимальное число пар в двудольном графе, хватит алгоритма Куна или потока.
Почему перебор не подходит
Наивный способ — перебрать все паросочетаний и для каждого проверить, нет ли блокирующей пары. Проверка стоит , итого . Для это уже сотни миллионов операций, для — за пределами разумного.
Ещё одна наивная идея — «чинить» паросочетание: нашли блокирующую пару, поженили её, брошенных партнёров соединили между собой, повторили. Это не работает: такие исправления могут ходить по кругу бесконечно. Нужен процесс, в котором есть величина, монотонно меняющаяся в одну сторону.
Неочевидно даже, что стабильное паросочетание вообще существует. Дэвид Гейл и Ллойд Шепли в статье 1962 года доказали это конструктивно — предъявили алгоритм, который всегда его находит.
Алгоритм Гейла–Шепли
Идея — «отложенное принятие» (deferred acceptance). Одна группа делает предложения, другая их принимает, но не окончательно.
- Все свободны. Каждый кандидат держит указатель на начало своего списка.
- Пока есть свободный кандидат , у которого ещё есть кому предлагать:
- делает предложение компании — следующей в своём списке, которой ещё не предлагал;
- если свободна, она принимает предложение «условно»;
- если уже держит кандидата , но ей нравится больше, она меняет на , а снова становится свободным;
- иначе отказывает, и остаётся свободным.
- Когда свободных кандидатов не осталось, текущие пары и есть ответ.
Два свойства держат весь алгоритм:
- Кандидат движется только вниз по своему списку. Каждому он предлагает не больше одного раза, и каждое следующее предложение хуже предыдущего.
- Компания движется только вверх. Однажды получив предложение, она уже никогда не будет свободна, и каждый следующий её партнёр лучше предыдущего.
Отсюда и название: компания не говорит окончательное «да», пока процесс не закончится, — вдруг придёт кто-то получше.
Разбор на примере
Три кандидата и три компании. Списки предпочтений:
| Кандидат | 1-й выбор | 2-й выбор | 3-й выбор |
|---|---|---|---|
| Аня | Гамма | Бета | Альфа |
| Борис | Гамма | Альфа | Бета |
| Вика | Альфа | Гамма | Бета |
| Компания | 1-й выбор | 2-й выбор | 3-й выбор |
|---|---|---|---|
| Альфа | Аня | Борис | Вика |
| Бета | Борис | Вика | Аня |
| Гамма | Вика | Аня | Борис |
Предлагают кандидаты. Свободных обрабатываем по очереди:
- Аня → Гамма: Гамма свободна, принято.
- Борис → Гамма: Гамма держит Аню, а Аня ей нравится больше Бориса. Отказ.
- Вика → Альфа: принято.
- Борис → Альфа: Альфа предпочитает Бориса Вике. Принято, Вика снова в поиске.
- Вика → Гамма: Гамма предпочитает Вику Ане. Принято, Аня снова в поиске.
- Аня → Бета: Бета свободна, принято.
Итог: Аня — Бета, Борис — Альфа, Вика — Гамма. Каждый кандидат получил второй вариант из своего списка.
Проверим стабильность. Аня хотела бы в Гамму, но Гамма держит Вику — свой первый выбор. Борис хотел бы в Гамму, но и Гамма, и сам процесс ему уже отказали. Вика хотела бы в Альфу, но Альфа держит Бориса, которого ставит выше Вики. Блокирующих пар нет.
Теперь запустим тот же алгоритм, но предлагать будут компании:
- Альфа → Аня: принято.
- Бета → Борис: принято.
- Гамма → Вика: принято.
Каждая компания получила первый выбор, а кандидаты — Аня третий вариант, Борис третий, Вика второй. Оба паросочетания стабильны, но выгодны разным сторонам. Это не случайность, а теорема — к ней вернёмся ниже.
Реализация на Python
Участников удобно пронумеровать от до . Тогда предпочтения — это матрицы .
from collections import deque def gale_shapley(proposer_prefs, acceptor_prefs): n = len(proposer_prefs) # rank[a][p] — место предлагающего p в списке принимающего a rank = [[0] * n for _ in range(n)] for a in range(n): for place, p in enumerate(acceptor_prefs[a]): rank[a][p] = place next_choice = [0] * n # кому p сделает следующее предложение partner_of = [-1] * n # partner_of[a] — кого сейчас держит a free = deque(range(n)) while free: p = free.popleft() a = proposer_prefs[p][next_choice[p]] next_choice[p] += 1 current = partner_of[a] if current == -1: partner_of[a] = p elif rank[a][p] < rank[a][current]: partner_of[a] = p free.append(current) # брошенный снова свободен else: free.append(p) # отказ, p попробует следующего match = [-1] * n for a, p in enumerate(partner_of): match[p] = a return match
Ключевая деталь — матрица rank. Вопрос «кто нравится компании больше, или ?» задаётся на каждом предложении. Если отвечать на него через acceptor_prefs[a].index(p), каждое сравнение стоит , и весь алгоритм деградирует до . Предварительно построенная обратная таблица отвечает за .
Индекс next_choice[p] никогда не выйдет за границу списка: как показано ниже, при полных списках каждый кандидат будет принят раньше, чем переберёт всех.
Проверка стабильности
Решение полезно уметь проверять — на собеседовании это хороший способ показать, что вы понимаете определение, а в тестах — поймать ошибку.
def find_blocking_pairs(match, proposer_prefs, acceptor_prefs): n = len(match) partner_of = [-1] * n for p, a in enumerate(match): partner_of[a] = p blocking = [] for p in range(n): for a in proposer_prefs[p]: if a == match[p]: break # дальше идут те, кого p любит меньше prefs = acceptor_prefs[a] if prefs.index(p) < prefs.index(partner_of[a]): blocking.append((p, a)) return blocking men = [[0, 1, 2], [1, 0, 2], [0, 1, 2]] women = [[1, 0, 2], [0, 1, 2], [0, 1, 2]] m = gale_shapley(men, women) print(m, find_blocking_pairs(m, men, women)) # [0, 1, 2] [] w = gale_shapley(women, men) print(w, find_blocking_pairs(w, women, men)) # [1, 0, 2] []
Для каждого кандидата смотрим только тех, кого он ставит выше своей текущей пары: только с ними может образоваться блокирующая пара. Здесь index допустим — проверка вызывается один раз, и в худшем случае для тестов не страшно. Если нужно быстрее, используйте ту же матрицу rank.
Здесь тоже видно, что от выбора предлагающей стороны зависит ответ: при одних и тех же данных получаются два разных стабильных паросочетания.
Почему алгоритм корректен
Он завершается
Каждый кандидат предлагает каждой компании не больше одного раза. Всего возможных предложений , а каждая итерация цикла делает ровно одно. Значит, итераций не больше .
Это и есть та самая монотонная величина, которой не хватало наивному «исправлению»: число сделанных предложений только растёт и ограничено сверху.
Все получают пару
Допустим, кандидат получил отказ от всех компаний. Компания отказывает, только если уже кого-то держит, и после первого предложения навсегда остаётся занятой. Значит, все компаний заняты. Но кандидатов тоже , и среди них свободен — тогда компаний держат не больше кандидата. Противоречие.
Результат стабилен
Пусть в итоге работает в компании , а держит . Предположим, и — блокирующая пара: ставит выше , а ставит выше .
Кандидат идёт по списку сверху вниз, и у него выше . Значит, предлагал раньше, чем , и получил отказ — сразу или позже, когда его вытеснили. Оба варианта означают, что в тот момент держала кого-то лучше . А партнёры компании со временем только улучшаются, поэтому финальный для тоже лучше . Это противоречит предположению.
Доказательство целиком держится на двух монотонностях из описания алгоритма. На собеседовании достаточно сформулировать их и показать, как из них следует отсутствие блокирующей пары.
Кому выгоден результат
Стабильных паросочетаний может быть много, и Гейл–Шепли находит не какое-то, а вполне определённое.
Теорема. Паросочетание, которое строит алгоритм, когда предлагает сторона , оптимально для : каждый её участник получает лучшего партнёра, с которым он вообще бывает в паре хоть в одном стабильном паросочетании. Одновременно оно худшее для другой стороны: каждый принимающий получает худшего из своих «стабильно достижимых» партнёров.
Отсюда два следствия:
- Порядок обработки свободных не важен. Хоть очередь, хоть стек, хоть случайный выбор — результат один и тот же. В реализации выше
dequeможно заменить на список сpop(), ответ не изменится. - Выбор предлагающей стороны — это политическое решение. В нашем примере, когда предлагали кандидаты, все они получили второй вариант. Когда предлагали компании, кандидаты скатились до второго–третьего, а компании получили первый выбор.
Есть и вопрос честности стратегий. Для предлагающей стороны врать о своих предпочтениях невыгодно: указав списки честно, участник ничего не теряет. А вот принимающая сторона в некоторых ситуациях может выиграть, исказив свой список. Поэтому в реальных системах предлагающей стороной обычно делают людей — студентов, интернов, абитуриентов, — а не организации.
Где это используется
- Распределение интернов в США. National Resident Matching Program распределяет выпускников медицинских вузов по ординатурам. Исторически её процедура оказалась вариантом отложенного принятия, а в конце 1990-х её перестроили на алгоритм, где предлагают сами кандидаты (Roth–Peranson), с учётом пар супругов, которые хотят попасть в один город.
- Распределение по школам. Школьные системы Нью-Йорка и Бостона перешли на deferred acceptance в 2000-х.
- Нобелевская премия. В 2012 году Ллойд Шепли и Элвин Рот получили премию по экономике памяти Нобеля за теорию стабильных распределений и её практическое применение. Дэвид Гейл до этого не дожил — он умер в 2008 году.
- Системы распределения ресурсов. Сопоставление запросов и серверов, заданий и исполнителей — везде, где у обеих сторон есть предпочтения и важно, чтобы никто не захотел «договориться в обход».
Обобщения
Больницы и интерны: один ко многим
В реальной задаче у больницы не одно место, а несколько, и не каждый интерн готов идти куда угодно. Алгоритм почти не меняется: больница держит до capacity[h] лучших кандидатов, а при переполнении выгоняет худшего. Чтобы находить худшего быстро, удобна куча.
import heapq from collections import deque def hospitals_residents(resident_prefs, hospital_prefs, capacity): rank = { h: {r: i for i, r in enumerate(prefs)} for h, prefs in hospital_prefs.items() } next_choice = {r: 0 for r in resident_prefs} # max-куча по рангу: на вершине худший из принятых accepted = {h: [] for h in hospital_prefs} free = deque(resident_prefs) while free: r = free.popleft() prefs = resident_prefs[r] if next_choice[r] == len(prefs): continue # список исчерпан — остаётся без места h = prefs[next_choice[r]] next_choice[r] += 1 if r not in rank[h]: free.append(r) # больница его не рассматривает continue heap = accepted[h] heapq.heappush(heap, (-rank[h][r], r)) if len(heap) > capacity[h]: _, worst = heapq.heappop(heap) # вытесняем худшего free.append(worst) return {h: sorted(r for _, r in heap) for h, heap in accepted.items()} residents = { 'r1': ['A', 'B'], 'r2': ['A', 'B'], 'r3': ['A'], 'r4': ['B', 'A'], } hospitals = { 'A': ['r3', 'r1', 'r2', 'r4'], 'B': ['r1', 'r2', 'r4'], } print(hospitals_residents(residents, hospitals, {'A': 2, 'B': 1})) # {'A': ['r1', 'r3'], 'B': ['r2']}
Здесь r4 остаётся без места: больница A заполнена теми, кого ставит выше, а B предпочитает r2. Это нормально — при неполных списках и неравных размерах сторон стабильное паросочетание может быть неполным. Известно, что множество оставшихся без пары одно и то же во всех стабильных паросочетаниях (rural hospitals theorem): никакая хитрость с выбором стабильного решения не поможет пристроить r4.
Неравные группы и неполные списки
Если кандидатов больше, чем компаний, или кто-то вычеркнул неприемлемые варианты, достаточно двух правок, как в коде выше: кандидат с исчерпанным списком выбывает из очереди, а компания отказывает тем, кого нет в её списке. Стабильность при этом понимается с учётом «быть одному лучше, чем с неприемлемым партнёром».
Задача о соседях по комнате
Если группа одна (каждый может оказаться в паре с каждым, как при расселении по двухместным комнатам), стабильного паросочетания может не существовать вовсе. Классический пример — четыре человека, где трое по кругу предпочитают друг друга, а четвёртый у всех последний: кто бы ни оказался с четвёртым, у него найдётся блокирующая пара. Проверить существование и найти решение можно за алгоритмом Ирвинга, но он заметно сложнее Гейла–Шепли.
Ничьи в предпочтениях
Если участникам разрешено ставить варианты на одно место, задача про «слабую» стабильность по-прежнему решается: ничьи разбиваются произвольно, и Гейл–Шепли работает. А вот поиск стабильного паросочетания максимального размера при ничьих и неполных списках уже NP-трудная задача.
Сложность
| Ресурс | Оценка | Комментарий |
|---|---|---|
| Время | Не больше предложений, каждое за благодаря rank | |
| Память | Матрица rank; сами входные списки занимают столько же |
Асимптотику не улучшить в общем случае: чтобы просто прочитать все предпочтения, нужно времени. Подробнее о том, как читать такие оценки, — в статье про нотацию O большое.
Число предложений в худшем случае действительно порядка , но на случайных предпочтениях их в среднем около : большинство кандидатов пристраиваются в одну из первых компаний своего списка.
Типичные ошибки
list.indexвнутри цикла. Самая частая: код выглядит правильно, но работает за . Стройте таблицу рангов заранее.- Забыть вернуть брошенного в очередь. Компания поменяла партнёра, а вытесненный кандидат исчез из
free— он так и останется без пары. - Начинать список заново. Вытесненный кандидат продолжает с того места, где остановился, а не с начала списка. Компании, которые ему уже отказали, не передумают — ведь их партнёры только улучшаются.
- Путать направления индексов.
match[p](компания кандидата) иpartner_of[a](кандидат компании) легко перепутать, особенно при одинаковом . Называйте массивы по смыслу и проверяйте ответ черезfind_blocking_pairs. - Считать, что результат «честный» для обеих сторон. Он стабилен, но систематически выгоден предлагающим. На вопрос «кто должен предлагать?» правильный ответ — «та сторона, чьи интересы приоритетнее».
- Путать стабильность с оптимальностью по сумме. Если интервьюер просит минимизировать суммарную стоимость, нужен венгерский алгоритм, а не Гейл–Шепли.
Как это спрашивают на собеседовании
Прямую задачу «реализуйте Гейла–Шепли» дают нечасто — чаще в компаниях с сильным алгоритмическим уклоном или в виде задачи на дизайн: «распределите кандидатов по командам с учётом предпочтений обеих сторон». Типичный сценарий разговора:
- Уточнить определение стабильности и показать, что простая жадность («каждому — его первый выбор») ломается на конфликтах.
- Описать алгоритм отложенного принятия и написать код за , проговорив, зачем нужна таблица рангов.
- Доказать завершимость (не больше предложений) и стабильность (две монотонности).
- Ответить на follow-up: кому выгоден результат, что будет при нескольких местах у компании, при неполных списках, при одной группе вместо двух.
Если на последнем шаге вы спокойно говорите «результат оптимален для предлагающих и пессимален для принимающих, а при одной группе решения может не быть», — это ровно то, что отличает знание алгоритма от заученного кода.
Итог
- Стабильное паросочетание — такое, где нет пары, которой выгодно сбежать вдвоём. Оно всегда существует, если групп две.
- Алгоритм Гейла–Шепли: свободные предлагают по своему списку, принимающие держат лучшего и меняют его на ещё лучшего. Не больше предложений, время .
- Корректность следует из двух монотонностей: предлагающие идут вниз по списку, принимающие только улучшают партнёра.
- Результат не зависит от порядка обработки, но зависит от того, кто предлагает: этой стороне достаётся лучший стабильный вариант, другой — худший.
- Тот же алгоритм с небольшими правками работает для «один ко многим» и неполных списков; для одной группы нужен уже другой алгоритм, и решения может не быть.