5.6. ИСПОЛЬЗОВАНИЕ ОЦЕНОК СТОИМОСТИ ДЛЯ ПРЯМОГО ПЕРЕБОРА

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

В процессе перебора, который мы опишем, строится дерево перебора. На любом этапе этого перебора внизу дерева

перебора располагаются вершины одного из следующих трех типов:

1) вершины, признанные в процессе перебора заключительными;

2) вершины, относительно которых в процессе перебора было установлено, что они не являются заключительными и у них нет дочерних вершин;

3) вершины, для которых в процессе перебора еще не были построены дочерние вершины.

Любую из таких вершин в дереве перебора мы будем называть концевой вершиной.

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

Если установлено, что является заключительной вершиной, то

Если установлено, что не является заключительной вершиной и у нее нет дочерних вершин, то функция не определена.

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

— неконцевая вершина, имеющая дочерние вершины типа «ИЛИ»

Эвристическая функция задается формулой

— неконцевая вершина, имеющая дочерние вершины типа «И»

Эвристическая функция для суммарных стоимостей за дается формулой

а для максимальных стоимостей — формулой

Поскольку для заключительных вершин, наше определение дает гарантию, что при Н в состав дерева перебора будет входить наше «И/ИЛИ» деревб целиком.

Далее, в дереве поиска на каждом этапе содержится множество поддеревьев с корнем в каждое из которых могло бы в зависимости от результатов дальнейшего раскрытия вершин стать верхней частью полного дерева решения. Назовем эти деревья потенциальными деревьями решений для Для каждой вершины, имеющей дочерние вершины типа «ИЛИ», в дереве поиска можно выбрать отдельное потенциальное дерево решения, соответствующее каждой из дочерних вершин типа «ИЛИ». Аналогично имеются также потенциальные деревья решений с корнем в вершине которые могли бы решать подзадачу, соответствующую этой вершине. (Конечно, если только эта вершина не помечена уже как неразрешимая.)

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

1. Начальная вершина входит в

2. Если у вершины входящей в то, в деоеве перебора есть

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

б) дочерние вершины типа «И», то все они входят в то.

Это потенциальное дерево решения то, по оценке служащее верхней частью оптимального дерева решения с корнем в является ключевым понятием в эвристическом процессе перебора, который нам предстоит описать. Уместная здесь процедура упорядочения связана с вопросом «Какое из потенциальных деревьев решения наиболее перспективно для раскрытия», а не с вопросом «Какая из вершин наиболее перспективна для раскрытия на следующем шаге». (Аналогично при переборе в пространстве состояний, выбирая вершину с минимальным значением мы продолжаем наиболее перспективный частичный путь.) Мы будем брать то в качестве наиболее перспективного потенциального дерева решения.

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

что раскрытой вершине, ибо для других вершин они не изменятся. (Величина Н для вершины зависит лишь от величин Н следующих за ней вершин.)

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