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

Метод ветвей и границ разработан Литлом, Мерти, Суини и Каре­лом. Рассмотрим основные идеи этого метода. Прежде всего, этот метод связан с некоторой общей схемой допущения и оценки альтернатив. Схема построения альтернативных предположений в общем виде может быть представлена, как это показано на рис. 3.9.

Вершины на рис. 3.9 соответствуют, как и ранее, состояниям зада­чи. Из каждой вершины выходит только два альтернативных направле­ния, что, впрочем, не ограничивает общности рассмотрения. Направле­ния отмечены буквами П с индексами. Идентификатор R(b_i) есть неко­торая числовая оценка, приписываемая вершине b_i.

Вообще говоря, не имеется ограничений на глубину построения де­рева, хотя ясно, что нужно стремиться к минимальной глубине. Этим, в частности, обосновывается выбор того или иного предположения П_m:сначала следует стремиться доказать предположение, достоверность которого в наибольшей степени сомнительна, или наоборот, попытаться опровергнуть предположение, достоверность которого в наибольшей степени правдоподобна, т.е. действовать по принципу reductio ad absurdum, поскольку вероятность получения противоречия здесь наи­большая, это позволяет отсечь соответствующую альтернативу у ее "ис­токов", вместо того, чтобы строить новые альтернативные предполо­жения.

Пусть ищется состояние b^*, в котором R(b^*) минимально. Допус­тим далее, что известно некоторое текущее решение b_x с текущим рекор­дом R(b_x). Тогда ясно, что любое состояние b_i, в котором наилучшее достижимое значение R(b_i) ³ R(b_x), может быть удалено (соответствующая часть дерева поиска отмечена, как показано с помощью заштрихованной области на рис. 3.9).

Рис. 3.9

Рассмотрим задачу коммивояжера в следующей частной поста­новке. Пусть дано множество N из 4 городов, соединенных дорогами. Будем интерпретировать N сетью, в которой вершины соответствуют городам, причем дугам, соединяющим вершины, приписаны веса с_ij, учитывающие затраты на переход коммивояжера из города i в город j (рис. 3.10а).

А) б)

Рис. 3.10

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

Рассмотрим решение этой задачи методом ветвей и границ. Решающими оказываются следующие два обстоятельства.

А1) Решению задачи коммивояжера соответствует выбор ровно од­ного элемента в каждой строке матрицы затрат С и ровно одного эле­мента в каждом столбце этой матрицы, причем сумма выбранных эле­ментов минимальна и они образуют цикл. Последнее замечание сущест­венно. Например, элементы (1, 2), (2, 3), (3, 1), (4, 4) не образуют цикл.

А2) Если из любой строки (столбца) вычесть (добавить) одну и ту же константу D, то результирующее значение С* суммарных затрат в оптимальном цикле Ц* уменьшится (увеличится) ровно на эту величину D.

Воспользуемся свойством А2. Выпишем минимальные элементы h_j в каждом столбце j, после чего вычтем их из элементов соответствую­щих столбцов. Затем в полученной матрице выпишем минимальные элементы h_i в строках i. Получим приведенную матрицу на рис. 2.11, а. Вычтем из каждой строки соответствующее значение h_i (рис. 3.11, б).

Из матрицы на рис. 3.11, б легко устанавливается, что минимально возможное значение С* (которое обозначим ) вычисляется следую­щим образом

Теперь будем строить предположения для приведенной матрицы затрат на рис. 3.11, б.

Сделаем допущение, что дуга принадлежит Ц*; альтернатив­ное допущение означает, что . Если дуга , то полагаем для дуги с_4,3 = ¥, а также удаляем из матрицы затрат на рис. 2.11, б строку 3 и столбец 4, что в итоге дает матрицу, показанную на рис. 2.12, а. Приведенная матрица изображена на рис.2.12, б.

Для матрицы на рис. 2.12,б находим . Таким образом, получаем, что длина оптимального цикла, содержащего дугу суть

А) б)

Рис. 3.11

А) б)

Рис. 3.12

В то же время длина цикла равна 5+2+3+2=12, следовательно, делаем вывод, что дуга не входит в оптимальный цикл. Полагаем с_3,4 = ¥.

Допустим теперь, что дуга . Проведя аналогичные вы­кладки устанавливаем, что минимальная суммарная величина затрат для цикла, содержащего дугу , составляет 13 единиц. Следователь­но, это допущение также отбрасывается, т.к. оно не улучшает текущий рекорд. Полагаем с_1,4 = ¥.

В результате в столбце 4 матрицы на рис. 3.10, б останется единст­венный допустимый элемент с_2,4 = 2 . Полагаем, . Это допущение позволяет удалить строку 2 и столбец 4. В результате получаем приведенную матрицу, изображенную на рис. 3.13, для кото­рой Ц* равно 12.

Допустим, что дуга Тогда автоматически следует, что дуга . Удалим строку 4 и столбец 3: получим приведенную матрицу, изображенную на рис. 3.14, из которой автоматически сле­дует, что дуга . Таким образом, из исходного предположения о том, что дуга , устанавливаем следующий оптимальный цикл, не содержа­щий дуги :

с суммарными затратами, равными 2 + 3 + 2 + 5 = 12.

Рис. 3.13 Рис. 3.14 Рис. 3.15

Проверим теперь другую альтернативу: . Из этого допу­щения получим приведенную матрицу, изображенную на рис. 3.15. Не­посредственно устанавливаем из рис.3.11, б и 2.15, что оптимальный цикл, содержащий дугу , имеет минимально возможные суммарные затраты, равные

определяется ич матрицы на рис. 3.13.

Таким образом, эта альтернатива отсекается, и мы получаем опти­мальный цикл

,

суммарной величиной затрат, равной 12. Дерево поиска, которое было построено в ходе решения задачи, изображено на рис. 3.16.

Рис. 3.16

Символом “Х” обозначены отсекаемые направления, раскрытие которых гарантированно не улучшает рекорд. Отметим, что в этой задаче был сразу использован в качестве текущего рекорда оптимальный цикл, что, впрочем не снижает общности рассуждений, однако сокращает размеры построения дерева решения.