Поскольку 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 определена не только на вершинах, но и на деревьях. Для одновершинных деревьев (листов) n остается первоначальное определение
f( n) = g( n) + h( n)
Для дерева T с корнем n, имеющем преемников m1, m2, …, получаем
Программа поиска с предпочтением, составленная в соответствии с приведенными выше общими соображениями, показана на рис 12.3. Ниже даются некоторые дополнительные пояснения.
Так же, как и в случае поиска в ширину (рис. 11.13), ключевую роль играет процедура