Программирование на языке Пролог для искусственного интеллекта

       

Отношение расширить



Рисунок 12. 4.  Отношение расширить: расширение дерева Дер до тех
пор, пока   f-оценка не превзойдет Предел, приводит к дереву Дер1.


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

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

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

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

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

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

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

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

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



Содержание раздела