Задача о стабильных паросочетаниях: алгоритм Гейла–Шепли за O(n²)

Алгоритм Гейла–Шепли простыми словами: что такое стабильное паросочетание, почему алгоритм всегда завершается, кому он выгоден, как распределяют интернов. Код на Python.

12 мин чтенияалгоритмы · графы · жадные алгоритмы · python

Коротко

ВопросОтвет
ЗадачаРазбить nn «предлагающих» и nn «принимающих» на пары так, чтобы ни одна пара не захотела сбежать
Блокирующая параpp и aa не вместе, но оба предпочитают друг друга своим текущим партнёрам
АлгоритмГейл–Шепли (deferred acceptance): свободные делают предложения по списку, принимающие держат лучшего
СложностьO(n2)O(n^2) по времени и памяти — линейно от размера входа, ведь сами списки предпочтений занимают n2n^2
Главный подвохРезультат оптимален для тех, кто предлагает, и худший из возможных — для тех, кто принимает

Задача о стабильных паросочетаниях (stable marriage problem) — редкий случай, когда алгоритм из учебника работает в реальной жизни в масштабах целых стран: им распределяют выпускников медвузов по больницам и школьников по школам. На собеседованиях она встречается реже, чем BFS или динамика, зато отлично проверяет, умеете ли вы доказывать корректность, а не только писать код. Разберём постановку, сам алгоритм, доказательство, реализацию и вопросы, которые обычно задают следом.

Постановка задачи

Есть две группы одинакового размера nn. Классически это «мужчины» и «женщины», но удобнее думать о кандидатах и компаниях, студентах и вузах, интернах и больницах. Каждый участник упорядочил всех участников другой группы от самого желанного к наименее желанному. Ничьих в списках нет.

Паросочетание — разбиение на nn пар, где в каждой паре по одному представителю от каждой группы.

Блокирующая пара — кандидат pp и компания aa, которые сейчас не вместе, но при этом:

  • pp предпочитает aa своей текущей компании;
  • aa предпочитает pp своему текущему кандидату.

Такой паре выгодно бросить назначенных партнёров и договориться напрямую. Стабильное паросочетание — паросочетание без блокирующих пар.

Важно, что стабильность — не то же самое, что «все довольны» или «сумма рангов минимальна». Стабильное паросочетание может оставить кого-то с последним вариантом из списка. Гарантия другая: никто не сможет улучшить своё положение, договорившись с кем-то, кому это тоже выгодно.

Если нужна именно минимальная суммарная стоимость назначения, это другая задача — её решает венгерский алгоритм. А если предпочтений нет и нужно просто максимальное число пар в двудольном графе, хватит алгоритма Куна или потока.

Почему перебор не подходит

Наивный способ — перебрать все n!n! паросочетаний и для каждого проверить, нет ли блокирующей пары. Проверка стоит O(n2)O(n^2), итого O(n!⋅n2)O(n! \cdot n^2). Для n=10n = 10 это уже сотни миллионов операций, для n=20n = 20 — за пределами разумного.

Ещё одна наивная идея — «чинить» паросочетание: нашли блокирующую пару, поженили её, брошенных партнёров соединили между собой, повторили. Это не работает: такие исправления могут ходить по кругу бесконечно. Нужен процесс, в котором есть величина, монотонно меняющаяся в одну сторону.

Неочевидно даже, что стабильное паросочетание вообще существует. Дэвид Гейл и Ллойд Шепли в статье 1962 года доказали это конструктивно — предъявили алгоритм, который всегда его находит.

Алгоритм Гейла–Шепли

Идея — «отложенное принятие» (deferred acceptance). Одна группа делает предложения, другая их принимает, но не окончательно.

  1. Все свободны. Каждый кандидат держит указатель на начало своего списка.
  2. Пока есть свободный кандидат pp, у которого ещё есть кому предлагать:
    • pp делает предложение компании aa — следующей в своём списке, которой ещё не предлагал;
    • если aa свободна, она принимает предложение «условно»;
    • если aa уже держит кандидата p′p', но pp ей нравится больше, она меняет p′p' на pp, а p′p' снова становится свободным;
    • иначе aa отказывает, и pp остаётся свободным.
  3. Когда свободных кандидатов не осталось, текущие пары и есть ответ.

Два свойства держат весь алгоритм:

  • Кандидат движется только вниз по своему списку. Каждому он предлагает не больше одного раза, и каждое следующее предложение хуже предыдущего.
  • Компания движется только вверх. Однажды получив предложение, она уже никогда не будет свободна, и каждый следующий её партнёр лучше предыдущего.

Отсюда и название: компания не говорит окончательное «да», пока процесс не закончится, — вдруг придёт кто-то получше.

Разбор на примере

Три кандидата и три компании. Списки предпочтений:

Кандидат1-й выбор2-й выбор3-й выбор
АняГаммаБетаАльфа
БорисГаммаАльфаБета
ВикаАльфаГаммаБета
Компания1-й выбор2-й выбор3-й выбор
АльфаАняБорисВика
БетаБорисВикаАня
ГаммаВикаАняБорис

Предлагают кандидаты. Свободных обрабатываем по очереди:

  1. Аня → Гамма: Гамма свободна, принято.
  2. Борис → Гамма: Гамма держит Аню, а Аня ей нравится больше Бориса. Отказ.
  3. Вика → Альфа: принято.
  4. Борис → Альфа: Альфа предпочитает Бориса Вике. Принято, Вика снова в поиске.
  5. Вика → Гамма: Гамма предпочитает Вику Ане. Принято, Аня снова в поиске.
  6. Аня → Бета: Бета свободна, принято.

Итог: Аня — Бета, Борис — Альфа, Вика — Гамма. Каждый кандидат получил второй вариант из своего списка.

Проверим стабильность. Аня хотела бы в Гамму, но Гамма держит Вику — свой первый выбор. Борис хотел бы в Гамму, но и Гамма, и сам процесс ему уже отказали. Вика хотела бы в Альфу, но Альфа держит Бориса, которого ставит выше Вики. Блокирующих пар нет.

Теперь запустим тот же алгоритм, но предлагать будут компании:

  1. Альфа → Аня: принято.
  2. Бета → Борис: принято.
  3. Гамма → Вика: принято.

Каждая компания получила первый выбор, а кандидаты — Аня третий вариант, Борис третий, Вика второй. Оба паросочетания стабильны, но выгодны разным сторонам. Это не случайность, а теорема — к ней вернёмся ниже.

Реализация на Python

Участников удобно пронумеровать от 00 до n−1n - 1. Тогда предпочтения — это матрицы n×nn \times n.

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. Вопрос «кто нравится компании больше, pp или p′p'?» задаётся на каждом предложении. Если отвечать на него через acceptor_prefs[a].index(p), каждое сравнение стоит O(n)O(n), и весь алгоритм деградирует до O(n3)O(n^3). Предварительно построенная обратная таблица отвечает за O(1)O(1).

Индекс 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 допустим — проверка вызывается один раз, и O(n3)O(n^3) в худшем случае для тестов не страшно. Если нужно быстрее, используйте ту же матрицу rank.

Здесь тоже видно, что от выбора предлагающей стороны зависит ответ: при одних и тех же данных получаются два разных стабильных паросочетания.

Почему алгоритм корректен

Он завершается

Каждый кандидат предлагает каждой компании не больше одного раза. Всего возможных предложений n2n^2, а каждая итерация цикла делает ровно одно. Значит, итераций не больше n2n^2.

Это и есть та самая монотонная величина, которой не хватало наивному «исправлению»: число сделанных предложений только растёт и ограничено сверху.

Все получают пару

Допустим, кандидат pp получил отказ от всех nn компаний. Компания отказывает, только если уже кого-то держит, и после первого предложения навсегда остаётся занятой. Значит, все nn компаний заняты. Но кандидатов тоже nn, и pp среди них свободен — тогда nn компаний держат не больше n−1n - 1 кандидата. Противоречие.

Результат стабилен

Пусть в итоге pp работает в компании aa, а a′a' держит p′p'. Предположим, pp и a′a' — блокирующая пара: pp ставит a′a' выше aa, а a′a' ставит pp выше p′p'.

Кандидат идёт по списку сверху вниз, и a′a' у него выше aa. Значит, pp предлагал a′a' раньше, чем aa, и получил отказ — сразу или позже, когда его вытеснили. Оба варианта означают, что a′a' в тот момент держала кого-то лучше pp. А партнёры компании со временем только улучшаются, поэтому финальный p′p' для a′a' тоже лучше pp. Это противоречит предположению.

Доказательство целиком держится на двух монотонностях из описания алгоритма. На собеседовании достаточно сформулировать их и показать, как из них следует отсутствие блокирующей пары.

Кому выгоден результат

Стабильных паросочетаний может быть много, и Гейл–Шепли находит не какое-то, а вполне определённое.

Теорема. Паросочетание, которое строит алгоритм, когда предлагает сторона PP, оптимально для PP: каждый её участник получает лучшего партнёра, с которым он вообще бывает в паре хоть в одном стабильном паросочетании. Одновременно оно худшее для другой стороны: каждый принимающий получает худшего из своих «стабильно достижимых» партнёров.

Отсюда два следствия:

  • Порядок обработки свободных не важен. Хоть очередь, хоть стек, хоть случайный выбор — результат один и тот же. В реализации выше 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.

Неравные группы и неполные списки

Если кандидатов больше, чем компаний, или кто-то вычеркнул неприемлемые варианты, достаточно двух правок, как в коде выше: кандидат с исчерпанным списком выбывает из очереди, а компания отказывает тем, кого нет в её списке. Стабильность при этом понимается с учётом «быть одному лучше, чем с неприемлемым партнёром».

Задача о соседях по комнате

Если группа одна (каждый может оказаться в паре с каждым, как при расселении по двухместным комнатам), стабильного паросочетания может не существовать вовсе. Классический пример — четыре человека, где трое по кругу предпочитают друг друга, а четвёртый у всех последний: кто бы ни оказался с четвёртым, у него найдётся блокирующая пара. Проверить существование и найти решение можно за O(n2)O(n^2) алгоритмом Ирвинга, но он заметно сложнее Гейла–Шепли.

Ничьи в предпочтениях

Если участникам разрешено ставить варианты на одно место, задача про «слабую» стабильность по-прежнему решается: ничьи разбиваются произвольно, и Гейл–Шепли работает. А вот поиск стабильного паросочетания максимального размера при ничьих и неполных списках уже NP-трудная задача.

Сложность

РесурсОценкаКомментарий
ВремяO(n2)O(n^2)Не больше n2n^2 предложений, каждое за O(1)O(1) благодаря rank
ПамятьO(n2)O(n^2)Матрица rank; сами входные списки занимают столько же

Асимптотику не улучшить в общем случае: чтобы просто прочитать все предпочтения, нужно Θ(n2)\Theta(n^2) времени. Подробнее о том, как читать такие оценки, — в статье про нотацию O большое.

Число предложений в худшем случае действительно порядка n2n^2, но на случайных предпочтениях их в среднем около nln⁡nn \ln n: большинство кандидатов пристраиваются в одну из первых компаний своего списка.

Типичные ошибки

  • list.index внутри цикла. Самая частая: код выглядит правильно, но работает за O(n3)O(n^3). Стройте таблицу рангов заранее.
  • Забыть вернуть брошенного в очередь. Компания поменяла партнёра, а вытесненный кандидат исчез из free — он так и останется без пары.
  • Начинать список заново. Вытесненный кандидат продолжает с того места, где остановился, а не с начала списка. Компании, которые ему уже отказали, не передумают — ведь их партнёры только улучшаются.
  • Путать направления индексов. match[p] (компания кандидата) и partner_of[a] (кандидат компании) легко перепутать, особенно при одинаковом nn. Называйте массивы по смыслу и проверяйте ответ через find_blocking_pairs.
  • Считать, что результат «честный» для обеих сторон. Он стабилен, но систематически выгоден предлагающим. На вопрос «кто должен предлагать?» правильный ответ — «та сторона, чьи интересы приоритетнее».
  • Путать стабильность с оптимальностью по сумме. Если интервьюер просит минимизировать суммарную стоимость, нужен венгерский алгоритм, а не Гейл–Шепли.

Как это спрашивают на собеседовании

Прямую задачу «реализуйте Гейла–Шепли» дают нечасто — чаще в компаниях с сильным алгоритмическим уклоном или в виде задачи на дизайн: «распределите кандидатов по командам с учётом предпочтений обеих сторон». Типичный сценарий разговора:

  1. Уточнить определение стабильности и показать, что простая жадность («каждому — его первый выбор») ломается на конфликтах.
  2. Описать алгоритм отложенного принятия и написать код за O(n2)O(n^2), проговорив, зачем нужна таблица рангов.
  3. Доказать завершимость (не больше n2n^2 предложений) и стабильность (две монотонности).
  4. Ответить на follow-up: кому выгоден результат, что будет при нескольких местах у компании, при неполных списках, при одной группе вместо двух.

Если на последнем шаге вы спокойно говорите «результат оптимален для предлагающих и пессимален для принимающих, а при одной группе решения может не быть», — это ровно то, что отличает знание алгоритма от заученного кода.

Итог

  • Стабильное паросочетание — такое, где нет пары, которой выгодно сбежать вдвоём. Оно всегда существует, если групп две.
  • Алгоритм Гейла–Шепли: свободные предлагают по своему списку, принимающие держат лучшего и меняют его на ещё лучшего. Не больше n2n^2 предложений, время O(n2)O(n^2).
  • Корректность следует из двух монотонностей: предлагающие идут вниз по списку, принимающие только улучшают партнёра.
  • Результат не зависит от порядка обработки, но зависит от того, кто предлагает: этой стороне достаётся лучший стабильный вариант, другой — худший.
  • Тот же алгоритм с небольшими правками работает для «один ко многим» и неполных списков; для одной группы нужен уже другой алгоритм, и решения может не быть.

Потренироваться в спокойной обстановке

Все задачи