Предположим, ЧТО А - множество мужчин, а В - множе-о ;кенщин. Каждый мужчина и каждая женщина устанав-ggjoT определенный порядок предпочтения для своих воз-яных партнеров по браку. Если п пар выбрано таким об-язо№, что существуют какие-то мужчина и женщина, не со-Р^щ'ие в браке друг с другом, но предпочитающие друг пуга своим действительным супругам, то такое множество йойков считается неустойчивым. Если же такой пары не су-яествует, то множество называется устойчивым.

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

Решение можно искать следующим образом; пробовать последовательно объединять в пары члены двух множеств, пока оба множества не будут исчерпаны. Намереваясь найти все устойчивые распределения, мы можем легко набросать решение, используя в качестве образца схему программы (3.35). Пусть try{m)-алгоритм поиска партнерши для мужчины т, и пусть поиск происходит согласно списку предпочтений этого мужчины. Приведем первую версию, основанную на этих допущениях:

procedure try{m: man);

var г: rank; begin

for r:=l to ft do

begin выбрать г-ю женщину из списка предпочтений мужчины т;

if приемлемо then

begin записать брак; (3.36)

if т - не последний мужчина then try{succ{m))

else записать устойчивое множество; отменить брак end end .

end ... . . . .. -

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

дютг{т] обозначает список прсдпочтспнй, установленный муж-чиной т, т. е. wmr [т\ [г] ~ wmr [т, г\ - женщина, которая занимает г-е место в списке предпочтений мужчины т. Точно так же mwr [w] - список предпочтений женщины ш, а mwr{w,r\ - мужчина, занимающий г-е место в ее списке.

Результат представляется в виде массива женщин х, такого, что х[т] обозначает партнершу мужчины т. Для сохранения симметрии (называемой также равноправием ) между мужчинами и женщинами, вводится дополнительный массив у, такой, что y[w] обозначает партнера женщины ш:

var х: arrayfmanl of woman;

(3 39)

у: arrayof man;

Ясно, что в массиве у нет особой нужды, поскольку он содержит информацию, которая уже представлена в массиве х. В самом деле, для любых т я w, состоящих между собой в браке, выполняются равенства

X [у [w] ] = w, у [х [т] ] = т. (3.40)

Следовательно, значение y\w\ можно установить просто поиском по х; но использование массива у явно повышает эффективность. Информация, представленная в массивах х и f/i нужна для огтределения устойчивости предлагаемого множества браков. Поскольку это множество строится постепенно, путем выбора отдельных пар и проверки устойчивости множества после каждого такого предлагаемого брака, д; и </ используются еще до того, как будут заполнены. Для того чтобы знать, какие компоненты уже определены, можно ввести бУ левские массивы

singtem: array[ma ] of boolean singtew: array[twoman] of boolean

В частности, сразу понятно, что означает какая-либо nepeej ная:

type тап = 1. .п;

woman=\..n\ {ц

rank == 1.. п;

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

var штг:. array[man, rank\o\ woman mwr: array[ffiomaft, rank]ot man

какими значениями:

-xsinglem [т] предполагает, что х [mj определено, -,singlew[w] предпо.пагает, что y[is!}] определено.

plo, рассматривая предлагаемый алгоритм, легко обнару- (ять, что семейное положение мужчины можно определить дрпсто по значению т следующим образом:

- singlem[k]k< т. (3.42)

0оэтому массив singlem можно удалить; соответственно мы упростим имя singlew до single.

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

procedure иу(т: man);

var г: rank; w: woman; beinfor / := 1 to и do

begin vt := wmr[m,r];

if singldiw] Д stable then

begin x[m] w; y[w] : m; single[w] . false;

is m < n then try(succ(m))

else запись устойчивого множества;

single[w] := true end

Здесь все еще заметно большое сходство с программой 3.5.

Теперь основная задача - уточнить алгоритм определения устойчивости. К сожалению, устойчивость нельзя представить таким, же простым выражением, как безопасность позиции ферзя в программе 3.5. Нужно прежде всего иметь в виду, что устойчивость по определению следует из сравнения предпочтений, или рангов. Но ранги мужчин и женщин нигде в Наших описанных до сих пор данных явно не представлены. Конечно, ранг женщины w с точки зрения мужчины т можно вычислить, но лишь с помощью трудоемкого поиска w тг[т].

Так как вычисление устойчивости - очень частое действие, ЗДательно, чтобы эта информация была более доступна. Для этого мы будем использовать две матрицы

rmw: аггау[тап, woman] of rank;

rwm: array[woman, mari]ofrank;