Реферат: Лекции по вычислительной математике

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

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

5-й семестр

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

Лекция 1

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

Пусть - конечное множество и - ве-щественно-значная функция на нем; требуется найти минимум

этой функции и элемент множества, на котором этот минимум

достигается.

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

всего полный перебор производить приходится. В этом случае

обязательно возникает задача, как лучше перебор организовать.

Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда

выполняются специфические дополнительные условия на множе-

ство M и минимизируемую на нем функцию. А именно, -

предположим , что имеется вещественно-значная функция j на множестве подмножеств множества M со следующими двумя свойствами:

1) для (здесь - множество, состоящее

из единственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

разобьем множество M на части (любым способом) и выбе-

рем ту из его частей W₁ , на которой функция j минимальна; за-тем разобьем на несколько частей множество W₁ и выберем ту из его частей W₂ , на которой минимальна функция j ; затем разо-бьем W₂ на несколько частей и выберем ту из них, где минималь-на j, и так далее, пока не придем к какому-либо одноэлементно-му множеству .

Это одноэлементное множество называется рекордом .

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

оценочной. Очевидно, что рекорд не обязан доставлять минимум

функции f ; однако, вот какая возможность возникает сократить

перебор при благоприятных обстоятельствах .

Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось

несколько множеств и выбиралось затем одно из них. Пусть

- подмножества множества M , возникшие на предпослед-нем этапе построения рекорда, и пусть множество оказалось

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

; кроме того, по определению оценочной функции, .

Предположим, что ; тогда для любого элемента m множества M , принадлежащего множеству , будут верны не-

равенства; это значит, что при полном пере-

боре элементов из M элементы из уже вообще не надо рас-

сматривать. Если же неравенство не будет выполне-

но, то все элементы из надо последовательно сравнить с най-

денным рекордом и как только отыщется элемент, дающий мень-

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

улучшением рекорда.

Слова метод ветвей и границ связаны с естественной гра-

фической интерпретацией всего изложенного: строится много-

уровневое дерево, на нижнем этаже которого располагаются

элементы множества M , на котором ветви ведут к рекорду и его

улучшениям и на котором часть ветвей остаются «оборванными»,

потому что их развитие оказалось нецелесообразным.

Мы рассмотрим сейчас первый из двух запланированных в

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

Имеется несколько городов, соединеных некоторым обра-зом дорогами с известной длиной; требуется установить, имеет-

ся ли путь, двигаясь по которому можно побывать в каждом горо-

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

ся, установить кратчайший из таких путей.

Формализуем условие в терминах теории графов. Города

будут вершинами графа, а дороги между городами - ориентиро-ванными (направленными) ребрами графа, на каждом из кото-рых задана весовая функция: вес ребра - это длина соответству-

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

дит по каждой своей вершине только один раз; цикл называется

ориентированным , если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным , если в нем име-ются все возможные ребра); такие циклы называются также га-

мильтоновыми.

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

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

теперь это в окончательном виде:

пусть - полный ориентированный граф и -

весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Пусть конкретный состав множества вершин и

- весовая матрица данного орграфа, т.е.

,

причем для любого .

Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного

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

Введем некоторые термины. Пусть имеется некоторая чис-

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

Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова

привести матрицу по столбцам .

Наконец, слова привести матрицу означают, что матрица

сначала приводится по строкам, а потом приводится по столб-цам.

Весом элемента матрицы называют сумму констант приве-

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

Приступим теперь к описанию метода ветвей и границ для

решения задачи о коммивояжере.

Первый шаг . Фиксируем множество всех обходов коммиво-

яжера (т.е. всех простых ориентированных остовных циклов). По-

скольку граф - полный, это множество заведомо непусто. Сопо-ставим ему число, которое будет играть роль значения на этом

множестве оценочной функции: это число равно сумме констант

приведения данной матрицы весов ребер графа. Если множест-во всех обходов коммивояжера обозначить через G, то сумму

констант приведения матрицы весов обозначим через j(G). При-веденную матрицу весов данного графа следует запомнить; обо-значим ее через M ₁ ; таким образом, итог первого шага:

множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M ₁ .

Второй шаг. Выберем в матрице M ₁ самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и раз-

делим множество G на две части: на часть , состоящую из

обходов, которые проходят через ребро , и на часть ,

состоящую из обходов, которые не проходят через ребро .

Сопоставим множеству следующую матрицу M _{1 ,1} : в

матрице M ₁ заменим на ¥ число в клетке . Затем в получен-ной матрице вычеркнем строку номер i и столбец номер j , причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M _{1 ,1} ; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в даль-нейшем через j(), сопоставим множеству .

Теперь множеству тоже сопоставим некую матрицу

M _1,2 . Для этого в матрице M ₁ заменим на ¥ число в клетке

и полученную в результате матрицу приведем. Сумму констант

приведения запомним, а полученную матрицу обозначим через M _1,2 . Прибавим запомненную сумму констант приведения к

числу j(G) и полученное число, обозначаемое в дальнейшем че-

рез j(), сопоставим множеству .

Теперь выберем между множествами и то, на

котором минимальна функция j (т.е. то из множеств, которому

соответствует меньшее из чисел j() и j().

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

матрицы, к которым, конечно, можно все то же самое применить.

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

в ней надо заменить на ¥ числа во всех тех клетках, которые со-ответвуют ребрам, заведомо не принадлежащим тем гамильто-новым циклам, которые проходят через уже отобранные ранее ребра; эту довольно трудную фразу мы еще не раз рассмотрим в

следующей лекции на конкретном примере.

К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это воз-можно.

Доказывается, что в результате получится множество, со-стоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказы-ваются выполненными все условия, обсуждавшиеся при описа-нии метода ветвей и границ.

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.