Некоторые особенности оценочных функций

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

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

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

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

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

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