33. Задача об оптимальной выборке (о рюкзаке) и ее решение методом ветвей и границ

 

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

IF f(решение) > f(optimum) THEN optimum := решение END;                                                                   (3.47)

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

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

 Мы видим, что при рассмотрении каждого объекта (в предыду­щих примерах мы называли их кандидатами) возможны два зак­лючения, а именно либо включать исследуемый объект в теку­щую выборку, либо не включать. В такой ситуации оператор цик­ла уже не годится, вместо этого нужно явно описать оба варианта. Этот процесс и описан ниже, причем объекты здесь пронумеро­ваны 1, 2,..., п:

PROCEDURE Try(i:  INTEGER);

BEGIN

 IF включение приемлемо THEN включение i-го объекта;

            IF i < n THEN Try(i+1)  ELSE проверка оптимальности END;

            исключение i-го объекта                                                                             (3.48)

END;

IF приемлемо невключение THEN

IF i < n THEN Try(i+1) ELSE проверка оптимальности END

 END

 END Try;

 Из схемы (3.48) видно, что существует всего 2n возможных вы­борок, поэтому нужно использовать такой критерий приемлемо­сти, который значительно бы сократил число перебираемых кан­дидатов. Для пояснения этого процесса возьмем конкретный при­мер построения выборки. Пусть каждый из n объектов а1 ,..., an характеризуется весом и ценностью. Оптимальной назовем вы­борку с максимальной суммой ценностей и суммой весов, огра­ниченной некоторым пределом. С такой проблемой сталкивается любой путешественник, упаковывающий чемоданы и стремящий­ся выбрать так n предметов, чтобы ценность их была оптималь­ной, а общий вес не превышал какого-то допустимого предела.

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

TYPE  index  = [1..n];

objectRECORD weightvalue:   INTEGER END;

VAR      obj:  ARRAY index OF object;                                                                                  

limwtotvmaxv:  INTEGER;

s,   opts:   SET OF index;

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

 Каковы же критерии приемлемости объекта для текущей вы­борки? Если речь идет о включении, то объект можно включать в выборку, если он подходит по весовым ограничениям. Если он не подходит, то попытки добавить еще один объект в текущую выборку можно прекратить. Если, однако, речь идет об исключе­нии, то критерием приемлемости, т. е. возможности продолжения построения текущей выборки, будет то, что после данного исклю­чения общая ценность будет не меньше полученного до этого мо­мента оптимума. Ведь если сумма меньше, то продолжение поис­ка, хотя он и может дать некоторое решение, не приведет к опти­мальному решению. Следовательно, дальнейший поиск на текущем пути бесполезен. Из этих двух условий мы определяем величины, которые нужно вычислять на каждом шаге процесса отбора:

1.       Общий вес tw выборки, полученной к данному моменту.

2.       Общую ценность av текущей выборки, которую можно еще достичь.

Эти две величины удобно представлять как параметры про­цедуры Try. Условие включение приемлемо в (3.48) можно теперь сформулировать так:

tw + a[i].weight £ limw,                                                                                                                                              (3.50)

И последующая проверка на оптимальность выглядит следующим образом:

IF av > maxv THEN (* новый оптимум,  его запись *)

opts  :=  s;  maxv  := av                                                                                             (3.51)

END;

Последнее присваивание основано на том соображении, что до­стижимое значение будет получено только после обработки всех объектов. Условие приемлемо невключение в (3.48) выражается так:

av  -  а[i].value > maxv.                                                                                                                                             (3.52)

Поскольку полученное значение av - a [i].value вновь использу­ется, оно, чтобы избежать повторного вычисления, "сохраняется" в переменной аv1.

Из схемы (3.48) и фрагментов (3.49)-(3.52) получаем, добавив соответствующие операторы инициации глобальных переменных, всю программу целиком. Следует заметить, что для включения и исключения из множества s здесь очень удобно пользоваться операциями над множествами. В табл. 3.5 приводятся результа­ты работы программы (листинг 3.7) с допустимыми весами от 10 до 120.

Таблица 3.5.   Результаты работы программы оптимального выбора

 

Вес

10

11

12

13

14

15

16

17

18

19

 

Ценность

18

20

17

19

25

21

27

23

25

24

 

10

*

 

 

 

 

 

 

 

 

 

18

20

 

 

 

 

 

 

*

 

 

 

27

30

 

 

 

 

*

 

*

 

 

 

52

40

*

 

 

 

*

 

*

 

 

 

70

50

*

*

 

*

 

 

*

 

 

 

84

60

*

*

*

*

*

 

 

 

 

 

99

70

*

*

 

 

*

 

*

 

*

 

115

80

*

*

*

 

*

 

*

*

 

 

130

90

*

*

 

 

*

 

*

 

*

*

139

100

*

*

 

*

*

 

*

*

*

 

157

110

*

*

*

*

*

*

*

 

*

 

172

120

*

*

 

 

*

*

*

*

*

*

183

 

Такая схема с возвратами, использующая некоторые ограниче­ния для уменьшения роста потенциального дерева поиска, назы­вается алгоритмом ветвей и границ.