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

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

Для простоты будем считать, что элементы множеств мужчин и женщин про- нумерованы {1, ..., n}. Для этого можно упорядочить мужчин и женщин (скажем, по алфавиту) и связать число i с i-м мужчиной m и i-й женщиной w. в этом порядке. Такое предположение (или система обозначений) позволяет определить массив, индексированный по всем мужчинам или всем женщинам. Нам нужно создать список предпочтений для каждого мужчины и каждой женщины. Для этого пона- добятся два массива: в одном будут храниться предпочтения женщин, а в другом предпочтения мужчин. Мы будем использовать запись 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 = МаnРrеf[m,Nехt[m]], а после предложения w значение Nехt[m] увеличивается на 1 независимо от того, приняла w его предложение или нет.

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

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

Пожалуй, сложнее всего будет выбрать способ хранения предпочтений женщин, обеспечивающий эффективную реализацию шага (4). Рассмотрим шаг алгоритма, на котором мужчина m делает предложение женщине w. Предположим, w уже по- молвлена и ее текущим партнером является m' = Сurrепt[w]. Нам хотелось бы за время 0(1) решить, кто, с точки зрения w, является более предпочтительным — m или m'. Хранение предпочтений женщин в массиве WomanPrеf (по аналогии с тем, как это делалось для мужчин) не работает, так как нам придется последовательно перебирать элементы списка w; поиск m и m' в списке займет время 0(n). И хотя время 0(n) является полиномиальным, можно получить намного лучший результат, построив вспомогательную структуру данных.

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

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

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

2.4.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ УДАЧИ
  3. Уровень устойчивого, продолжительного счастья
  4. АЛГОРИТМ
  5. 4.2. Хорошие и устойчивые вопросы
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. Методика повышения психологической устойчивости.
  8. Методика повышения психологической устойчивости.
  9. Специальную значимость имеетморально-психологическая устойчивость
  10. Алгоритм исцеления:
  11. Статья 220. Сокрытие устойчивой финансовой несостоятельности
  12. Алгоритм избавления от боли