Prolog

можностей имеется в виду. Это может быть одна из следующих комбинаций:

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

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

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

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 неинициализирована.

Процедура