Неизвестно - Prolog

И / ИЛИ-графе ( h = 0) при решении задачи рис. 13.4.

прекращается. В результате процесс поиска не успевает "осознать", что h - это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу с . Поскольку в этот момент F( b) = 9, устанавливается верхняя граница для F( c) , равная 9. Дерево-кандидат с корнем с наращивается (с учетом установленного ограничения) до тех пор, пока не возникает ситуация, показанная на снимке Е. Теперь процесс поиска обнаруживает, что найдено решающее дерево (включающее в себя целевые вершины h и g ), на чем поиск заканчивается. Заметьте, что в качестве результата процесс поиска выдает наиболее дешевое из двух возможных решающих деревьев, а именно решающее дерево рис. 13.4(с).

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 -оценка превзошла Предел, решающее дерево не было обнаружено.