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




Поиск с предпочтением - часть 4


        f( с) = g( c) + h( c) = 6 + 4 = 10

        f( e) = g( e) + h( e) = 2 + 7 = 9

Поскольку f( e) < f( c),  Процесс 2 переходит к  f,  a Процесс 1 ждет. Однако

        f( f) = 7 + 4 = 11

        f( c) = 10

        f( c) < f( f)

Поэтому Процесс 2 останавливается, а Процессу 1 дается разрешение продолжать движение, но только до  d,  так как f( d) = 12 > 11. Происходит активация Процесса 2, после чего он, уже не прерываясь, доходит до цели  t.

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

(1)        л( В, F/G) - дерево, состоящее из одной вершины (листа); В

  -  вершина пространства состояний, G

  -  g( B)  (стоимость уже найденного пути из стартовой вершины в В);   F - f( В)  =  G

  + h( В).

(2)        д( В, F/G, Пд) - дерево с непустыми поддеревьями; В  -   корень дерева, Пд  -  список поддеревьев; G  -  g( B);   F  -  уточненное значение f(

В),  т.е. значение   f    для наиболее перспективного преемника вершины В;  список Пд   упорядочен в порядке возрастания f-оценок поддеревьев.

Уточнение значения  f  необходимо для того, чтобы дать программе возможность распознавать наиболее перспективное поддерево (т.е. поддерево, содержащее наиболее перспективную концевую вершину) на любом уровне дерева поиска. Эта модификация f-оценок на самом деле приводит к обобщению, расширяющему область определения функции f.  Теперь функция  f  определена не только на вершинах, но и на деревьях.


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