Лекция 1

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

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

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

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

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

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

2) если и , то .

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

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

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

функции f; однако, вот какая возможность возникает сократить перебор при благоприятных обстоятельствах.

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

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

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

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

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

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

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

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

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

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

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