а singlelw] then if stable then

begin xlm] := w; y[w] := m; singlфv] .- false; if tn < n then try{succ(m)) else print; single{w] true

end [try] ;

begin [основная программа] for /и := 1 to и do for r :== 1 to и do

begin read(yvmr[m,rj); rmwlm,wmr[m;r]] I-Y end;

for w ;= 1 to и do fM r := 1 to и do

begin read(t}vr[w,r]); rwm[w,mwr[w,r]] :== r end ;

for w := 1 fo n do .y/ng/w] :- true;

try (I) end .

Программа 3.6. Устойчивые браки.

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

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

п п

гт= rmw[m, х[т]], rw= rwm[x[m], т]. (3.46)

m=l m=l

Решение с наименьшим значением гт называется устой- Ивым решением, оптимальным для мужчин, а с наименьшим fw устойчивым решением, оптимальным для женщин. При збранной стратегии поиска первыми вычисляются решения, орошие с точки зрения мужчин, а благоприятные для жен- н решения даются в конце работы. В этом смысле алго-Ритм ориентирован на сильный пол. Но его можно быстро

s.7. задача оптимального выбора

Наш последний пример алгоритма с возвратом - это логи-ческое обобщение двух предыдущих алгоритмов, которые строятся по общей схеме (3.35). Вначале мы использовали принцип возврата для нахождения одного решения дайной задачи. Это было показано на примерах хода коня и задачи восьми ферзях. З^тем-мы задались Целью найти все реше-ния задачи; примерами были восемь ферзей и устойчивые браки. Теперь мы хотим найти оптимальное решение.

Для этого нужно получить все возможные решения и в процессе их получения оставлять только то, которое в некотором смысле является оптимальным. Если предположить, что оптимальность определена с помощью некоторой функции /( ), принимающей положительные значения, то алгоритм можно получить из схемы (3.35) заменой оператора течап решения на оператор

if f(solution) > f{optimum) tiien optimum := solution (3.47)

В переменной optimum хранится лучшее из полученных до сих пор решений. Разумеется, ее нужно должным образом инициировать; кроме того, значение f (optimum) принято хранить в другой переменной, чтобы избежать ее частого перевычисления.

В качестве примера общей задачи поиска оптимального решения мы выбираем следующую важную и часто встречающуюся задачу: найти оптимальную выборку из заданного множества объектов, подчиненную некоторым ограничениям. Выборки, составляющие приемлемые решения, строятся постепенно, с помощью исследования отдельных объектов базового множества. Процедура try описывает процесс исследования пригодности объекта для включения в выборку; она вызывается рекурсивно при переходе к следующему объекту, пока все объекты не будут рассмотрены.

Мы видим, что из рассмотрения каждого объекта можно сделать два возможных вывода: либо включить объект в текущую выборку, либо не включать его. Поэтому здесь не удастся использовать операторы цикла; вместо этого нуЖН .явно описать оба случая. Это показано в (3,48); предполо

изменить, систематически поменяв ролями мужчин и женщц^ т. е. заменив mwr на wmr и rmw на rwm.

Здесь мы не будем далее обобщать эту программу, а оста вим поиск оптимального решения в качестве очередного J последнего примера алгоритма с возвратом.

focedure try{i: integer); ., . . - .

включение приемлемо then * begn включить i-й объект;

if i<n then try{i.-\-\) else:проверить-Оптимальность; удалить i-й объект v (3.48j

-gndr -

о. ii невключение приемлемо then , if t < n then/г^/(/+ 1) else проверить оптимальность,

Из этой схемы видно, что всего имеютсй 2 возможные выборки; поэтому ясно, что критерии приемлемости должны значительно ограничить количество рассматриваемых возможностей. Для пояснения возьмем конкретный пример: пусть каждый из п объектов ai, ..an обладает весом из и ценностью v. Оптимальным пусть считается множество с наибольшей суммарной ценностью компонент, а ограничением пусть служит их предельный общий вес. Эта задача хорошо знакома всем отправляющимся в путешествие, которые упаковывают чемоданы, стараясь так выбрать п предметов, чтобы их общая ценность была максимальной, а об-ший вес не превышал какого-то допустимого предела.

Теперь мы можем решить, как предстарить известные факты в виде данных. Из вышесказанного легко получаются такие описания: . .

type index ~ 1 ..п;

object = record w,t>: integer &ай var a: array [index] of object; (3.49)

limw, totv, maxv: integer; \ , .

s, opts: set of index

Переменные limw и totv обозначают предельный вес и общую ценность всех п объектов. Фактически эти два значения в течение всего процесса отбора постоянны; через s обозначается текущая выборка объектов, где каждый объект представлен своим именем (индексом); opts есть оптимальная выборка. Полученная до сих пор, а maxv-.ее ценность..

Теперь посмотрим, каковы критерии приемлемости объекта Для текущей выборки. Когда речь идет о включении, объект ojKHo включить в выборку, если он удовлетворяет допусти-**ому весу. Если же не удовлетворяет, то можно прекратить Попытки добавлять новые объекты в текущей выборке. Но сли рассматривать невключение, то критерием приемлемо- 8, т. е. возможности ; продолжать построение текущей

что объекты пронумерованы 1.2,..., я: