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




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


Для одновершинных деревьев (листов) n  остается первоначальное определение

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

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

        f( T) = min  f( mi )
                      i
Программа поиска с предпочтением, составленная в соответствии с приведенными выше общими соображениями, показана на рис 12.3. Ниже даются некоторые дополнительные пояснения.

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

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

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

line();

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

        эврпоиск( Старт, Решение):-
                макс_f( Fмакс).
                    % Fмакс  >  любой  f-оценки
                расширить( [ ], л( Старт, 0/0), Fмакс, _, да, Решение).

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

        расширить( П, л( В, F/G), Предел, Дер1, ЕстьРеш, Реш) :-
            F <= Предел,
            ( bagof( B1/C, ( после( В, В1, С), not принадлежит( В1, П)),
                            Преемники),   !,



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