Программирование на языке Пролог для искусственного интеллекта
Наша программа поиска начнет свою
Наша программа поиска начнет свою работу со стартовой вершины и, распространяя поиск из уже просмотренных вершин на их преемников, будет постепенно наращивать дерево поиска. Этот процесс будет строить дерево даже в том случае, когда сам И / ИЛИ-граф не является деревом; при этом граф будет разворачиваться в дерево за счет дублирования своих отдельных частей.
Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция h для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата - корня этого дерева?
Рис. 13. 9. Получение оценки Н трудности задач И / ИЛИ-графа.
Обозначим через Н( В) оценку трудности вершины В. Для самой верхней вершины текущего дерева поиска H( В) просто совпадает с h( В). С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение h, поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как
H( B) = min ( c( B, Bi) + H( Bi) )
i
где с( В, В) - стоимость дуги, ведущей из В в Вi. Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу В, нам нужно решить только одну из ее задач-преемников. Трудность И-вершины В
можно приближенно оценить так:
Будем называть H-оценку внутренней вершины "возвращенной" (backed-up) оценкой.
Более практичной с точки зрения использования в нашей программе поиска является другая величина F, которую можно определить в терминах H следующим образом.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий