Как работает алгоритм Гейла-Шепли?

Алгоритм Гейла-Шепли с отложенным принятием проходит в несколько раундов. В каждом раунде каждый свободный предлагающий делает предложение самому предпочтительному участнику из своего списка, который его еще не отвергал. Каждый принимающий временно принимает лучшее из полученных предложений и отвергает остальные; любой вытесненный предлагающий снова становится свободным. Алгоритм завершается, когда свободных предлагающих не остается.

Является ли стабильное сопоставление уникальным?

Нет. В одном наборе предпочтений может существовать много стабильных сопоставлений. Однако, когда одна сторона предлагает, алгоритм Гейла-Шепли всегда выдает оптимальное стабильное сопоставление для предлагающих: каждый предлагающий получает лучшего партнера, которого он мог бы получить в любом стабильном сопоставлении. Симметрично, это худший вариант для принимающей стороны.

Что такое блокирующая пара?

Блокирующая пара — это пара (a, b), не состоящая в браке в данный момент, где 'a' предпочитает 'b' своему текущему партнеру, И 'b' также предпочитает 'a' своему текущему партнеру. Если такая пара существует, сопоставление нестабильно. Стабильное сопоставление не имеет блокирующих пар.

Где применяется стабильное сопоставление в реальности?

Алгоритм Гейла-Шепли лежит в основе Национальной программы сопоставления резидентов (NRMP) в США, систем выбора школ в Бостоне и Нью-Йорке, приема в колледжи, обмена донорскими почками. Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике 2012 года частично за эту работу.

Должны ли обе группы быть одинакового размера?

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

Решатель задачи о стабильных браках

Решите задачу о стабильных браках / стабильном паросочетании с помощью алгоритма Гейла-Шепли. Вставьте ранжированные списки предпочтений для двух групп равного размера и получите гарантированно стабильное паросочетание с анимированной трассировкой предложений, статистикой удовлетворенности, проверкой блокирующих пар и интерактивной двудольной визуализацией.

Примеры:

Классический 3×3 Медицинская резидентура Учебный пример P/R Команды 5×5 4×4 (Б предлагает)

Одна строка на участника: Имя: Выбор1, Выбор2, ... — перечислите всех участников Группы Б по порядку.

Тот же формат. Каждый участник Группы Б ранжирует всех участников Группы А.

Кто предлагает?

В алгоритме Гейла-Шепли предлагающая сторона получает наилучшего возможного стабильного партнера, а принимающая — наихудшего.

Embed Решатель задачи о стабильных браках Widget

О Решатель задачи о стабильных браках

Решатель задачи о стабильных браках — это интерактивная реализация алгоритма Гейла-Шепли с отложенным принятием. Этот алгоритм сопоставления, представленный в 1962 году Дэвидом Гейлом и Ллойдом Шепли, доказывает, что всегда можно составить стабильные пары между двумя группами равного размера, если каждый участник предоставил полный список своих предпочтений. Инструмент принимает списки предпочтений, пошагово выполняет алгоритм и визуализирует результат в виде стабильного сопоставления, анимации двудольного графа, тепловых карт и подтвержденного доказательства отсутствия блокирующих пар.

Что такое задача о стабильных браках?

Даны два непересекающихся множества одинакового размера — например, n мужчин и n женщин, или n кандидатов и n вакансий. У каждого участника есть полный список предпочтений относительно участников другой группы. Сопоставление — это разбиение всех на пары «один-к-одному». Сопоставление называется стабильным, если не существует пары (a, b) вне сопоставления, которая предпочла бы быть друг с другом больше, чем со своими назначенными партнерами.

Формально, сопоставление M стабильно, если нет блокирующей пары — пары (a, b), где a в паре с b', а b в паре с a', таких что:

a предпочитает b больше, чем b' И b предпочитает a больше, чем a'

Если оба условия выполняются, a и b бросят своих партнеров, что делает сопоставление нестабильным. Стабильное сопоставление — это такое, где подобных пар нет.

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

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

Каждый свободный предлагающий делает предложение самому предпочтительному кандидату из своего списка, который его еще не отвергал.
Каждый принимающий, получивший одно или несколько предложений, выбирает наиболее предпочтительного (сравнивая его с текущим временным партнером) и временно принимает его; остальные отвергаются.
Отвергнутые предлагающие снова становятся свободными и переходят к следующему выбору в следующем раунде.
Алгоритм завершается, когда все предлагающие заняты — это гарантированно происходит максимум за n² предложений.

Временная сложность: O(n²) Сложность по памяти: O(n²) Макс. предложений: n²

Ключевые теоретические свойства

Существование и уникальность

Стабильное сопоставление существует всегда (Гейл и Шепли, 1962), но не всегда уникально. Для одного набора предпочтений может быть несколько вариантов стабильных пар.

Оптимальность для предлагающих

Когда одна сторона предлагает, алгоритм Гейла-Шепли выдает стабильное сопоставление, оптимальное для предлагающих: каждый предлагающий получает лучшего партнера, который возможен при условии стабильности. По симметрии это также наихудшее (пессимальное) сопоставление для принимающих. Смена предлагающей стороны в этом калькуляторе часто меняет результат.

Устойчивость к стратегиям

В алгоритме Гейла-Шепли предлагающим невыгодно лгать о своих предпочтениях: говорить правду — доминирующая стратегия. Однако принимающие иногда могут получить выгоду от стратегического искажения списка.

Формат ввода

Калькулятор ожидает по одной строке на участника: имя, двоеточие и полный ранжированный список предпочтений через запятую:

Имя1: выбор1, выбор2, выбор3, ..., последний выбор Имя2: выбор1, выбор2, ... ...

Требования:

Обе группы должны иметь одинаковое количество участников.
У каждого участника должен быть ранжирован каждый представитель другой группы.
В именах можно использовать буквы, цифры, пробелы и стандартные символы Unicode.
Поддерживается до 15 участников с каждой стороны для корректной анимации.

Как пользоваться калькулятором

Введите предпочтения Группы А в левое поле — по строке на человека.
Введите предпочтения Группы Б в правое поле в том же формате.
Выберите предлагающую сторону. Попробуйте оба варианта, чтобы сравнить А-оптимальный и Б-оптимальный результаты.
Нажмите «Решить задачу о стабильных браках». Вы получите список пар, статистику, анимацию и проверку стабильности.
Используйте плеер анимации (пуск, шаг, сброс), чтобы увидеть каждое предложение, принятие и замену в деталях.
Изучите тепловую карту. Желтым обведены итоговые пары — посмотрите, насколько высоко или низко они находятся в списках предпочтений.

Медицинская резидентура и Нобелевская премия

В 2012 году Шведская королевская академия наук присудила Нобелевскую премию по экономике Ллойду Шепли (за теорию, вместе с Дэвидом Гейлом, который не дожил до этого момента) и Элвину Роту (за применение теории на практике, включая редизайн систем сопоставления врачей и доноров почек). Награда была вручена за «теорию стабильного распределения и практику проектирования рынков».

Часто задаваемые вопросы

Что такое задача о стабильных браках?

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

Должны ли группы быть равными?

В классической модели — да. Для несбалансированных групп (например, больше студентов, чем мест в вузах) используются модификации алгоритма, такие как задача о больницах и резидентах.

Дополнительные материалы

Ссылайтесь на этот контент, страницу или инструмент так:

"Решатель задачи о стабильных браках" на сайте https://ru.miniWebtool.com/решатель-задачи-о-стабильных-браках/ от MiniWebtool, https://MiniWebtool.com/

от команды miniwebtool. Обновлено: 22 апр. 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.