31. Применение алгоритма с возвратом к задаче о паросочетаниях (стабильных браках)

 

 Предположим, есть два непересекающихся множества А и В оди­накового размера п. Нужно найти множество из п пар (а, Ь), та­ких, что а принадлежит A, a b принадлежит В и они удовлетворя­ют некоторым условиям. Для выбора таких пар существует мно­го различных критериев; один из них называется правилом стабильных браков.

Предположим, что Амножество мужчин, а В — женщин. У каждых мужчины и женщины есть различные правила пред­почтения возможного партнера. Если среди п выбранных пар су­ществуют мужчины и женщины, не состоящие между собой в бра­ке, но предпочитающие друг друга, а не своих фактических суп­ругов, то такое множество браков считается нестабильным. Если же таких пар нет, то множество считается стабильным. Такая си­туация характерна для многих похожих задач, где нужно прово­дить распределение в соответствии с некоторыми правилами предпочтения. Так, например, идет выбор студентами учебных заведений, призывниками — родов войск и т. п. Пример с браками выбран нами почти интуитивно, причем заметим, что правила предпочтения постоянны и в процессе выбора не изменяются. Это упрощает задачу, но сильно искажает действительность (как вся­кая абстракция).

 Один из путей поиска решения: пробовать объединять в пары элементы двух множеств до тех пор, пока они не будут исчерпа­ны. Намереваясь найти все устойчивые распределения, мы можем легко набросать некоторое решение, используя в качестве образца схему (3.35). Пусть Try (m) — алгоритм поиска супруги для мужчины m, причем этот поиск идет в порядке списка предпочтений именно этого мужчины. Первый вариант программы, основанный на этих предположениях, таков:

 

PROCEDURE Try(mman);

    VAR  r:   rank;

BEGIN

 FOR  r :=  1 TO n DO

выбор r-й претендентки для m;

IF допустимо THEN запись брака;

IF m - не последний THEN Try(successor(m))                          (3,36)

ELSE записать стабильное множество

END;

отменить брак

END 

END

END Try;

 

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

TYPE   man = [1..n];

woman = [1..n];                                                                                             (3.37)

 rank = [1..n];

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

VAR wmr: ARRAY man, rank OF woman;

mwr: ARRAY woman, rank OF man;

Соответственно, wmrm обозначает список женщин, предпочти­тельных для мужчины т, т. е. wmrm,  — женщина, стоящая на r-м  месте в списке для мужчины т. Аналогично, mwrwсписок предпочтительных партнеров для женщины w, a mwrw, rее r-й кандидат. В табл. 3.3 приведен пример таких исходных данных. Результат — массив женщин х, причем хт соответствует партнерше для мужчины т. Для поддержания симметрии между мужчинами и женщинами вводится дополнительный список у, и yw  задает партнера для женщины w.

VAR       x: ARRAY man OF woman;

 у: ARRAY woman OF man;                                                                              (3.39)

Фактически массив у излишен, поскольку хранящаяся в нем ин­формация уже существует в х. Ясно, что для находящихся в браке мужчины и женщины справедливы равенства:

Xyw=w, yxm=m.                                                                                                                                                   (3.40)

Таким образом, значение yw можно определить с помощью простого просмотра х. Однако нет сомнения, что наличие у повышает эффективность алгоритма. Ведь информация, заключающаяся в массивах х и у, нужна для определения стабильности предлага­емого множества браков. Поскольку это множество строится шаг за шагом и после каждого предлагаемого брака проверяется стабильность, то х и у используются еще до того, как будут определе­ны все их компоненты. Для того чтобы знать, какие компоненты уже определены, можно ввести булевские массивы:

singlem:  ARRAY man OF BOOLEAN;

singlew:  ARRAY woman OF BOOLEAN;                                                                        (3.41)                 

Истинность значения singlemm означает, что хm уже определено, a singlew wчто определено yw. Просматривая предложенный ал­горитм, мы, однако, легко выясняем, что семейное положение мужчины т определяется равенством:

~singlem[k] =k<m                                                                                          (3.42)

Следовательно, массив singlem можно убрать, соответственно и имя singlew сокращается до single. Все эти соглашения приводят нас к нижеприведенному уточненному алгоритму (3.43). Пре­дикат допустимо можно представить в виде конъюнкции single и stable, где stable — функция, которую еще нужно определить.

 

PROCEDURE Try(m:   man);

   VAR r: rank; w: woman;

BEGIN

FOR r := 1 TO n DO

w := wmr[m,r];

IF single[w] & stable THEN                                                                  (3.43)

           x[m]   := w;   y[w]   := m;   single[w]   := FALSE;

IF m < n THEN Try(successor(m))  ELSE  record Set  END;

single[w]   := TRUE

 END

END

END Try;

В этот момент все еще продолжает бросаться в глаза большое сходство с листингом 3.5. Теперь основная задача – уточнить ал­горитм определения стабильности. К сожалению, стабильность невозможно представить с помощью такого же простого выражения, каким характеризовалась безопасность поля для ферзя в программе на листинге 3.5. Прежде всего следует иметь в виду, что по определению стабильность связана со сравнением предпочтительности партнеров (рангов). Однако ранги мужчин и женщин нигде в наших данных явно не фигурируют. Конечно, ранг женщины  w  с точки зрения мужчины m можно определить, но для этого нужен “трудоёмкий” поиск значения w в массиве wmrm. Поскольку вычисления стабильности – очень часто встречающаяся операция, то хотелось бы, чтобы эта информация была более доступна. Для этого воспользуемся двумя матрицами: 

                rmw: ARRAY man, woman OF rank;                                                                 (3.44)

            rwm: ARRAY woman, man OF rank;

причем rmwm,w означает ранг женщины w в списке предпочтений мужчины m, а rwmw,m – ранг мужчины m в списке женщины w. Ясно, что значения этих вспомогательных массивов суть константы, и их можно определить в самом начале по значениям rmw и rwm. Процесс вычисления предиката stable теперь можно вести в строгом соответствии с его первоначальным определением. Вспомним, что мы пытаемся  определить возможность брака между m и w, где w=wmrm,r т.е. w стоит в списке  m на r-ом месте. Будучи оптимистами, мы вначале будем предполагать, что стабильность сохраняется, а затем уже попытаемся найти возможные источники неприятностей.  Где они могут таиться? Существуют две симметричные возможности:

1.       Может существовать женщина pw, которая для m предпочтительнее w, причем для pw m предпочтительнее её супруга.

2.       Может существовать мужчина pm, который для w предпочтительнее m, причем для hm w предпочтительнее его супруги.

 Исследуя первый источник неприятностей, мы сравниваем ранги rwmpw,ypw для всех женщин, которых m предпочитает w, т.е. для женщин, удовлетворяющих условию pw = wmrm,I при i < r.  Мы знаем, что все эти женщины уже были выданы замуж, так как если бы одна из них была ещё одинокой, то m выбрал бы её Описанный процесс можно сформулировать как простой линейный поиск; s означает стабильность:

s:= TRUE;  i:=1;

While (i< r) & s DO                                                                                                     (3.45)

pw  := wmr[m,i ];   i   ;= i+1;

IF ~single[pw] THEN s :=  rwm[pw,m] >  rwm[pw,y[pw]] END

END;

В поисках неприятностей второго вида мы должны проверить всех кандидатов рт, которые для w предпочтительнее "суженого", т. е. всех предпочитаемых ею мужчин рт = mwrW, i  для  i < rwmw,т. Как и при исследовании неприятностей первого вида нужно сравнивать ранги rmwpm, w с rmwpm,Xpm. Однако здесь надо быть внимательными и не проводить сравнение с хрт, если рm, еще не женат. Для этого можно воспользоваться проверкой рт < т, так как известно, что все мужчины, предшествующие m уже женаты.

 Полный алгоритм представлен в листинге 3.6, а в табл. 3.4 приведены девять стабильных решений, полученных на основе исходных wmr и mwr из табл. 3.3.

 Наш алгоритм построен по простой схеме поиска с возвратом. Его эффективность зависит главным образом от того, насколько удачно выбрана схема усечения дерева решений. Маквити и Уилсон [3.1; 3.2] предложили несколько более быстрый, но зато более сложный и менее "прозрачный" алгоритм; к тому же они распространили его на случай множеств различного размера.

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

 

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

 

X1

X2

X3

X4

X5

X6

X7

X8

rm

rw

c

1

7

4

3

8

1

5

2

6

16

32

21

2

2

4

3

8

1

5

7

6

22

27

449

3

2

4

3

1

7

5

8

6

31

20

59

4

6

4

3

8

1

5

7

2

26

22

62

5

6

4

3

1

7

5

8

2

35

15

47

6

6

3

4

8

1

5

7

2

29

20

143

7

6

3

4

1

7

5

8

2

38

13

47

8

3

6

4

8

1

5

7

2

34

18

758

9

3

6

4

1

7

5

8

2

43

11

34

 

Примечания:              а) с — число проверок устойчивости,

                        б) Решение 1 оптимально для мужчин, решение 9 — для женщин.

 

 Обратите внимание, что в табл. 3.4 приведены суммы рангов всех женщин с точки зрения их мужей и суммы рангов всех мужей с точки зрения их жен. Эти величины определяются так:

rт = Sm : 1<= т <= п : rmwm,Xm,

rw = Sm : 1<= т <= п : rwтXm, т.                                                                                                                                       (3.46)

 

Решение с минимальным значением rт называется стабильным оптимальным для мужчин, а с самым маленьким значением rw стабильным и оптимальным для женщин. Природа нашей стратегии выбора такова, что первыми формируются решения, больше удовлетворяющие мужчин, а решения, хорошие с точки зрения женщин, появляются только в конце. В этом смысле алгоритм ориентирован на сильный пол. Его можно быстро переориентировать, если систематически менять ролями мужчин и женщин, т.е. просто заменить mwr на wmr и наоборот. Мы не будем уже усложнять дальше нашу программу и оставим поиск оптимального решения для следующего, теперь, наконец, последнего примера алгоритма с возвратом.