Чтение онлайн

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

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

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

f( T) = min f( mi )

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, Преемники, ДД),

опт_f( ДД, F1),

расширить( П, д( В, F1/G, ДД), Предел, Дер1,

ЕстьРеш, Реш);

ЕстьРеш = никогда). % Нет преемников - тупик

расширить( П, д( В, F/G, [Д | ДД]), Предел, Дер1,

ЕстьРеш, Реш):-

F <= Предел,

опт_f( ДД, OF), мин( Предел, OF, Предел1),

расширить( [В | П], Д, Предел1, Д1, ЕстьРеш1, Реш),

продолжить( П, д( В, F/G, [Д1, ДД]), Предел, Дер1,

ЕстьРеш1, ЕстьРеш, Реш).

расширить( _, д( _, _, [ ]), _, _, никогда, _ ) :- !.

% Тупиковое дерево - нет решений

расширить( _, Дер, Предел, Дер, нет, _ ) :-

f( Дер, F), F > Предел. % Рост остановлен

продолжить( _, _, _, _, да, да, Реш).

продолжить( П, д( В, F/G, [Д1, ДД]), Предел, Дер1,

ЕстьРеш1, ЕстьРеш, Реш):-

( ЕстьРеш1 = нет, встав( Д1, ДД, НДД);

ЕстьРеш1 = никогда, НДД = ДД),

опт_f( НДД, F1),

расширить( П, д( В, F1/G, НДД), Предел, Дер1,

ЕстьРеш, Реш).

преемспис( _, [ ], [ ]).

преемспис( G0, [В/С | ВВ], ДД) :-

G is G0 + С,

h( В, Н), % Эвристика h(B)

F is G + Н,

преемспис( G0, ВВ, ДД1),

встав( л( В, F/G), ДД1, ДД).

% Вставление дерева Д в список деревьев ДД с сохранением

% упорядоченности по f-оценкам

встав( Д, ДД, [Д | ДД] ) :-

f( Д, F), опт_f( ДД, F1),

F =< F1, !.

встав( Д, [Д1 | ДД], [Д1 | ДД1] ) ) :-

встав( Д, ДД, ДД1).

% Получение f-оценки

f( л( _, F/_ ), F). % f-оценка листа

f( д( _, F/_, _ ) F). % f-оценка дерева

опт_f( [Д | _ ], F) :- % Наилучшая f-оценка для

f( Д, F). % списка деревьев