2.1.6. Задача о рюкзаке (перебор вариантов)

Постановка задачи. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес w_i и стоимость v_i (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k_i, тогда требуется максимизировать v₁*k₁+v₂*k₂+...+v_n*k_n при ограничениях w₁*k₁+w₂*k₂+...+w_n*k_nW, где k_i - целые (0k_i[W/w_i]), квадратные скобки означают целую часть числа.

Рассмотрим простой переборный вариант решения задачи, работоспособный только для небольших значений n (определить, для каких?). Итак, данные:

Сonst MaxN=????;

Var n,w:integer;{количество предметов, максимальный вес}

Weight,Price:array[1..MaxN] of integer;{вес, стоимость предметов}

Best,Now:array[1..MaxN] of integer;{наилучшее, текущее решения}

MaxPrice:LongInt;{наибольшая стоимость}

Решение, его основная часть - процедура перебора:

Procedure Rec(k,w:integer;st:LongInt);

{k - порядковый номер группы предметов, w - вес, который следует набрать из оставшихся предметов, st - стоимость текущего решения}

var i:integer;

begin

if (k>n) and (st>MaxPrice) then begin {найдено решение}

Best:=Now;MaxPrice:=st; end

else if k<=n then

for i:=0 to w div Weight[k] do begin

Now[k]:=i;

Rec(k+1,W-i*Weight[k],st+i*Price[k]);

end;

end;

Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.

2.1.7. Задача о коммивояжере (перебор вариантов)

Постановка задачи. Классическая формулировка задачи известна уже более 200 лет : имеются n городов, расстояния между которыми заданы ; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).

Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.

Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.

Структуры данных.

Const Max=100;

Var A:array[1..Max,1..Max] of integer;{Матрица расстояний между городами}

B:array[1..Max,1..Max] of byte;{Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А }

Way, BestWay:array[1..Max] of byte;{Хранится текущее решение и лучшее решение}

Nnew:array[1..Max] of boolean;{Значение элемента массива false говорит о том, что в соответствующем городе коммивояжер уже побывал}

BestCost:integer;{Стоимость лучшего решения}

Идея решения. Пусть мы находимся в городе с номером v. Наши действия.

Шаг 1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.

Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных. Если результат сравнения положительный, то значения BestCost и BestWay следует изменить и выйти из этой ветви дерева перебора .

Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way .

Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.

Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.

Пример. Ниже приведены матрицы А и В (после сортировки элементов каждой строки матрицы А).

Примечание. Можно использовать любой из методов сортировки, но авторы предпочитают использовать метод Хоара[1] из-за определенного изящества в его реализации. Рекурсивная логика плюс смена направления изменения индекса в одной циклической конструкции.

A B

@	27	43	16	30	26
7	@	16	1	30	25
20	13	@	35	5	0
21	16	25	@	18	18
12	46	27	48	@	5
23	5	5	9	5	@

4	6	2	5	3	1
4	1	3	6	5	2
6	5	2	1	4	3
2	5	6	1	3	4
6	1	3	2	4	5
2	3	5	4	1	6

Примечание. Символом @ обозначено бесконечное расстояние.

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

Итак, запись логики.

procedure Solve(v,Count:byte;Cost:integer);

{v - номер текущего города; Count - счетчик числа пройденных городов; Cost - стоимость текущего решения}

var i:integer;

begin

if Cost>BestCost then exit;{Стоимость текущего решения превышает стоимость лучшего из ранее полученных }

if Count=N then begin Cost:=Cost+A[v,1];Way[N]:=v;{Последний город пути. Доформировываем решение и сравниваем его с лучшим из ранее полученных.}

if Cost<BestCost then begin

BestCost:=Cost;BestWay:=Way;

end;

exit;

end;

Nnew[v]:=false;Way[Count]:=v;{Город с номером v пройден, записываем его номер в путь коммивояжера}

for i:=1 to N do if Nnew[B[v,i]] then

Solve(B[v,i], Count+1,Cost+A[v,B[v,i]]); {Поиск города, в который коммивояжер может пойти из города с номером v}

Nnew[v]:=true; {Возвращаем город с номером v в число непройденных}

end;

Первый вызов - Solve(1,1,0).

Разработка по данному «шаблону» работоспособной программы - техническая работа. Если Вы решитесь на это, то есть смысл проверить ее работоспособность на следующем примере (матрица А приведена ниже). Решение имеет вид 1 8 9 2 5 10 6 7 4 3 1, его стоимость 158.

@	32	19	33	22	41	18	15	16	31
32	@	51	58	27	42	35	18	17	34
9	51	@	23	35	49	26	34	35	41
33	58	23	@	33	37	23	46	46	32
22	27	35	33	@	19	10	23	23	9
41	42	49	37	19	@	24	42	42	10
18	35	26	23	10	24	@	25	25	14
15	18	34	46	23	42	25	@	1	32
16	17	35	46	23	42	25	1	@	32
31	34	41	32	9	10	14	32	32	@

Оцените время работы программы. Если у Вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода. Заметим, что набор 2500 чисел - утомительное занятие и разумная лень - «двигатель прогресса».