Шрифт:
Размер:
(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 неинициализирована.
Процедура продолжить, вызываемая после расширения списка деревьев, решает, что делать дальше, в зависимости от результата срабатывания процедуры расширить. Эта процедура либо строит решающее дерево, либо уточняет дерево поиска и продолжает процесс его наращивания, либо выдает сообщение "никогда" в случае, когда было обнаружено, что список деревьев не содержит решения.
/* ПРОГРАММА И / ИЛИ-ПОИСКА С ПРЕДПОЧТЕНИЕМ
Эта программа порождает только одно решение. Гарантируется, что это решение самое дешевое при условии, что используемая эвристическая функция является нижней гранью реальной стоимости решающих деревьев.