такие, что rmw [т, w] означает ранг ш-й женщины в спи^ предпочтений, т-го мужчины, а rwm[w, т\ -aw т-го цу чины в списке w-и женщины. Ясно, что значения этих вспо могательных' iviaccHBOB Постоянны и могут быть получен с, самого начала из значений wmr и mwr.

Значение предиката stable (устойчивый) теперь вычис Ляется в строгом соответствии с его исходным определениещ Вспомним, что мы исследуем возможность брака между W, где ш == wmr[m, г], т. е. w имеет ранг г в т-ъл списке пред. почтении. Будучи оптимистами, мы вначале предполагаем что устойчивость сохранилась, а затем пытаемся найти возможные источники неприятностей. Где они могут таиться? Есть две симметричные возможности:

4т-Може1 сущесчвивачъ женщина pw, предпочтительная для т по сравнению с ш, которая сама предпочитает m своему мужу.

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

Исследуя, источник неприятностей 1, мы сравниваем ранги гмм [pw, т] и rwm [pw, y[pw] ] для всех женщин, которых т предпочитает своей невесте йу, т. е. для всех pw wmr[m,i], таких, что i < г. Мы ёнаем, что все эти женщины уже выданы замуж, так как если бы какая-То- из .них была еще одинока, т выбрал бы ее раньще, чем w. Этот процесс проверки можно сформулировать в виде простого линейного поиска; s означает устойчивость:

S := true; Ц := 1; ......

while (i < г) А S йо

Ъе&т pw := wmr[m,i]; i:=i+l; (3-4S)

if -ismg/efpH] then s := rwmlpw, м] > rwmlpw, ylpwjl

Исследуя источник неприятностей 2, мы должны рассмотреть всех мужчин рт, которых w предпочитает своему предполагаемому партнеру т, т. е. всех рт = mwr [w, i], таких, что г < rwm [w, т]. Как и при исследовании источника Ь нужно сравнивать ранги rmw[pm,w] и rmw [рт, х[рт]] здесь HyHtHO быть внимательными, чтобы не производить срав; нений с участием х[рт], где рт еще не женат. Необходимой предосторожностью будет проверка рт < т, поскольку знаем, что все мужчины, предшествующие т, уже женаты. Г; Весь алгоритм представлен в программе 3.6. Табл. 3.3 сО держит множество входных данных, соответствующих массй'

Таблица 3.3. Пример вкоднык данных для задачи об устойчивых браках

вам wmr и mwr. И наконец, в табл. 3.4 приведены девять йо-лученных решений.

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

Решение

p <;=количество проверок устойчивости., решение 1==решение, оптимальное для мужчин.- ещение 9=решение, оптимальное для женщин.:

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

program marriage {input,output у, [задача о стабильных браках] const и = 8;

type man = I . .п; woman 1 .. и; rank = 1 .. var m: man; w: woman; r: rank;

wmr: array [man, rank] of woman;

mwr: array [woman, rank] of man;

rmw: array [man, woman] of rank;

rwm: array [woman, man] of rank;

x: ятгяу [man] of woman;

y: япяу [woman] of man;

single: ятгяу [woman] of boolean;

procedure print;

var m: man; rm, rw: mieger; begin rm := 0; rw 0; *

for w := 1 to n do begin write {x[m]:4);

rm :== rm -f rmwlni,x[m[]; rw := rw + /*w/ lx[m],wj end ;

writeln {rm:,rw:4); end {рпн/} ;

procedure try{m: man); var r: rank; w: woman;

function stable: boolean;

var pm: man; pw: woman; *

/, lim: rank; s: boolean; \

begin s true; i:~ \; while {i<r) A s йо beginи := wmr[m,i]; i:~ i+l;

if -isinglelpw] then ;S := гй/и[/И',пг] > rwm[pw,y[pii]] end;

i 1; lim :- rwm[w,m];

while (Klim) A s йо

begin pm := т'/[и',/3; / := HI;

if pm < m then s := rmw{pm,w] > rmw[pm,x[pm]] end ;

stable :=j J end {i/efc/e} ; begin [try)

for r := 1 to H do begin w := /[т/];