Часть1--------------------

цикл от i = 1 до V // формирование таблицы оптимального дохода для грузов типа 1

x[1, i] = i/boxV[1]

x1[1, i] = x[1, i]

f[i] = x[1, i]*boxC[1]

цикл от i = 2 до N // цикл по количеству типов грузов

Vi=boxV[i]

Ci=boxC[i]

цикл от j = 1 до V // цикл по объему упаковки

maxKol = 0; maxC = f[j]

если Vi <= j то

z = j/Vi // максимальное количество -го типа груза в объеме j

часть2---------------------

цикл от l = 1 до z // цикл нахождения максимальной стоимости

если (maxC < (Ci*l+f[j-l*Vi])) то

maxC = Ci*l+f[j-l*Vi]

maxKol= l

часть3---------------------

цикл от l=1 до i-1

x[l, j] = x1[l, j-maxKol*Vi]

x[I, j]=maxKol

часть4---------------------

цикл от l=1 до i

цикл от j=1 до V

x1[l, j]=x[l, j]

цикл от l=1 до V // цикл подсчета общей стоимости

sum = 0

часть5---------------------

цикл от j=1 до j<=i

sum = sum + x[j][l]*boxC[j]

f[l]=sum

В данном алгоритме части 1, 3, 4, 5 зависят только от , и их трудоемкость может быть подсчитана заранее , , ,

Трудоемкость части2 данного алгоритма в равна среднем элементарных операций.

Учитывая циклы по количеству типов грузов, по объему упаковки и цикла подсчета общей стоимости получаем среднее количество элементарных операций для данного алгоритма:

.

10. Метод ветвей и границ

Алгоритм ветвей и границ хорошо работает в задаче коммивоя­жера, рассмотренной в разделе 8.1.1. В данном разделе изложение будет вестись на примере задачи коммивояжера.

Метод, известный как метод ветвей и границ, исследует древовидную модель простран­ства решений. Применим для широкого круга дискретных комбина­торных задач. Алгоритмы ветвей и границ ориентированы в большей степени на оптимизацию. Например, в решаемой задаче определена числовая функция стоимости для каждой из вершин, появляющихся в дереве поиска. Цель — найти конфигурацию, на которой функция стоимости достигает максимального или минималь­ного значения.

Напомним, что задача заключается в нахождении в торговом участке коммивояжера тура из N городов с наименьшей стоимостью. Каждый город входит в тур только один раз. В терминах графов в графе городов надо найти покрывающий цикл наименьшей стоимости. Имеется матрица С, каждый элемент которой c_ij равен стоимости (обычно в единицах времени, денег или расстояния) прямого проезда из города i в город j. Задача называется симметричной, если c_ij = c_ji для всех i и j, т. е. если стоимость проезда между каждыми двумя городами не зависит от направления. Предположим, что сii=∞ для всех i.

Алгоритмы ветвей и границ для задачи коммивояжера могут быть сформулированы разными способами. Авторы излагаемого алгорит­ма - Литл, Мерти, Суини и Карел. Это своего рода классика [1].

Во-первых, рассмотрим ветвление. На рис. 10.1, а показана мат­рица стоимостей для асимметричной (несимметричной) задачи комми­вояжера с пятью городами, представленной на рис.10.1, 6. Обратите внимание на то, что используется ориентированный граф, чтобы ука­зать стоимости, так как стоимость проезда из города i прямо в город j не обязательно такая же, как стоимость проезда из города j в город i. Корень поискового дерева будет соответствовать множеству «всех возможных туров», т. е. эта вершина представляет множество всех 4! возможных туров в данной задаче с пятью городами. В общем случае для любой асимметричной задачи с N городами корень будет представлять полное множество R всех (N—1)! возможных туров. Ветви, выходящие из корня, определяются выбором одного ребра, скажем (t,j). Наша цель состоит в том, чтобы разделить множество всех туров на два множества: одно, которое, весьма вероятно, содер­жит оптимальный тур, и другое, которое, вероятн о, не содержит. Для этого выбираем ребро (i, j); оно, как мы надеемся, в ходит в оп­тимальный тур, и разделяем R на два множества {i, j} и {i, j}. В мно­жество {i, j) входят туры из R, содержащие ребро (i, j), а в {i, j} — не содержащие (i,j).

	1	2	3	4	5
1	∞	25	40	31	27
2	2	∞	17	30	25
3	19	15	∞	6	1
4	9	50	24	∞	6
5	22	8	7	10	∞

а)

б)

Рис. 10.1. Задача коммивояжера: (а) матрица стоимостей; (б) граф из пяти городов.

П редположим, в данном примере производится ветвление на ребре (i, j)=(3,5), имеющем наименьшую стоимость во всей матрице. Корень и первый уровень дерева пространства решений будут тогда такими, как показано на рис.10.2. Заметим, что каждый тур из R содержится только в одном множестве уровня 1. Если бы мы как-то могли сделать вывод, что множество {3,5} не содержит оптимального тура, то нам нужно было бы исследовать только множество {3, 5}.

З атем разделяем множество {3, 5} таким же образом, как и множе­ство R. Следующее по дешевизне ребро в матрице – это ребро (2, 1) со стоимостью c₂₁=5. Поэтому можно разделить множество {3, 5} на туры, включающие ребро (2, 1), и туры, не включающие этого ребра; это показано на уровне 2 на рис.10.2. Путь от корня к любой вершине дерева выделяет определенные ребра, которые должны или не должны быть включены в множество, представленное вершиной дерева. Например, левая вершина уровня 2 на рис.10.2 представляет множе­ство всех туров, содержащих ребро (3, 5) и не содержащих ребра (2, 1). Вообще, если X – вершина дерева, а (i, j) – ребро ветвления, то обозначим вершины, непосредственно следующие за X, через Y и Y. Множество Y обозначает подмножество туров из X с ребром (i,j), а множество Y – подмножество X без (i, j).

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

С каждой вершиной дерева мы связываем нижнюю границу стои­мости любого тура из множества, представленного вершиной. Вычис­ление этих нижних границ — основной фактор, дающий экономию усилий в любом алгоритме типа ветвей и границ. Поэтому особое внимание следует уделить получению как можно более точных границ. Причина этого следующая. Предположим, что мы построили конкрет­ный полный тур со стоимостью т. Если нижняя граница, связанная с множеством туров, представленных вершиной v_k, равна М≥т, то до конца процесса поиска оптимального тура не нужно рассматривать вершину v_k и все следующие за ней (почему?).

Основной шаг при вычислении нижних границ известен как при­ведение. Оно основано на следующих двух соображениях:

1. В терминах матрицы стоимостей С каждый полный тур содержит только один элемент (ребро и соответствующую стоимость) из каждого столбца и каждой строки. Заметим, что обратное утверждение не всегда верно. Множество, содержащее один и только один элемент из каждой строки и из каждого столбца С, не обязательно представляет тур. Например, в задаче, изображенной на рис.10.4 множество {(1,5), (5,1), (2,3), (3,4), (4,2)} удовлетворяет этому условию, но не образует тура.

2. Если вычесть константу h из каждого элемента какой-то строки или столбца матрицы стоимостей С, то стоимость любого тура при новой матрице С’ ровно на h меньше стоимости того же тура при матрице С. Поскольку любой тур должен содержать ребро из данной строки или данного столбца, стоимость всех туров уменьшается на h. Это вычитание и называется приведением строки (или столбца).

Пусть t — оптимальный тур при матрице стоимостей С. Тогда стоимостью тура t будет

Если С’ получается из С приведением строки (или столбца), то t дол­жен оставаться оптимальным туром; при С’ и

где z' (t) — стоимость тура t при С’.

Под приведением всей матрицы стоимостей С понимается следую­щее. Последовательно проходим строки С и вычитаем значение наи­меньшего элемента h_i каждой строки из каждого элемента этой строки. Потом то же самое делаем для каждого столбца. Если для некоторого столбца или строки h_i=0, то рассматриваемый столбец или строка уже приведены, и тогда переходим к следующему столбцу или строке.

Полученную в результате матрицу стоимостей назовем приведенной из С. На рис.10.3 показано приведение матрицы стоимостей, изобра­женной на рис.10.1, а. Значения h_i даны в конце каждой строки и столбца (строки и столбцы последовательно пронумерованы).

	1	2	3	4	5
1	∞	25	40	31	27	h1=25
2	2	∞	17	30	25	h2=5
3	19	15	∞	6	1	h3=1
4	9	50	24	∞	6	h4=6
5	22	8	7	10	∞	h5=7
	h6=0	h7=0	h8=0	h9=3	h10=0

h = 25+5+1+6+7+3 = 47

Рис.10.3 Приведение матрицы стоимостей, показанной на рис. 10.1, а.

Общее приведение составляет h=47 единиц. Следовательно, ниж­няя граница стоимости любого тура из R также равна 47, т. е.

z(t)=h+z’(t)≥h=47

так как z'(t)≥0 для любого тура t при приведенной матрице С’. Эта граница указана около корня дерева на рис.10.2.

По определению ребро (3, 5) содержится в каждом туре множе­ства {3, 5}. Этот факт препятствует выбору ребра (5, 3), так как ребра (3, 5) и (5, 3) образуют цикл, а это не допускается ни для какого тура.

Ребро (5, 3) исключаем из рассмотрения, положив с₅₃ = ∞ . Строку 3 и столбец 5 также можно исключить из дальнейшего рассмотрения по отношению к множеству {3, 5}, потому что уже есть ребро из 3 в 5. Часть приведенной матрицы стоимостей, показанной на рис.10.3, которая будет хоть сколько-нибудь полезна для дальнейшего поиска на множестве туров {3, 5}, показана на рис.10.4, а. Она может быть приведена к матрице стоимостей, показанной на рис.10.4, б с h = 15. Теперь нижняя граница для любого тура из множества {3, 5} равна 47+15=62; она указана около вершины {3, 5} на рис.10.2.

	1	2	3	4
1	∞	0	15	3
2	0	∞	12	22
4	3	44	18	∞
5	5	1	∞	0

	1	2	3	4
1	∞	0	3	3	0
2	0	∞	0	22	0
4	0	41	3	∞	3
5	15	1	∞	0	0
	0	0	12	0

а б

Рис. 10.4. (а) Приведенная матрица стоимостей после вычеркивания строки 3 и столбца 5 и установления с₅₃₌∞; (б) приведение матрицы стоимостей, изображенной в части (а).

Нижняя граница для множества {3, 5} получается несколько иным способом. Ребро (3, 5) не может находиться в этом множестве, поэтому полагаем c₃₅ = ∞ в матрице, изображенной на рис.10.3. В любой тур из {3,5} будет входить какое-то ребро из города 3 и какое-то ребро к городу 5. Самое дешевое ребро из города 3, исключая старое значение (3,5), имеет стоимость 2, а самое дешевое ребро к городу 5 имеет стоимость 0. Следовательно, нижняя граница любого тура в множестве {3,5} равна 47+2+0=49 (рис.10.2).

Н а данной стадии нам удалось сократить размер матрицы стои­мостей, рассматриваемой в вершине {3, 5}. Кроме того, если мы смо­жем найти тур из множества {3, 5} со стоимостью, меньшей или рав­ной 62, тогда не нужно проводить дальше ветвления и вычисления границ в вершине {3, 5}. В этом случае будем говорить, что вершина {3, 5} в дереве отработана. Тогда следующей целью может быть ветвление из вершины {3, 5} в надежде найти тур со стоимостью в пределах 49≤с≤62.

В основных чертах блок-схема этого алгоритма ветвей и границ показана на рис.10.5. Здесь используются следующие обозначения. Буква X обо­значает текущую вершину на дереве поиска, a w(X) — соответствую­щую нижнюю границу. Вершины, следующие непосредственно за X, назовем Y и Y; они выбираются ветвлением по некоторому ребру (k, l). Символ z₀ обозначает стоимость самого дешевого тура, извест­ного на данный момент. В начальный момент z₀ = ∞_.

Раскроем более детально содержание некоторых блоков этой схемы.

Блок 1. Установление начальных значений переменных, или ини­циализация, не представляет труда.

Блок 2. Первое приведение — это непосредственная реализация описанной ранее процедуры; детали оставляем в качестве упражнения.

Б лок 3. Выбор следующего ребра ветвления (k, l) определяет множества Y и Y, непосредственно следующие за текущим X. Ребро (k, l) нужно выбирать так, чтобы попытаться получить большую по величине нижнюю границу на множестве Y = {k, l}, что облегчит проведение оценки для множества Y. Обычно предпочтительнее про­вести оценку для Y, так как размер этого множества и соответству­ющая ему матрица стоимостей обычно больше, чем у Y (из матрицы для Y вычеркнуты строка k и столбец I). Можно надеяться также, что Y с большей вероятностью содержит оптимальный тур.

Как применить эти идеи к выбору конкретного ребра ветвления (k, l)? В приведенной матрице стоимостей С’, связанной с X, каждая строка и столбец имеют хотя бы по одному нулевому элементу (если нет, то С’ не полностью приведена). Можно предположить, что ребра, соответствующие этим нулевым стоимостям, будут с большей веро­ятностью входить в оптимальный тур, чем ребра с б ольшими стои­мостями. Поэтому мы выберем одно из них. Но какое? Пусть ребро (i, j) имеет с_ij= 0 в С. Мы хотим, чтобы у Y={i, j} была как можно большая нижняя граница. Вспоминая метод вычисления нижней границы для {3, 5} в нашем примере, мы видим, что для Y эта граница задается в виде

w(Y)=w(X) + (наименьшая стоимость в строке i, не включая с_ij) + + (наименьшая стоимость в столбце i, не включая с_ij).

Следовательно, из всех ребер (i, j) с с_ij = 0 в текущей матрице С’ мы выбираем то, которое дает наибольшее значение для w(Y). Пусть это будет ребро (k, I).

Поэтому более подробное описание выбора, представленного бли­ком 3, имеет следующий вид:

Шаг 1. Пусть S — множество ребер (i, j), таких, что с_ij = 0 в те­кущей матрице стоимостей С.

Шаг 2. Положим D_ij - равным наименьшей стоимости в строке i, исключая с_ij, плюс наименьшая стоимость в столбце j, исключая с_ij. Вычисляем D_ij для всех (i, j)  S.

Шаг 3. Выбираем следующее ребро ветвления (k, l) из условия

Блок 4. Определяем вершину Y, следующую за X, точно так же, как делали раньше.

В рассматриваемом примере X = R и Y={2, 1}, т, е. это множество всех туров, не содержащих ребро (2, 1). Вычисляем нижнюю границу w(Y) так же, как в блоке 3, т. е.

w(Y) = w(X)+D_k^*_l

и

w({2, 1}) = 47+ 15 = 62.

Блок 5. Вершине Y, следующей за X, соответствует подмножество туров из X, содержащих то ребро (k, /), которое выбрано в блоке 3. При вычислении w(Y) необ­ходима известная осторожность.

Блок 6. В конце концов, мы должны прийти к множествам, содержа­щим так мало туров, что мы можем рассмотреть каждый из них и провести оценку для этой вершины без дальнейшего ветвления. Блок 6 проверяет, не пришли ли мы уже к таким множествам. Каждое ребро, про которое мы знаем, что оно содержится во всех турах из Y, сокра­щает размер С на одну строку и один столбец. Если в исходной задаче было N городов, а текущая матрица С имеет размер 2x2, то выбрано уже N—2 ребер каждого тура Y. Поэтому множество Y содержит самое большее два тура (почему?). Вопрос о том, как их распознать, оставим в качестве упражнения. Таким образом, блок 6 проверяет, является ли С матрицей размера 2x2. Заметим, что это, по существу, дает ответ на вопрос, поставленный в конце шага 2 при обсуждении блока 5.

Блоки 7 и 8. Блок 7 работает, только если С — матрица размеров 2x2. В этом блоке отыскивается самый дешевый тур в Y и его вес обозначается через w(Y). В блоке 8 проверяется, лучше ли данный тур, чем текущий лучший из известных туров. Если нет, то новый тур отбрасывается. Если да, то текущим лучшим туром становится новый тур, и мы полагаем z₀=w(Y).

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

Блок 10. Наше обсуждение помогает решить, что делать с этим бес­покоящим вопросительным знаком, поставленным в блоке 10. Вы, должно быть, заметили, что алгоритм, представленный блок-схемой на рис. 10.5, не имеет окончания. Блок 10 показывает, должны ли мы остановиться. Если текущая граница для нашего лучшего тура z₀ меньше или равна w(X) — наименьшей из неисследованных нижних границ,— тогда никакая из вершин, следующих за X, не может содержать лучшего тура. Благодаря способу выбора X в блоке 9 лучший тур не может также содержаться ни в какой другой из не­оцененных конечных вершин. Теперь все дерево поиска оценено, и мы останавливаемся. Если w(Х)<z₀, поиск должен быть продолжен.

Б лок 11. В этой части алгоритма получается откорректированная матрица стоимостей С для текущей вершины X.

На рис.10.6 приведено дерево поиска для задачи рис.10.1.

Обо всех более или менее эффективных алгоритмах ветвей и гра­ниц известно или имеются предположения, что их трудоемкость в худшем случае является экспоненциальной. Анализ ожидаемой тру­доемкости очень сложен и часто выходит за рамки наших аналити­ческих возможностей. Все, что известно о большинстве алгоритмов ветвей и границ, описанных в литературе, это лишь некоторые экс­периментальные статистические данные.