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

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

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

5-й семестр

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

Лекция 1

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

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

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

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

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

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

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

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

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

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

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

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

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

2) если и , то .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Очевидно, в полном орг

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать