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




Эвристические оценки и алгоритм поиска - часть 2


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

Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция   h   для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата - корня этого дерева?

fig13_9.gif (2481 bytes)

Рис. 13. 9.  Получение оценки  Н  трудности задач  И / ИЛИ-графа.

Обозначим через Н( В) оценку трудности вершины  В.  Для самой верхней вершины текущего дерева поиска  H( В)  просто совпадает с  h( В).  С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение  h,  поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

        H( B) = min ( c( B, Bi) + H( Bi) )
                                i

где  с( В, В)  -  стоимость дуги, ведущей из  В  в  Вi.   Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу  В,  нам нужно решить только одну из ее задач-преемников. Трудность И-вершины  В   можно приближенно оценить так:

       

fig13_9_1.gif (514 bytes)

Будем называть H-оценку внутренней вершины "возвращенной" (backed-up) оценкой.

Более практичной с точки зрения использования в нашей программе поиска является другая величина  F,  которую можно определить в терминах  H  следующим образом.


Содержание  Назад  Вперед