Реализация алгоритма устойчивых паросочетаний

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

Для простоты будем считать, что элементы множеств мужчин и женщин пронумерованы {1, …, n}. Для этого можно упорядочить мужчин и женщин (скажем, по алфавиту) и связать число i с i-м мужчиной mi  и i-й женщиной wi  в этом порядке.

Такое предположение (или система обозначений) позволяет определить массив,

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

Мы будем использовать запись ManPref[m, i] для обозначения i-й женщины в списке предпочтений мужчины m и аналогичную запись WomanPref[w, i] для обозначения i-го мужчины в списке предпочтений женщины w. Обратите внимание: для хранения предпочтений всех 2n людей понадобится пространство O(n2), так как для каждого человека создается список длины n.

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

1. Найти свободного мужчину.
2. Для мужчины m — найти женщину с наивысшей оценкой, которой он еще не делал предложение.
3. Для женщины w — проверить, находится ли w в состоянии помолвки, и если находится, найти ее текущего партнера.
4. Для женщины w и двух мужчин m и m’ — определить (также за постоянное время), кто из m и m’ является предпочтительным для w.

Начнем с выбора свободного мужчины. Для этого мы организуем множество свободных мужчин в связанный список. Когда потребуется выбрать свободного мужчину, достаточно взять первого мужчину m в этом списке. Если m переходит в состояние помолвки, он удаляется из списка, возможно, со вставкой другого мужчины m’, если тот переходит в свободное состояние. В таком случае m’ вставляется в начало списка — также за постоянное время.

Возьмем мужчину m. Требуется выявить женщину с наивысшей оценкой, которой он еще не делал предложение. Для этого понадобится дополнительный массив Next, в котором для каждого мужчины m хранится позиция следующей женщины, которой он сделает предложение, в его списке.

Массив инициализируется Next[m] = 1 для всех мужчин m. Если мужчина m должен сделать предложение, он делает его женщине w = ManPref[m, Next[m]], а после предложения w значение Next[m] увеличивается на 1 независимо от того, приняла w его предложение или нет.

Теперь предположим, что мужчина m делает предложение женщине w; необходимо иметь возможность определить мужчину m’ , с которым помолвлена w (если он есть). Для этого будет создан массив Current длины n, где Current[w] — текущий партнер m’ женщины w. Если мы хотим обозначить, что женщина w в настоящее время не помолвлена, Current[w] присваивается специальное обозначение null; в начале алгоритма Current[w] инициализируется null для всех w.

Итак, структуры данных, которые мы определили до настоящего момента, способны реализовать каждую из операций (1)–(3) за время O(1).

Пожалуй, сложнее всего будет выбрать способ хранения предпочтений женщин, обеспечивающий эффективную реализацию шага (4). Рассмотрим шаг алгоритма, на котором мужчина m делает предложение женщине w. Предположим, w уже помолвлена и ее текущим партнером является m’ = Current[w]. Нам хотелось бы за время O(1) решить, кто, с точки зрения w, является более предпочтительным — m или m’.

Хранение предпочтений женщин в массиве WomanPref (по аналогии с тем, как это делалось для мужчин) не работает, так как нам придется последовательно перебирать элементы списка w; поиск m и m’ в списке займет время O(n). И хотя время O(n) является полиномиальным, можно получить намного лучший результат, построив вспомогательную структуру данных.

В начале алгоритма мы создадим массив Ranking с размерами n × n, в котором Ranking[w, m] содержит оценку мужчины m в отсортированном порядке предпочтений женщины w. Для каждой женщины w этот массив создается за линейное время при одном проходе по ее списку предпочтений; таким образом, общие затраты времени пропорциональны n2. После этого, чтобы решить, кто из мужчин — m или m’ — является предпочтительным для w, достаточно сравнить значения Ranking[w, m] и Ranking[w, m’].

Это позволяет выполнить шаг (4) за постоянное время, а следовательно, у нас появляется все необходимое для обеспечения желаемого времени выполнения.

(2.10) Структуры данных, описанные выше, позволяют реализовать алгоритм Гейла–Шепли за время O(n2).