Конструирование оценочной функции для верхней и нижней границ целевой функции. (Рассмотрите на примере задачи поиска простой цепи графа)

Пример: задача определения маршрута min/max длины в ориентированном графе.

Дерево декомпозиции по методу в ширину:

 

Рассмотрим вариант поиска дерева min длинны. В качестве оценочной функции будем использовать суммарную длину ребер, уже включенных в рассматриваемый фрагмент маршрута. Метод ветвления – поиск в ширину, отсечение – по нижней границе.

 

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

 

Для нижней границы существуют св-ва: не должна уменьшаться

нижняя граница должна быть = F_ц^к (значение ЦФ в конечной вершине)

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

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

Для верхней границы существуют св-ва: не должна возрастать,

в конечных вершинах она должна быть = F_ц^к (значение ЦФ в конечной вершине).

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

Суммирование необходимо выполнять, начиная от данной вершины до последней конечной.