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

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

Вероятно, у вас уже имеется некоторый опыт реализации базовых алгоритмов со структурами данных. В этой книге структуры данных будут рассматриваться в контексте реализации конкретных алгоритмов, поэтому в ней вы встретите разные структуры данных в зависимости от потребностей разрабатываемого алгоритма. Для начала мы рассмотрим реализацию алгоритма устойчивых паросочетаний Гейла-Шепли; ранее было показано, что алгоритм завершается максимум за n² итераций, а наша реализация обеспечивает соответствующее худшее время выполнения O(n²) с подсчетом фактических вычислительных шагов вместо простого количества итераций. Чтобы получить такую границу для алгоритма устойчивых паросочетаний, достаточно использовать две простейшие структуры данных: списки и массивы. Таким образом, наша реализация также предоставит хорошую возможность познакомиться с использованием этих базовых структур данных.

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

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

Массивы и списки

Для начала сосредоточимся на одном списке — например, списке женщин в порядке предпочтений некоторого мужчины. Возможно, для хранения списка из n элементов проще всего воспользоваться массивом A длины n, в котором A[i] содержит i-й элемент списка. Такой массив легко реализуется практически на любом стандартном языке программирования и обладает следующими свойствами.

♦ Ответ на запрос вида “Какое значение хранится в i-м элементе списка?” можно получить за время O(1), напрямую обратившись к значению A[i].

♦ Если мы хотим определить, входит ли в список некоторый элемент e (то есть равен ли он A[i] для некоторого i), необходимо последовательно проверить все элементы за время O(n) — при условии, что нам ничего не известно о порядке следования элементов в A.

♦ Если элементы массива отсортированы в четко определенном порядке (например, по числовым значениям или по алфавиту), тогда принадлежность элемента e списку проверяется за время O(log n) методом бинарного поиска; в алгоритме устойчивых паросочетаний бинарный поиск не используется, но мы вернемся к нему в следующем разделе.

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

Для ведения таких динамических наборов элементов можно (а часто и желательно) использовать связанные списки. В связанном списке для формирования последовательности элементов каждый элемент указывает на следующий элемент списка. Таким образом, в каждом элемента v должен храниться указатель на следующий элемент; если это последний элемент, указателю присваивается null. Также существует указатель First, ссылающийся на первый элемент. Начиная с First и последовательно переходя по указателям на следующий элемент, пока не будет обнаружен указатель null, можно перебрать все содержимое списка за время, пропорциональное его длине.

Обобщенный способ реализации связанного списка, в котором набор возможных элементов не может быть зафиксирован изначально, основан на создании записи e для каждого элемента, включаемого в список. Такая запись содержит поле e. val, в котором хранится значение элемента, и поле e. Next с указателем на следующий элемент списка. Также можно создать двусвязный список, поддерживающий переходы в обоих направлениях; для этого добавляется поле e. Prev со ссылкой на предыдущий элемент списка. (Для первого элемента в списке e. Prev = null.) Также добавляется указатель Last — аналог First, указывающий на последний элемент в списке. Схематическое изображение части такого списка представлено в верхней части рис. 2.1.

Рис. 2.1. Схематическое представление двусвязного списка с удалением элемента e

С двусвязным списком могут выполняться следующие операции.

♦ Удаление. Чтобы удалить элемент e из двусвязного списка, достаточно “обойти” его так, чтобы предыдущий элемент (на который указывает e.Prev) и следующий элемент (на который указывает e. Next) указывали друг на друга. Операция удаления изображена на рис. 2.1.

♦ Вставка. Чтобы вставить элемент e между элементами d и f в списке, мы присваиваем d.Next и f.Prev указатель на e, а полям Next и Prev в e — указатели на d и f соответственно. Эта операция, по сути, является обратной по отношению к удалению; чтобы понять происходящее, достаточно просмотреть рис. 2.1 снизу вверх.

При вставке или удалении e в начале списка обновляется указатель First — вместо обновления записи элемента, предшествующего e.

Списки хорошо подходят для ведения динамически изменяемых множеств, но у них имеются свои недостатки. В отличие от массивов, i-й элемент списка невозможно найти за время O(1): переход к i-му элементу потребует перехода по указателям Next, начиная от начала списка, что займет в общей сложности время O(i).

С учетом относительных достоинств и недостатков массивов и списков может оказаться так, что мы получим входные данные задачи в одном из двух форматов и захотим преобразовать их к другому формату. Как упоминалось ранее, такая предварительная обработка часто приносит пользу; и в таком случае преобразование между массивами и списками легко выполняется за время O(n). Это позволит нам свободно выбрать структуру данных, которая лучше подходит для конкретного алгоритма, не привязываясь к той структуре, в которой были получены входные данные.

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

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

Для простоты будем считать, что элементы множеств мужчин и женщин пронумерованы {1, ..., n}. Для этого можно упорядочить мужчин и женщин (скажем, по алфавиту) и связать число i с i-м мужчиной m_i и i-й женщиной w_i в этом порядке. Такое предположение (или система обозначений) позволяет определить массив, индексированный по всем мужчинам или всем женщинам. Нам нужно создать список предпочтений для каждого мужчины и каждой женщины. Для этого понадобятся два массива: в одном будут храниться предпочтения женщин, а в другом предпочтения мужчин. Мы будем использовать запись ManPref[m, i] для обозначения i-й женщины в списке предпочтений мужчины m и аналогичную запись WomanPref[w, i] для обозначения i-го мужчины в списке предпочтений женщины w. Обратите внимание: для хранения предпочтений всех 2n людей понадобится пространство O(n²), так как для каждого человека создается список длины 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 этот массив создается за линейное время при одном проходе по ее списку предпочтений; таким образом, общие затраты времени пропорциональны n². После этого, чтобы решить, кто из мужчин — m или m' — является предпочтительным для w, достаточно сравнить значения Ranking[w, m] и Ranking[w, m'].

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

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