Вычислительная математика
Специальность ПО
5-й семестр
Конспект лекций
Лекция 1
Общее описание метода ветвей и границ организации пол-ного перебора возможностей
. Решение задачи о коммивояжере методом ветвей и границ: основная схема.
Пусть - конечное множество и - ве-щественно-значная функция на нем; требуется найти минимум
этой функции и элемент множества, на котором этот минимум
достигается.
Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M
. Но чаще
всего полный перебор производить приходится. В этом случае
обязательно возникает задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда
выполняются специфические дополнительные условия на множе-
ство M
и минимизируемую на нем функцию. А именно, -
предположим
, что имеется вещественно-значная функция j
на множестве подмножеств множества M
со следующими двумя свойствами:
1) для (здесь - множество, состоящее
из единственного элемента );
2) если и , то .
В этих условиях можно организовать перебор элементов множества M
с целью минимизации функции на этом множестве так:
разобьем множество M
на части (любым способом) и выбе-
рем ту из его частей W1
, на которой функция j
минимальна; за-тем разобьем на несколько частей множество W1
и выберем ту из его частей W2
, на которой минимальна функция j
; затем разо-бьем W2
на несколько частей и выберем ту из них, где минималь-на j,
и так далее, пока не придем к какому-либо одноэлементно-му множеству
.
Это одноэлементное множество называется рекордом
.
Функция j
, которой мы при этом выборе пользуемся, называется
оценочной.
Очевидно, что рекорд не обязан доставлять минимум
функции f
; однако, вот какая возможность возникает сократить
перебор при благоприятных обстоятельствах
.
Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось
несколько множеств и выбиралось затем одно из них. Пусть
- подмножества множества M
, возникшие на предпослед-нем этапе построения рекорда, и пусть множество оказалось
выбранным с помощью оценочной функции. Именно при разбие-нии и возник рекорд, который сейчас для определенности обозначим через . Согласно сказанному выше, ,
; кроме того, по определению оценочной функции, .
Предположим, что ; тогда для любого элемента m
множества M
, принадлежащего множеству , будут верны не-
равенства; это значит, что при полном пере-
боре элементов из M
элементы из уже вообще не надо рас-
сматривать. Если же неравенство не будет выполне-
но, то все элементы из надо последовательно сравнить с най-
денным рекордом и как только отыщется элемент, дающий мень-
шее значение оптимизируемой функции, надо им заменить ре-корд и продолжить перебор. Последнее действие называется
улучшением рекорда.
Слова метод ветвей и границ
связаны с естественной гра-
фической интерпретацией всего изложенного: строится много-
уровневое дерево, на нижнем этаже которого располагаются
элементы множества M
, на котором ветви ведут к рекорду и его
улучшениям и на котором часть ветвей остаются «оборванными»,
потому что их развитие оказалось нецелесообразным.
Мы рассмотрим сейчас первый из двух запланированных в
этом курсе примеров применения метода ветвей и границ - ре-шение задачи о коммивояжере.
Вот ее формулировка.
Имеется несколько городов, соединеных некоторым обра-зом дорогами с известной длиной; требуется установить, имеет-
ся ли путь, двигаясь по которому можно побывать в каждом горо-
де только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеет-
ся, установить кратчайший из таких путей.
Формализуем условие в терминах теории графов. Города
будут вершинами графа, а дороги между городами - ориентиро-ванными (направленными) ребрами графа, на каждом из кото-рых задана весовая функция: вес ребра - это длина соответству-
ющей дороги. Путь, который требуется найти, это - ориентиро-ванный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным
, если он проходит по всем вершинам графа; цикл называется простым
, если он прохо-
дит по каждой своей вершине только один раз; цикл называется
ориентированным
, если начало каждого последующего ребра совпадает с концом предыдущего; вес
цикла - это сумма весов его ребер; наконец, орграф называется полным
, если в нем име-ются все возможные ребра); такие циклы называются также га-
мильтоновыми.
Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о ком-мивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер при-писать вес ¥, считая, что &y
Отсюла следует, что задачу о коммивояжере достаточно ре-шить для полных орграфов с весовой функцией. Сформулируем
теперь это в окончательном виде:
пусть
- полный ориентированный граф и
-
весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.
Пусть конкретный состав множества вершин и
- весовая матрица данного орграфа, т.е.
,
причем для любого .
Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного
примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции.
Введем некоторые термины. Пусть имеется некоторая чис-
ловая матрица. Привести строку этой матрицы
означает выде-лить в строке минимальный элемент (его называют константой приведения
) и вычесть его из всех элементов этой строки. Оче-видно, в результате в этой строке на месте минимального эле-мента окажется ноль, а все остальные элементы будут неотрица-тельными. Аналогичный смысл имеют слова привести столбец
матрицы.
Слова привести матрицу по строкам
означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова
привести матрицу по столбцам
.
Наконец, слова привести матрицу
означают, что матрица
сначала приводится по строкам, а потом приводится по столб-цам.
Весом
элемента матрицы называют сумму констант приве-
дения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на ¥. Следовательно, слова самый тяжелый нуль в матрице
означают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом.
Приступим теперь к описанию метода ветвей и границ для
решения задачи о коммивояжере.
Первый шаг
. Фиксируем множество всех обходов коммиво-
яжера (т.е. всех простых ориентированных остовных циклов). По-
скольку граф - полный, это множество заведомо непусто. Сопо-ставим ему число, которое будет играть роль значения на этом
множестве оценочной функции: это число равно сумме констант
приведения данной матрицы весов ребер графа. Если множест-во всех обходов коммивояжера обозначить через G, то сумму
констант приведения матрицы весов обозначим через j(G). При-веденную матрицу весов данного графа следует запомнить; обо-значим ее через M
1
; таким образом, итог первого шага:
множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M
1
.
Второй шаг.
Выберем в матрице M
1
самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и раз-
делим множество G на две части: на часть , состоящую из
обходов, которые проходят через ребро , и на часть ,
состоящую из обходов, которые не проходят через ребро .
Сопоставим множеству следующую матрицу M
1
,1
: в
матрице M
1
заменим на ¥ число в клетке . Затем в получен-ной матрице вычеркнем строку номер i
и столбец номер j
, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M
1
,1
; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в даль-нейшем через j(), сопоставим множеству .
Теперь множеству тоже сопоставим некую матрицу
M
1,2
. Для этого в матрице M
1
заменим на ¥ число в клетке
и полученную в результате матрицу приведем. Сумму констант
приведения запомним, а полученную матрицу обозначим через M
1,2
. Прибавим запомненную сумму констант приведения к
числу j(G) и полученное число, обозначаемое в дальнейшем че-
рез j(), сопоставим множеству .
Теперь выберем между множествами и то, на
котором минимальна функция j (т.е. то из множеств, которому
соответствует меньшее из чисел j() и j().
Заметим теперь, что в проведенных рассуждениях исполь-зовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было вы-делено определенное ребро графа и были построены новые
матрицы, к которым, конечно, можно все то же самое применить.
При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии
: пе-ред тем, как в очередной матрице вычеркнуть строку и столбец,
в ней надо заменить на ¥ числа во всех тех клетках, которые со-ответвуют ребрам, заведомо не принадлежащим тем гамильто-новым циклам, которые проходят через уже отобранные ранее ребра; эту довольно трудную фразу мы еще не раз рассмотрим в
следующей лекции на конкретном примере.
К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это воз-можно.
Доказывается, что в результате получится множество, со-стоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции
j; таким образом, оказы-ваются выполненными все условия, обсуждавшиеся при описа-нии метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.