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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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