Prolog

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

        Дер = д( В, 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- оценками

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

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