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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

h ( n ) ≤ h *( n )

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

Этот результат имеет огромное практическое значение. Даже если нам не известно точное значение h *, нам достаточно найти какую-либо нижнюю грань h * и использовать ее в качестве h в А*-алгоритме — оптимальность решения будет гарантирована.