Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 31
Текст из файла (страница 31)
Пусть 1ту(т) — алгоритм поиска партнерши для мужчины т, н пусть поиск происходят согласно списку предпочтений этого мужчины. Приведем первую версию, основанную на этих допущениях: ргосег(нге 1ту(т: тап); чаг т1 тапй; Ьеп)п 1ог т:=1 1о п бо Ьея)п вгабрать т-ю акени1ину из списка предпочтеншь лчулсчпны т; И приемлемо 1Ьеп Ьса)п записать брак; (3. 36) 11 гп — не последний жузечина 1Ьеп!ту(зисс(нп)) е1ае записать устойчивое мноаеество; отменить брак епб епб епг) Вновь мы пе можем двигаться дальше, пока яе решим, как представлять данные. Определпь~ трп скалярных типа; для простоты пусть нх значения будут целыми числами от 1 до и. Хотя формально эти трн типа одинаковы, присваивание им различимых имен значительно проясняет программу.
8. Ранурсиен»ы алгоритмы !тв В частности, сразу понятно, что означает какая-либо перемен- ная: (уре таи = 1 .. п; потап=1. и; гаий=! .и; (3.37) Исходные данные представляются двумя матрицами, в которых указан порядок предпочтений мужчин н женщин их партнерами: чаг штг: аггау[тап, гаиlг]о1 шатап тгег: аггау[сеотап, гапп]о$ тап (3.38) штг [т] обозначает список предпочтений, установленный мужчиной т, т.
е. штг[т] К= тетг[т,г] — женщина, которая занимает г-е место в списке предпочтений мужчины т. Точно так же та[и] — список предпочтений женщины и, а ттег[ю, г] — мужчина, занимающий г-е место в ее списке. Результат представляется в виде массива женшин х, такого, что х[т] обозначает партнершу мужчины и, Для сохранения симметрии (называемой также аравноправием») между мужчинами и женщинами, вводигся дополнительный массив у, такой, что у[в] обозначает партнера женщины ан чаг х: аггау[тап] о1 шатап; у: аггау[щотап] о1 таи; (3,39) Ясно, что в массиве у иет особой нужды, поскольку он содержит информацию, которая уже представлена в массиве х. В самом деле, лля любых т и ш, состоящих между собой в браке, выполняются равенства х[у[ю]]=и, у[х[т]]=и. (3,40) зту!ет: аггау[тап] о$ Ьоо1еап (3.4 !) а(ис!евп аггау[аютап] от Ьоо!еап Следовательно, значение у[в] можно установить просто поиском по х; но использование массива у явно повышает эффективность.
Информация, представленная в массивах х и у, нужна для определения устойчивости предлагаемого множества браков. Поскольку это множество строится постепенно, путем выбора отдельных пар и проверки устойчивости множества после каждого такого предлагаемого брака, х и у используются еще до того, как будут заполнены.
Для того чтобы. знать, какие компоненты уже определены, можно ввести булевские массивы ай. Задача об устойчивых браках с такими значениями: — зспй(епг [пг[ предполс гает, что х [гп[ определено, — Ипй(есе [со[ предполааавг, что у [са[ определено, Но, рассматривая предлагаемый алгоритм, легко обнаружить, что семейное положение мужчины можно определить просто по значению гп следующим образом: — айсй1ет [й[ ыа й < т. Поэтому массив гдпн1есп можно удалить; соответственно мы упростим имя япн(еш до йпьаЫ, После соответствующих соглашений алгоритм принимает вид (3.43).
Предикат «приемлемо» можно изобразить в виде конъюнкции згпп(в и ссоре («усгойчнвыд»), где Иаосе— функция, которую еще надо будет уточнить. ргоеейиге сгу(гп: гпап); чаг г: галГс; и". полчан; 'вей1и Гог г: = 1 $о п йо Ьери ы:-=- пп1г[пьг[; И всае1е[чс[ УХ хГаЫс 1йев Ьей(в хаяси[:= в; у[и[:- пг; йгпй(е[п1: = га(ге; 1« гп < и «йеи ггу(снес(гп)) ' (ЗАЗ) е(ае запись успюйчивого лснозгесгпаа; ипк!е[п[:- ггне евй евй епй Здесь все еще заметно большое сходство с программой 3.5.
Теперь основная задача — уточнить алгоритм определения устойчивости. К сожалению, устойчивость нельзя представить таким же простьпя выражением, как безопасность позиции ферзя в программе 3,5 Нужно прежде всего иметь в виду, что устойчивость по определению следует нз сравнения предпочтений, нли рангов. Но ранги мужчин и женщин нигде в наших описанных до сих пор данных явно ие представлены.
Конечно, ранг женшины го с точки зрения мужчины гп можно вычислить, но лишь с помощью трудоемкого поиска ш в штг[т[. Так как вычисление устойчивости — очень частое действие, желательно, чтобы эта информация была более доступна. Для этого мы будем использовать две матрицы гтис аггау[тап, шотап[ о$ гапй; гшпп аггву[июпсап, топ[о(гапй; д' ранга авнме 'алиаригым ' 17В такие, что гтю(т, ю] означает ранг;с-й женщш1ы в списке предпочтений т-го мужчины, а гьат(-а, т] — ранг т-го мужчины в списке ю-й женщины.
Ясно, по значения этих вспомогательных массивов постоянны и могут быть получены с самого начала пз значений ютг и игюг. Значение преднката згаЫа (устойчивый) теперь вычисляется в строгом соответствии с его исходным определением. Вспомним, что мы исследуем возможность брака между >и и аа, где ю = ютг(т, г], т. е. ю имеет ранг г в т-и списке предпочтений.
Будучи оптпмнстамп, мы вначале предполагаем, что устойчивость сохранилась, а затем пытаемся лайте возможные источники непрцягностей. Где они могут таиться? Есть две симметричные возможности; 1. Может существовать женщина рю, предпочтптельцая для т по сравнению 'с к', которая сама предпочитает т своему мужу. 2. Может существовать мужчина рт, предпочтительный для ю по сравнению с и, который сам предпочитает ю своей жене. Исследуя источник неприятностей 1, мы сравниваем ранги гнат(рю, т] п ггрт(рю, р(рю]] для всех женщин, которых ~и предпочитает своей невесте ю, т.
е. для всех рвт =;сок(т, 1], таких, что 1( г. Мы знаем, что все эти жешцпны:,жс выданы замуж, так как сслн бы какая-то из них была еще одинока, т выбрал бы ее раньше, чем ю. Этот процесс проверки можно сформулировать в виде простого линейного поиска; з означает устойчпвосттк х:= ггие; и';= 1, тт)и]1е Г1 < г) Л з йо Ьей1п рм;= нтнГ(,,1; 1:= 1т11 рй —.лии1е(рЯ 1пеп х: = гнт(ри, т] ) гвт(р1а, у(ргк]] спд (З.45) Исследуя источник неприятностей 2, мы должны рассмотреть всех мужчин рги, которых га предпочитает своему предполагаемому партнеру т, т. е, всех рт = тшг( ', 1], таких, что 1< гиии(ш,т].
)лак н прн исследовании источника 1, нужно сравнивать ранги гтю(рт, ю] и гицц(рп, х(рт]], Но здесь нужно быть впимательнымп, чтобы не производить сравнений с участием х(рт], где рт еще пе женат. Необходимой предосторожностью будет проверка рт т, поскольку мы знаем, что все мужчины, предшествующие т, уже женаты. Весь алгоритм представлен в программе З.б.
Табл. З,З содержит множество входных данных, соответствуюгцнх масси- 8.б. Задача об устобсивовх браках !79 таблииа З.З. Пример входных данных для задачи об устойчивых браках 1 2 3 4 5 б 7 8 Ранг 2 6 5 4 3 2 Б 5 2 4 1 В 8 4 2 1 3 4 6 2 7 5 2 6 4 6 3 В 4 2 8 6 2 5 7 5 3 1 2 8 1 2 5 2 4 7 1 3 1 4 8 1 3 8 5 6 7 2 6 2 8 4 1 ВаМ Ырил И тотртд И НаКОНЕц, В табЛ. ЗА ПрИВЕдЕНЫ дЕВятЬ ПО- лученных решений. Таблица 3.4. Рещеиия задачи об устойчивых браках Кв Хт ХВ Хс Хв ХВ Хт Хв с4И ГЕР С ! 7 4 3 8 ! 2 2 4 3 8 ! 3 2 4 3 1 7 4 6 4 3 8 ! 5 6 4 3 ! 7 6 6 3 4 8 ! 7 6 3 4 ! 7 8 3 6 4 8 1 9 3 6 4 ! 7 Решение 'с=коневе ство прооеровс !стоп пщостн. Рощювне !=рещение, оптнмвленое дле мужнин.
Ранение В=рещение, оптимальное для женщнн. По своей сути этот алгоррпм основан на простой схеме поиска с возвратом. Его эф рективность зависит в основном от удачного построения схемы усекаиия дерева решения. г1есколько более быстрый, но более сложный и менее понятный алгорзпм предложен Мак-Вити и уилсоном (3.!, 3.21, которые, кроме того, распространили его на случай множеств (мужчин и женщвн) неодинакового размера, Мужчина 1 ввтбнраег жсттщину 7 2 4 3 3 4 3 5 8 б 8 7 2 8 6 Женищна 1 выбирает мужчину 4 2 8 3 6 4 3 5 6 б 2 7 3 8 7 3 6 В 1 '7 8 5 7 5 8 7 6 1 7 4 3 1 1 У 5 7 5 3 8 1 3 6 7 4 3 4 7 6 8 8 5 7 2 7 4 6 в 5 6 3 5 2 6 16 5 7 6 22 5 8 6 31 5 7 2 26 5 8 2 35 5 7 2 29 5 8 2 38 5 7 2 34 5 8 2 43 32 21 27 449 20 59 22 62 15 47 20 143 13 47 18 758 11 34 ргоагат нсагг1а8о (!при,оссгрссс); ! задана о стабильных браках) сопи! и —.= 8; гу ре тап:. = 1 ..
и; и опсасг - 1, . и; гап!с:--. 1 .. и; уаг нс: тал; и: потап; т: гсссс!с; ггтг: агапу [тап, гап!с) еК сстсссссс,' псит: аггау [потап, сап!с)оу тап! ст«". иггау [тап, «отан) а1 сап!с; гюн: агапу [потап, асан) оу гап!с; х: агапу [тасс) оу и'отан; у; аггеу [««отан[ ос тап; юсс8!с".' аггау [и опсасс) аЕ Ьоо!стс; ргосес!иге рпт; гаг нс: тап; ын, г«:: угс1ерег! Ъсра гпс:. О; ги с .—.
О,' гог т:== 1 !о и де Ьера «гсге (х[т):4); гт:: . гт .,'- гти[сн,х[сгс)); ги:==- гсг + гнт[хс[нс)гн~! еас1; от!се!сс (гпс:З,гн:4); еай [рг1нс); ргосес!аге Ггу(пс: тап); тзг г: гап!с; «с: и'отан; Уиас!!оа гсаЬ1о: Ьоо1еап; гаг рп~: вап; рсг: !гота«; с', Ьп: гоп!с; г, Ьоо1сст; Ъера г .'== ггссе; 1:= — 1; ггЫ!е (1<г) с'с ю с!о Ъе8!а рис:= сгпсг[нс,1); 1:=-= 1+1! М вЂ” сг1«81о[рв] 1Ьесп г:-'= г«нс[рсс,т[ > гсга[рсе,у[рсс)[ еаза; 1;--= 1,' Ьп:=- гсггп[«',пс); егЪ!!е (1<1!т) Л ю да Ъе8!а рт:=- тссг[сгД; 1;.= 1+ 1; !1рлс < пс 1Ьеа г:= гпсь[рт,ж) > сппгс[рсн,х[рсн)) еай; г(аЫе: г еас! (г!аЫе) 1 Ьерп (ггу) Хог г;= 1 !о и Ьо Ье8!а ис:=- ггнсс [нбг); Дб. Задача об рогойчаоьгх браках И егиб1е[и) ГЬев И егаЫе тйев Ьеяш х[т);= !р; у[и):= т; егий)е[!г):= «а1ге; Ы т < и тйев ггу(еиее(т)) е!!герг!пг; егщ1еЯ: = ггие евй ево ев$ [ггу); Ьей(в [основная программа) хог т:= 1 то и оо $ог г:=- 1 то и йо Ьея1в гебу(!гтг[т,г)); г!ни[т,гртг[т;гД:= и ево; 1ог !а:= 1 то и оо 1ог г:= 1 $о и йо Ьея(в геой(тнт[чг,г)); гит[!г,тат[и!,гД:= г евй; Ког !г:= 1 го ч йо х!пб1е[!р):=.
Ггие; ггу (!) евй . Программа З.б. Устойчивме браки. Алгоритмы такого вида, как в двух последних примерах, дающие все возможные решения задачи (при определенных огранкчениях), часто используются для ныбора одного или нескольких решений, которые в каком-то смысле являются оптимальными. В данном примере можно было бы, допустим, интересоваться решением, которое в среднем больше удовлетворяет мужчин, пли женшин, или всех. Отметим, что в табл, 3.4 указаны суммы рангов всех женщи; с точки зрения их мужей и суммы рангов всех мужчин с точки зрения нх жен. Это значения гт= 2 гтш[т, х[т1[, гн!= ~, ггвт[х[т), т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
