Prolog

Дер1            Дерево Дер, расширенное в пределах ограничения Предел;

                    f-оценка дерева Дер1 больше, чем Предел ( если только при расширении не была обнаружена целевая вершина).

ЕстьРеш      Индикатор, принимающий значения "да", "нет" и "никогда".

Решение     Решающий путь, ведущий из стартовой вершины через дерево Дер1

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

Переменные Путь, Дер, и Предел - это "входные" параметры процедуры расширить в том смысле, что при каждом обращении к расширить они всегда конкретизированы. Процедура расширить порождает результаты трех видов. Какой вид результата получен, можно определить по значению индикатора ЕстьРеш следующим образом:

(1)        ЕстьРеш = да.

            Решение = решающий путь, найденный при расширении дерева Дер с учетом ограничения Предел.

            Дер1 = неконкретизировано.

(2)        ЕстьРеш = нет

            Дер1 = дерево Дер, расширенное до тех пор, пока его f-оценка не превзойдет Предел (см. рис. 12.4).

            Решение = неконкретизировано.

(3)        ЕстьРеш = никогда.

            Дер1 и Решение = неконкретизированы.

В последнем случае Дер является "тупиковой" альтернативой, и соответствующий процесс никогда не будет реактивирован для продолжения просмотра этого дерева. Случай этот возникает тогда, когда f-оценка дерева Дер не превосходит ограничения Предел, однако дерево не может "расти" потому, что ни один его лист не имеет преемников, или же любой преемник порождает цикл.

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

        Дер = д( В, F/G, [Д | ДД ] )

означает следующее. Во-первых, расширению подвергается наиболее перспективное дерево Д. В качестве ограничения этому дереву выдается не Предел, а не-

Рис. 12. 4.  Отношение расширить: расширение дерева Дер до тех

пор, пока   f-оценка не превзойдет Предел, приводит к дереву Дер1.

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

Предложение, относящееся к случаю

        Дер = л( В, F/G)

порождает всех преемников вершины В вместе со стоимостями дуг, ведущих в них из В. Процедура преемспис формирует список поддеревьев, соответствующих вершинам-преемникам, а также вычисляет их g- и f-оценки, как показано на рис. 12.5. Затем полученное таким образом дерево подвергается расширению с учетом ограничения Предел. Если преемников нет, то переменной ЕстьРеш придается значение "никогда" и в результате лист В покидается навсегда.

Другие отношения:

        после( В, В1, С)                     В1   -  преемник вершины В;  С - стоимость дуги, ведущей из В  в В1.

        h( В, Н)                                    Н   -  эвристическая оценка стоимости оптимального пути

                                                        из вершины В  в целевую вершину.

        макс_f( Fмакс)                       Fмакс   -  некоторое значение, задаваемое пользователем,

                                                        про которое известно, что оно больше любой возможной f-оценки.

В следующих разделах мы покажем на примерах, как можно применить нашу программу поиска с предпочтением к конкретным задачам. А сейчас сделаем несколько заключительных замечаний общего характера относительно этой программы. Мы реализовали один из вариантов эвристического алгоритма, известного в литературе как А*-алгоритм (ссылки на литературу см. в конце главы). А*-алгоритм привлек внимание многих исследователей. Здесь мы приведем один важный результат, полученный в результате математического анализа А*-алгоритма:

Рис. 12. 5.  Связь между g-оценкой вершины  В  и  f- и  g-оценками

ее "детей" в пространстве состояний.

Алгоритм поиска пути называют допустимым, если он всегда отыскивает оптимальное решение (т.е. путь минимальной стоимости) при условии, что такой путь существует. Наша реализация алгоритма поиска, пользуясь механизмом возвратов, выдает все существующие решения, поэтому, в нашем случае, условием допустимости следует считать оптимальность первого из найденных решений. Обозначим через h*(n)  стоимость оптимального пути из произвольной вершины  n   в целевую вершину. Верна следующая теорема о допустимости А*-алгоритма:  А*-алгоритм, использующий эвристическую функцию  h,   является допустимым, если

        h( n) <= h*( n)

для всех вершин  n  пространства состояний.