13.4.2. Программа поиска

13.4.2. Программа поиска

Программа, в которой реализованы идеи предыдущего раздела, показана на рис. 13.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой программы, давайте рассмотрим тот способ представления дерева поиска, который в ней используется.

Существует несколько случаев, как показано на рис. 13.11. Различные формы представления поискового дерева возникают как комбинации следующих возможных вариантов, относящихся к размеру дерева и к его "решающему статусу".

• Размер:

 (1) дерево состоит из одной вершины (листа) или

 (2) оно имеет корень и (непустые) поддеревья.

• Решающий статус:

 (1) обнаружено, что дерево соответствует решению задачи (т.е. является решающим деревом) или

 (2) оно все еще решающее дерево-кандидат.

Рис. 13.11. Представление дерева поиска.

Основной функтор, используемый для представления дерева, указывает, какая из комбинаций этих воз-можностей имеется в виду. Это может быть одна из следующих комбинаций:

лист  решлист  дер  решдер

Далее, в представление дерева входят все или некоторые из следующих объектов:

• корневая вершина дерева,

• F-оценка дерева,

• стоимость С дуги И/ИЛИ-графа, ведущей в корень дерева,

• список поддеревьев,

• отношение (И или ИЛИ) между поддеревьями.

Список поддеревьев всегда упорядочен по возрастанию F-оценок. Поддеревья, являющиеся решающими деревьями, помещаются в конец списка.

Обратимся теперь к программе рис. 13.12. Отношение самого высокого уровня — это

и_или( Верш, РешДер)

где Верш — стартовая вершина. Программа строит решающее дерево (если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции h, которую использует алгоритм. Существует теорема, в которой говорится о том, как оптимальность решения зависит от h. Эта теорема аналогична теореме о допустимости алгоритма поиска с предпочтением в пространстве состояний (гл. 12). Обозначим через С( В)  стоимость оптимального решающего дерева для вершины В. Если для каждой вершины В И/ИЛИ-графа эвристическая оценка  h(B)?C(B), то гарантируется, что процедура и_или найдет оптимальное решение. Если же h не удовлетворяет этому условию, то найденное решение может оказаться субоптимальным. Существует тривиальная эвристическая функция, удовлетворяющая условию оптимальности, а именно h = 0 для всех вершин. Ее недостатком является отсутствие эвристической силы.

Основную роль в программе рис. 13.12 играет отношение

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

Дер и Предел — его "входные" аргументы, а Дер1 и ЕстьРеш — "выходные". Аргументы имеют следующий смысл:

Дер — дерево поиска, подлежащее расширению.

Предел — предельное значение F-оценки, при котором еще разрешено наращивать дерево Дер.

ЕстьРеш — индикатор, значения которого указывают на то, какой из следующих трех случаев имеет место:

(1) ЕстьРеш = да: Дер можно "нарастить" (с учетом ограничения Предел) таким образом, чтобы образовалось решающее дерево Дер1.

(2) ЕстьРеш = нет: дерево Дер можно расширить до состояния Дер1, для которого F-оценка превосходит Предел, но прежде чем F-оценка превзошла Предел, решающее дерево не было обнаружено.

(3) ЕстьРеш = никогда: Дер не содержит решения.

В зависимости от случая Дер1 — это либо решающее дерево, либо Дер, расширенное до момента перехода через Предел; если ЕстьРеш = никогда, то переменная Дер1 неинициализирована.

Процедура

расширспис( Деревья, Предел, Деревья1, ЕстьРеш)

аналогична процедуре расширить. Так же, как и в процедуре расширить, Предел задает ограничение на рост дерева, а ЕстьРеш — это индикатор, указывающий, каков результат расширения ("да", "нет" или "никогда"). Первый аргумент — это, на этот раз, список деревьев (И-список или ИЛИ-список):

Деревья = или:[Д1, Д2, ...] или

Деревья = и : [Д1, Д2, ...]

Процедура расширспис выбирает из списка Деревья наиболее перспективное дерево (исходя из F-оценок). Так как деревья в списке упорядочены, таким деревом является первый элемент списка. Наиболее перспективное дерево подвергается расширению с новым ограничением Предел1. Значение Предел1 зависит от Предел, а также от других деревьев списка. Если Деревья — это ИЛИ-список, то Предел1 устанавливается как наименьшая из двух величин: Предел и F-оценка следующего по "качеству" дерева из списка Деревья. Если Деревья — это И-дерево, то Предел1 устанавливается равным Предел минус сумма F-оценок всех остальных деревьев из списка. Значение переменной Деревья1 зависит от случая, задаваемого индикатором ЕстьРеш. Если ЕстьРеш = нет, то Деревья1 — это то же самое, что и список Деревья, причем наиболее перспективное дерево расширено с учетом ограничения Предел1. Если ЕстьРеш = да, то Деревья1 — это решение для всего списка Деревья (найденное без выхода за границы значения Предел). Если ЕстьРеш = никогда, то переменная Деревья1 неинициализирована.

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

/* ПРОГРАММА И/ИЛИ-ПОИСКА С ПРЕДПОЧТЕНИЕМ

Эта программа порождает только одно решение. Гарантируется, что это решение самое дешевое при условии, что используемая эвристическая функция является нижней гранью реальной стоимости решающих деревьев.

Дерево поиска имеет одну из следующих форм:

дер( Верш, F, С, Поддеревья) дерево-кандидат

лист( Верш, F, C)            лист дерева поиска

решдер( Верш, F, Поддеревья) решающее дерево

решлист( Верш, F)            лист решающего дерева

С - стоимость дуги, ведущей в Верш

F = С + H, где H - эвристическая оценка оптимального решающего дерева с корнем Верш

Список Поддеревья упорядочен таким образом, что

(1) решающие поддеревья находятся в конце списка;

(2) остальные поддеревья расположены в порядке возрастания F-оценок

*/

:- op( 500, xfx, :).

:- op( 600, xfx, --->).

и_или( Верш, РешДер) :-

 расширить( лист( Верш, 0, 0), 9999, РешДер, да).

  % Предполагается, что 9999  >  любой F-оценки

% Процедура расширить( Дер, Предел, НовДер, ЕстьРеш)

% расширяет Дер в пределах ограничения Предел

% и порождает НовДер с "решающим статусом" ЕстьРеш.

% Случай 1:  выход за ограничение

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

 f( Дер, F),  F > Предел, !. % Выход за ограничение

% В остальных случаях F ? Предел

% Случай 2:  встретилась целевая вершина

расширить( лист( Верш, F, С), _, решлист( Верш, F), да) : -

 цель( Верш), !.

% Случай 3:  порождение преемников листа

расширить( лист( Верш, F,C), Предел, НовДер, ЕстьРеш) :-

 расшлист( Верш, С, Дер1), !,

 расширить( Дер1, Предел, НовДер, ЕстьРеш);

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

% Случай 4:  расширить дерево

расширить( дер( Верш, F, С, Поддеревья),

 Предел, НовДер, ЕстьРеш) :-

 Предел1 is Предел - С,

 расширспис( Поддеревья, Предел1, НовПоддер, ЕстьРеш1),

 продолжить( ЕстьРеш1, Верш, С, НовПоддер, Предел,

  НовДер, ЕстьРеш).

% расширспис( Деревья, Предел, Деревья1, ЕстьРеш)

% расширяет деревья из заданного списка с учетом

% ограничения Предел и выдает новый список Деревья1

% с "решающим статусом" ЕстьРеш.

расширспис( Деревья, Предел, Деревья1, ЕстьРеш) :-

 выбор( Деревья, Дер, ОстДер, Предел, Предел1),

 расширить( Дер, Предел1, НовДер, ЕстьРеш1),

 собрать( ОстДер, НовДер, ЕстьРеш1, Деревья1, ЕстьРеш).

% "продолжить" решает, что делать после расширения

% списка деревьев

продолжить( да, Верш, С, Поддеревья, _,

 решдер( Верш, F, Поддеревья), да): -

 оценка( Поддеревья, H), F is С + H, !.

продолжить( никогда, _, _, _, _, _, никогда) :- !.

продолжить( нет, Верш, С, Поддеревья, Предел,

 НовДер, ЕстьРеш) :-

 оценка( Поддеревья, H), F is С + H, !,

 расширить( дер( Верш, F, С, Поддеревья), Предел,

  НовДер, ЕстьРеш).

% "собрать" соединяет результат расширения дерева со списком деревьев

собрать( или : _, Дер, да, Дер, да):- !. % Есть решение ИЛИ-списка

собрать( или : ДД, Дер, нет, или : НовДД, нет) :-

 встав( Дер, ДД, НовДД), !.  % Нет решения ИЛИ-списка

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

  % Больше нет кандидатов

собрать( или:ДД, _, никогда, или:ДД, нет) :- !.

  % Есть еще кандидаты

собрать( и : ДД, Дер, да, и : [Дер Э ДД], да ) :-

 всереш( ДД), !.             % Есть решение И-списка

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

  % Нет решения И-списка

собрать( и : ДД, Дер, ДаНет, и : НовДД, нет) :-

 встав( Дер, ДД, НовДД), !.  % Пока нет решения И-списка

% "расшлист" формирует дерево из вершины и ее преемников

расшлист( Верш, С, дер( Верш, F, С, Оп : Поддеревья)) :-

 Верш---> Оп : Преемники,

 оценить( Преемники, Поддеревья),

 оценка( Оп : Поддеревья, H), F is С + H.

 оценить( [], []).

оценить( [Верш/С | ВершиныСтоим], Деревья) :-

 h( Верш, H), F is С + H,

 оценить( ВершиныСтоим, Деревья1),

 встав( лист( Верш, F, С), Деревья1, Деревья).

% "всереш" проверяет, все ли деревья в списке "решены"

всереш([]).

всереш( [Дер | Деревья] ) :-

 реш( Дер),

 всереш( Деревья).

реш( решдер( _, _, _ ) ).

реш( решлист( _ , _) ).

f( Дер, F) :-              % Извлечь F-оценку дерева

 arg( 2, Дер, F), !.       % F - это 2-й аргумент Дер

% встав( Дер, ДД, НовДД) вставляет Дер в список

% деревьев ДД; результат - НовДД

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

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

 реш( Д1), !.

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

 реш( Д),

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

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

 f( Д, F), f( Д1, F1), F=< F1, !.

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

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

% "оценка" находит "возвращенную" F-оценку И/ИЛИ-списка деревьев

оценка( или :[Дер | _ ], F) :-

 % Первое дерево ИЛИ-списка - наилучшее

 f( Дер, F), !.

оценка( и :[], 0) :- !.

оценка( и : [Дер1 | ДД], F) :-

 f( Дер1, F1),

 оценка( и : ДД, F2),

 F is F1 + F2, !.

оценка( Дер, F) :-

 f( Дер, F).

% Отношение выбор( Деревья, Лучшее, Остальные, Предел, Предел1):

% Остальные - И/ИЛИ-список Деревья без его "лучшего" дерева

% Лучшее; Предел - ограничение для Списка Деревья, Предел1 -

% ограничение для дерева Лучшее

выбор( Оп : [Дер], Дер, Оп : [], Предел, Предел) :- !.

  % Только один кандидат

выбор( Оп : [Дер | ДД], Дер, Оп : ДД, Предел, Предел1) :-

 оценка( Оп : ДД, F),

 ( Оп = или, !, мин( Предел, F, Предел1);

   Оп = и, Предел1 is Предел - F).

мин( А, В, А) :- А < В, !.

мин( А, В, В).

Рис. 13.12. Программа поиска с предпочтением в И/ИЛИ-графе.

Еще одна процедура

собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш)

связывает между собой несколько объектов, с которыми работает расширспис. НовДер — это расширенное дерево, взятое из списка деревьев процедуры расширспис, ОстДер — остальные, не измененные деревья из этого списка, а ЕстьРеш1 указывает на "решающий статус" дерева НовДер. Процедура собрать имеет дело с несколькими случаями в зависимости от значения ЕстьРеш1, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

собрать( или : _, Дер, да, Дер, да).

означает: в случае, когда список деревьев — это ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево Дер. Остальные случаи легко понять из текста процедуры собрать.

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр (рис. 13.8). Оставляем это читателю в качестве упражнения.