Вычислительная математика

Специальность ПО

5-й семестр

Конспект лекций

Лекция 1

Общее описание метода ветвей и границ организации пол-ного перебора возможностей. Решение задачи о коммивояжере методом ветвей и границ: основная схема.

Пусть [pic]- конечное множество и [pic] - ве-щественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум достигается.

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

Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда выполняются специфические дополнительные условия на множе- ство M и минимизируемую на нем функцию. А именно, - предположим, что имеется вещественно-значная функция ( на множестве подмножеств множества M со следующими двумя свойствами:

1) для [pic] (здесь [pic] - множество, состоящее из единственного элемента [pic]);

2) если [pic] и [pic], то [pic].

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так: разобьем множество M на части (любым способом) и выбе- рем ту из его частей (1, на которой функция ( минимальна; за-тем разобьем на несколько частей множество (1 и выберем ту из его частей (2, на которой минимальна функция (; затем разо-бьем (2 на несколько частей и выберем ту из них, где минималь-на (, и так далее, пока не придем к какому-либо одноэлементно-му множеству [pic].

Это одноэлементное множество [pic]называется рекордом.
Функция (, которой мы при этом выборе пользуемся, называется оценочной. Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая возможность возникает сократить перебор при благоприятных обстоятельствах.

Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось несколько множеств и выбиралось затем одно из них. Пусть [pic]
[pic] - подмножества множества M, возникшие на предпослед-нем этапе построения рекорда, и пусть множество [pic] оказалось выбранным с помощью оценочной функции. Именно при разбие-нии [pic] и возник рекорд, который сейчас для определенности обозначим через [pic].
Согласно сказанному выше, [pic],
[pic]; кроме того, по определению оценочной функции, [pic].

Предположим, что [pic]; тогда для любого элемента m множества M, принадлежащего множеству [pic], будут верны не- равенства[pic][pic]; это значит, что при полном пере- боре элементов из M элементы из [pic] уже вообще не надо рас- сматривать. Если же неравенство [pic] не будет выполне- но, то все элементы из [pic] надо последовательно сравнить с най- денным рекордом и как только отыщется элемент, дающий мень- шее значение оптимизируемой функции, надо им заменить ре-корд и продолжить перебор. Последнее действие называется улучшением рекорда.

Слова метод ветвей и границ связаны с естественной гра- фической интерпретацией всего изложенного: строится много- уровневое дерево, на нижнем этаже которого располагаются элементы множества M, на котором ветви ведут к рекорду и его улучшениям и на котором часть ветвей остаются «оборванными», потому что их развитие оказалось нецелесообразным.

Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров применения метода ветвей и границ - ре-шение задачи о коммивояжере. Вот ее формулировка.

Имеется несколько городов, соединеных некоторым обра-зом дорогами с известной длиной; требуется установить, имеет- ся ли путь, двигаясь по которому можно побывать в каждом горо- де только один раз и при этом вернуться в город, откуда путь был начат
(«обход коммивояжера»), и, если таковой путь имеет- ся, установить кратчайший из таких путей.

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

Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о ком-мивояжере для полных орграфов.
Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер при-писать вес (, считая, что ( - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь лег-чайший гамильтонов цикл, то при наличии у него ребер с весом ( можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший га- мильтонов цикл окажется конечным по весу, то он и будет иско-мым циклом в исходном графе.

Отсюла следует, что задачу о коммивояжере достаточно ре-шить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть [pic] - полный ориентированный граф и [pic] - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Пусть [pic] конкретный состав множества вершин и
[pic] - весовая матрица данного орграфа, т.е.

[pic], причем для любого [pic].

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

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