Методы направленного перебора

Пусть дана Z - задача оптимизации –пара (F,c), где F –множество решений, а – c функция стоимости, отображающая элементы F на множество действительных чисел. Требуется найти такую x* точку из F, на которой значение функции c (x*) обладает определенным свойством, например, минимально, максимально и пр. Рассмотрим, например, задачу на минимум.

В задаче коммивояжера – это множество всех гамильтоновых циклов графа, в задаче ЦЛП – множество целочисленных точек многогранника и т.п.

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

1. Экстремальное значение на множестве и на подмножестве связаны определенными неравенствами. В случае задачи на минимум c_G - минимум функции стоимости на подмножестве G F не превосходит c (x*) - минимума функции стоимости на всем множестве.
2. Пусть l (x*)≤ c (x*) ≤ u (x*), т.е. l (x*) и u (x*) - нижняя и верхняя оценка для c (x*). При этом значения l (x*) и u (x*) могут быть найдены полиномиальным алгоритмом.
3. Все множество F может быть иерархически разбито на непересекающиеся подмножества. Это разбиение представимо в виде дерева ветвей. Пример приведен на рисунке.

Здесь каждая вершина – некоторое множество допустимых решений. Все множество решений, соответствующее каждому родительскому узлу разбивается на подмножества решений, соответствующих узлам-потомкам. Здесь все подмножества родительского узла не пересекаются, а их объединение в точности дает множество, соответствующее родительскому узлу. Листья дерева – одноэлементные множества.

1. Если для некоторого узла дерева G F выполняется соотношение

l (x*)< c_G,

то это означает, что оптимальное решение x* не может находиться среди допустимых решений, соответствующих данному узлу, а все множество G можно исключить из дальнейшего рассмотрения. (Отрезать ветвь дерева.)

Отсюда следует другое название методов направленного перебора – методы ветвей и границ.

Дата добавления: 2015-07-11