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




Поиск с предпочтением


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

fig12_1.gif (1069 bytes)

Рис. 12. 1.  Построение эвристической оценки f(n)  стоимости

самого дешевого пути из  s  в  t,   проходящего через  n:  f(n) = g(n) + h(n).

Мы будем в дальнейшем предполагать, что для дуг пространства состояний определена функция стоимости с(n, n')  - стоимость перехода из вершины n  к вершине-преемнику n'.

Пусть f  - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n  оценку f( n)   "трудности" этой вершины. Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой  f

  принимает минимальное значение. Мы будем использовать здесь функцию  f   специального вида, приводящую к хорошо известному А*-алгоритму. Функция  f( n)   будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины  s  к одной из целевых вершин при условии, что этот путь проходит через вершину  n.  Давайте предположим, что такой путь существует и что  t  -  это целевая вершина, для которой этот путь минимален. Тогда оценку  f( n) можно представить в виде суммы из двух слагаемых (рис. 12.1):

        f( n) = g( n) + h( n)

Здесь  g( n)  - оценка оптимального пути из  s  в  n;  h( n) -  оценка оптимального пути из  n  в  t.




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