Prolog

        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  определена не только на вершинах, но и на деревьях. Для одновершинных деревьев (листов) n  остается первоначальное определение

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

Для дерева T  с корнем  n,   имеющем преемников m₁,  m₂,   ...,  получаем

        f( T) = min  f( m_i )

                      ⁱ

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

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

        расширить( Путь, Дер, Предел, Дер1, ЕстьРеш, Решение)

Эта процедура расширяет текущее (под)дерево, пока  f-оценка остается равной либо меньшей, чем Предел.

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

        эврпоиск( Старт, Решение):-

                макс_f( Fмакс).                     % Fмакс  >  любой  f-оценки

                расширить( [ ], л( Старт, 0/0), Fмакс, _, да, Решение).

        расширить( П, л( В, _ ), _, _, да, [В | П] ) :-

                цель( В).

        расширить( П, л( В, F/G), Предел, Дер1, ЕстьРеш, Реш) :-

            F <= Предел,

            ( bagof( B1/C, ( после( В, В1, С), not принадлежит( В1, П)),

                            Преемники),   !,

                преемспис( G, Преемники, ДД),