Метод ветвей и границ

Общее описание метода ветвей и границ организации полного перебора возможностей.
Решение задачи о коммивояжере методом ветвей и границ: основная схема.
Пусть - конечное множество и - вещественно-значная функция на нем; требуется
найти минимум этой функции и элемент множества, на котором этот минимум
достигается.
Когда имеется та или иная дополнительная информация о множестве, решение этой
задачи иногда удается осуществить без полного перебора элементов всего множества
M. Но чаще
всего полный перебор производить приходится. В этом случае обязательно возникает
задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного перебора. Он
применим не всегда, а только тогда, когда выполняются специфические
дополнительные условия на множество M и минимизируемую на нем функцию. А именно,
-
предположим, что имеется вещественно-значная функция j на множестве подмножеств
множества M со следующими двумя свойствами:
для (здесь - множество, состоящее из единственного элемента );
2) если и , то .
В этих условиях можно организовать перебор элементов множества M с целью
минимизации функции на этом множестве так:
разобьем множество M на части (любым способом) и выберем ту из его частей W1, на
которой функция j минимальна; затем разобьем на несколько частей множество W1 и
выберем ту из его частей W2, на которой минимальна функция j; затем разобьем W2
на несколько частей и выберем ту из них, где минимальна j, и так далее, пока не
придем к какому-либо одноэлементному множеству .
Это одноэлементное множество называется рекордом.
Функция j, которой мы при этом выборе пользуемся, называется оценочной.
Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая
возможность возникает сократить перебор при благоприятных обстоятельствах.
Описанный выше процесс построения рекорда состоял из последовательных этапов, на
каждом из которых фиксировалось несколько множеств и выбиралось затем одно из
них. Пусть - подмножества множества M, возникшие на предпоследнем этапе
построения рекорда, и пусть множество оказалось выбранным с помощью оценочной
функции. Именно при разбиении и возник рекорд, который сейчас для
определенности обозначим через . Согласно сказанному выше, , ; кроме того, по
определению оценочной функции, .
Предположим, что ; тогда для любого элемента m множества M, принадлежащего
множеству , будут верны неравенства; это значит, что при полном переборе
элементов из M элементы из уже вообще не надо рассматривать. Если же
неравенство не будет выполнено, то все элементы из надо последовательно
сравнить с найденным рекордом и как только отыщется элемент, дающий меньшее
значение оптимизируемой функции, надо им заменить рекорд и продолжить перебор.
Последнее действие называется улучшением рекорда.
Слова метод ветвей и границ связаны с естественной графической интерпретацией
всего изложенного: строится многоуровневое дерево, на нижнем этаже которого
располагаются элементы множества M, на котором ветви ведут к рекорду и его
улучшениям и на котором часть ветвей остаются “оборванными”, потому что их
развитие оказалось нецелесообразным.
Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров
применения метода ветвей и границ - решение задачи о коммивояжере. Вот ее
формулировка.
Имеется несколько городов, соединенных некоторым образом дорогами с известной
длиной; требуется установить, имеется ли путь, двигаясь по которому можно
побывать в каждом городе только один раз и при этом вернуться в город, откуда
путь был начат (“обход коммивояжера”), и, если таковой путь имеется, установить
кратчайший из таких путей.
Формализуем условие в терминах теории графов. Города будут вершинами графа, а
дороги между городами - ориентированными (направленными) ребрами графа, на
каждом из которых задана весовая функция: вес ребра - это длина соответствующей
дороги. Путь, который требуется найти, это - ориентированный остовный простой
цикл минимального веса в орграфе (напомним: цикл называется остовным, если он
проходит по всем вершинам графа; цикл называется простым, если он проходит по
каждой своей вершине только один раз; цикл называется ориентированным, если
начало каждого последующего ребра совпадает с концом предыдущего; вес цикла -
это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются
все возможные ребра); такие циклы называются также гамильтоновыми.
Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос
о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай
задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не
является полным, то его можно дополнить до полного недостающими ребрами и
каждому из добавленных ребер приписать вес ¥, считая, что ¥ - это “компьютерная
бесконечность”, т.е. максимальное из всех возможных в рассмотрениях чисел. Если
во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то
при наличии у него ребер с весом ¥ можно б