Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 32
Текст из файла (страница 32)
(346) т=- ! !к 1 Решение с наименьшим значением гт называется устойчивым решением, оптимальным для мужчин, а с наименьшим гш — устойчивым решением, оптимальным для женшин. При избранной стратегии поиска первыми вычисляются решения, хорошие с точки зрения мужчин, а благоприятные для женщин решения даются в конце работы. В этом смысле алгоритм ориентирован на сильный пол. Но его можно быстро 8. Рекурсивные алгоригиы 182 изменить, систематически поменяв ролями мужчин и женшин, т.
е. заменив тшг на штг и гтш на гшт. Здесь мы не будем далее обобщать эту программу, а оставим поиск оптимального решения в качестве очередного и последнего примера алгоритма с возвратом. З.У. ЗАДАЧА ОПТИМАЛЬНОГО ВЫВОРА Наш последний пример алгоритма с возвратом — это логическое обобщение двух предыдуших алгоритмов, которые строятся по обшей схеме (3.35). Вначале мы использовали принцип возврата для нахождения одного решения данной задачи.
Это было показано на примерах хода коня и задачи о восьми ферзях. Затем мы задались целью найти все решения задачи; примерами были восемь ферзей н устойчивые браки. Теперь мы хотим найти оптимальное решение. Для этого нужно получить все возможные решения и в процессе их получения оставлять только то, которое в некотором смысле является оптимальным.
Если предположить, что оптимальность определена с помощью некоторой функции )'(з), принимающей положительные значения, то алгоритм можно получить из схемы (3.35) заменой оператора «печать решению> па оператор И 1(зо1и11оп) ) )(ор11тит) Яеп ор11тит:= зо1и11оп (3.47) В переменной орбтит хранится лучшее нз полученных до сих пор решений. Разумеется, ее нужно должным образом инициировать; кроме того, значение 1(ор11тит) принято хранить в другой переменной, чтобы избежать ее частого перевьшисления. В качестве примера об1цей задачи поиска оптимального решешгя мы выбираем следующую важную н часто встречающуюся задачу: найти оптимальную выборку из заданного множества объектов, подчиненную некоторым ограничениям. Выборки, составляющие приемлемые решения, строятся постепенно, с помощью исследования отдельны.', объектов базового множества.
Процедура 1гу описывает процесс исследования пригодности объекта для включения в выборку; она вызывается рекурсивно при переходе к следующему объекту, пока все объекты не будут рассмотрены. Мы видим, что нз рассмотрения каждого объекта могкно сделать два возможных вывода: либо включить объект в текущую выборку, либо не включать его, Поэтому здесь не удастся использовать операторы цикла; вместо этого нужно явно описать оба случая. Это показано в (3.48); предполо- 8,7. Задача аатамальнога аьчеара !!з э1ой схемы видно, что всего имеются 2" возможные выварки; поэтому ясно, что критерии приемлемости должны значительно ограничить количество рассматршаасмых возможностей, Для пояснении возьмем конкретный пример: и;сть каждый пз и обьектов аь ..., ач обладает весом ю и ценностью о.
Оптимальным пусть считается множество с наибольшей суммарной ценностью компонент, а ограничением п) сть служит и: предельный общий вес. Эта задача хорошо знакома всем отправляющимся в путешествие, которые упаковывают чемоданы, стараясь так выбрать и предметов, чтобы нх общая ценность была максимальной, а общий вес нс превышал какого-то допустимого предела. (еперь мы можем решить, как представить известные факты в виде данных. )4з вышесказанного легко получаются такие описания: 1уре тг)ех = ! ..
и; оЪ)ест =- гесогй ы,е: Ьпеяег еп4 чаг а: аггау (тч)ех) о1 оЪ|ес1; 1)ппа, гоге, тахе: 1п1ееет; в, оргг: зс1 о1 ии)ех (349) Переменные (~тго и 1ого обозначают предельный вес и общую ценность всех и объектов, Фактически эти два значения в течение всего процесса отбора постоянны; через з обозначается текущая выборка объектов, где каждый объект представлен свопы именем (индексом); ор)в есть оптнмальпая выборка, пол)ченная до сих пор, а тахо — се ценность. Теперь посмотрим, каковы критерии приемлемости объекта для текущей выборки. Когда речь ндст о включении, объект можно включить в выборку, если ои удовлетворяет допустимому весу. Если же не удовлетворяет, то можно прекратить попытки добавлять новые обьекты в текущей выборке. Но если рассматривать невключение, то критерием приемлемости, т, с.
возможности продолжазь построение текущей жим, что объекты пронумерованы 1, 2, ..., п: ргосеч(иге 1гр(1: )п1еоег); Ьец!п 1: И включение приемлемо 1Ьеп Ьен!и включить 1-и' объект; И г' < п 1Ьеп )гу(1+ 1) е1зе проверить оптимальность; Молить 1-и' объект (3.48) епб; 2: И невключение приемлемо 1Ьеп И 1 < п 1Ьец )гу(1+ 1) е!ае проверить апти.яальность епб ргопгаа ве!всИоп (!при«,ои«рв); (поиск оптимальной вьсборки обьсюпов при ограничениях) сепе! и = 10; Фуре гобсх = 1 .. и; ой!ес! тесогй е,!г! !и!вас«епв; ча' 1: !по!сх; а: актау 1йиуех) еу ой!ее!1 !!т!г, гот, тахо: уи«ваег! п1, !г2, !гЗ: !и!вкег! кч ар!в: веФ оу упйех! гл актау (йоо!сап) е! сйаг; увосебпге !гу(!! йнусх; !ь',ае: й!!еусг); час ае1: инсбсг; ЬеФп ! попытка включения объекта !) Ы М+ аЩ .!Г, !!тЫ !ЬЕП Ьеп)п в:= в+ Я; Ы ! < и !Ьеп ггу(!+1, гн+а[!)я«, аг) с)ве Ы аю = тахе !Ьеп Ьеп)п тахе:= ае; ар!я:= в епб; в:= в — И епб; (попытка исключения обьвкта !) ог1.; — ае — оТ е1 Ы ае! > тахе Йеп Ьеа!пЫ ! ( и !Ьепну(!+1, !!е, ао1) сЫе Ьеп1п тахе:= ае1; ор!г: - в епв епб епй (ггу); Ьеп!п го!е ! 0; !ег 1: 1 1о и йо п1!Ь а(!) ао Ьек!п гсвг!(чр)! !ого 1= йбе + е епй; геаб(ь10«2,нЗ) ! х(ггие);= 'е'; в(уа!ге):=-- ' '; и«!гв( ччеинг )! Хо« 1:- 1 1о и йо п'«!!в (а!!) лг: 4)1 ь г«!в!и; !ег!!в (' чиле '); уог 1:=- 1 1о и бо н'г!гс (аД л'; 4); нпгс!и; кереа$ !йпп:=- !«1; !«кохе:= 0; в .= ", ); ар!в:= 1); 1вб 3.7.
Задача оп»анального выбора ггу(1,0, гоп 7.' нтйв((йпи); (ог 1':== 1 1о и йо ипгг(' итйг(п; и1:= ьг1 + ьо2 ив1П нг1 > тгЗ евй ', г(1 1п оры)); Программа 3.7. Оптимальная амбарам Эти два значения удобно представить в виде параметров процедуры (гу. Условие «включение приемлемо» в (3.48) теперь можно еформулировать как !ге+а Ц.гв«йтгв (3.50) а последующую проверку оптимальности — как П ао > тахо 1Ьеп Ьеп)п (запись нового оптимума) орИ:=з; тахо:=ао епб (3.51) Последнее присванвание связано с тем соображением, что достижимое значение будет получено после просмотра всех л объектов.
Условие «невключение приемлемо» в (3.48) выражается как ао — а Ц. о > тахо (3.52) Так как позднее оно снова используется, значение ав— — а и м присваивается переменной ао!, чтобы избежать повторного вычисления. Всю программу полностью теперь можно получить нз (3.48) с помощью (3.52), добавив соответствующие операторы инициации глобальных переменных, Следует отметить, что здесь удобно используются операции над множествами, выборки, будет возможность получить без этого объекта такую общую ценность выборки, которая была бы не меньше получен~ого до снх пор оптимума. Ведь иначе продолжение поиска, хотя и будет давать какие-то решения, никогда не приведет к оптимальному, следовательно, на этом пути бесполезен какой-либо дальнейший поиск. С учетом зтнх двух условий мы определяем, какие существенные величины нужно вычислять для каждого шага в процессе отбора: 1.
Общий вес 1ш выборки з, полученной до сих пор. 2. Общую ценность ао текущей выборки з, которой еще можно достичь. 8. Рекурсивные алгоритмы 186 Результат выполнения нрггграммы 3 7 с заданными предельными весами от 1О до 120 показан в табл. 3.5. Таблица 8.5. Пример результата работы программы оптимальной выборки Вес 10 11 12 13 14 15 16 17 18 1Э Значение 18 20 17 18 25 21 27 23 25 24 10 « 20 30 40 50 е» 60 е е 70 е а 80 а ч 80 а 100 е е 110 « е 120 а УП Р АЖН ЕН ИЯ 3,!. (Хаиойские башни.) Даны три стержня и и дисков разного размера, Диски можно надевать на стержни, строя таким образом «башни». Пусть вначале диски находятсв на стержне Л в порядке убывающего размера, как показано на рис. 3,!О для и = 3.
Нужно переместить п ,УГ д~УУ~1~Й Рис. 3.!О. Ханойские башни, дискон на стержень С так, чтобы они остались в том же порядке. Этого нужно добиться, соблюдая следующие правила: !. На каждом шаге ровно один диск перемещается с одного стержня на другой. 2.
Диск большего размера нельзя помещать па меньший 3. Стержень В можно использовать в качестве промежуточного. Постройте алгоритм, который выполняет эту задачу Заметим, что баозню удобно рассматривать как состоящую из одного диска иа самом верху и из башни, состоящей нз остальных дисков. Опншнте этот алгоритм в виде рекурсивной программы. Упражнения 137 3.2. Напишите процедуру, которая Формирует все и! перестановок и элементов аь ..., а, 'и з((и, т. е без использования другого массива.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
