10.3. Деревья и их применение

10.3.0. Определения

Деревом называется направленный граф, содержащий единственный выделенный узел, называемый корнем, в который не входит ни одной дуги. В любой другой узел такого графа входит в точности одна дуга.

Рис. 10.3. Дерево.

Циклы и петли (дуги, выходящие из какого-нибудь узла и входящие в него же) запрещены. Узлы, из которых не выходит ни одной дуги, называются листьями-, узлы, имеющие и входящую и выходящую дуги, называются внутренними (пример такого графа приведен на рис. 10.3). Правда, вопреки „древесной" терминологии такой граф представляет собой множество скорее родового, нежели растительного происхождения; это видно из того, что нижележащие узлы являются потомками, а вышележащие — предками. Заметим, что любой узел дерева будет корнем

поддерева, состоящего из этого узла и его потомков. Учитывая это, мы иногда будем говорить о поддереве, начинающемся из узла

Деревья используются в искусственном интеллекте двумя способами: для представления задач, решаемых сведением к подзадачам, и для моделирования ходов в формальных играх. В первом случае концевые точки дерева (т. е. листья) должны достигаться до того, как задача решена... по крайней мере до решения ее в наиболее очевидном представлении. Во втором случае, т. е. в игровых графах, дерево раскрывается постепенно, без возвращений назад, поскольку сделанный ход избавляет игрока от необходимости исследования альтернативных ходов. В обоих случаях нельзя непосредственно применять только что изложенные алгоритмы поиска в пространстве состояний. Вместо этого обычно применяются специальные алгоритмы поиска на дереве. В дальнейшем, однако, мы увидим, что это не всегда обязательно.

10.3.1. Деревья сведения задачи к подзадачам

Основную идею построения дерева сведения задачи к подзадачам можно продемонстрировать на примере нахождения неопределенного интеграла

Дерево решения изображено на рис. 10.4. Можно было бы представить числитель в (38) в виде и сократить со знаменателем, что дало бы более простое эквивалентное выражение

С другой стороны, можно было бы воспользоваться равенством Тогда

(39) и (40) являются ИЛИ-подцелями исходной задачи (см. рис. 10.4). Каждая из них в свою очередь имеет свои подцели. Интеграл (39) можно вычислить как сумму его частей, при условии что решения

и

можно найти. Интегрирование (40) дает дерево несколько более сложных подцелей. Заметим, что (41), (42) и дерево выражений, составляющих (40), следует определить раньше, чем будут решены те задачи, которые их породили. Следовательно, эти подзадачи являются И-подцелями порождающей цели. Наконец, рассмотрим интегралы (41) и (42). Они представляют собой непосредственно решаемые задачи, т. е. задачи, решение которых можно получить, не порождая никаких подцелей. (В данном случае решения можно найти в таблицах интегралов.)

Рис. 10.4. Дерево решения задачи.

Идея решения задачи с помощью графа состоит в том, чтобы раскрывать его до тех пор, пока не будет найдена непосредственно решаемая задача. Она становится листом дерева, и, когда она достигается, записывается ее решение. Затем решающая программа вводит это решение в качестве составляющей во все возможные задачи высших уровней, отмечая, если надо, каждую решенную задачу более высокого уровня. В качестве иллюстрации рассмотрим программу, которая постепенно порождает подзадачи, отмечает их связь с задачей-предком и после того, как подзадача поставлена, проверяет ее по таблице интегралов. После того как образован интеграл программа запомнит его решение и, продвигаясь в обратном направлении, найдет, что это — одно из решений, необходимых для решения И-подзадачи задачи Затем программа сформирует интеграл который также есть в таблице

интегралов. Этим кончится решение множества И-подзадач. Следовательно, после соответствующего объединения их порождающая задача будет решена. Затем программа обнаружит, что она решила ИЛИ-подзадачу, т. е. главную задачу, которую отметит как решенную; на этом работа программы заканчивается.

Какими свойствами мы хотели бы наделить программу поиска графов сведения задачи к подзадачам? При каждом ветвлении типа ИЛИ программа должна выбирать наиболее легкую подзадачу. Для этого программа должна иметь какой-нибудь способ оценки сложности задачи. Эвристическая функция Я обеспечивает этот механизм при решении задач в пространстве состояний; для поиска на дереве нужна аналогичная функция. В некоторых ситуациях одна подзадача может быть составляющей нескольких подзадач более высокого уровня. Программа должна обнаружить этот факт и решить повторяющуюся задачу только один раз. Для примера рассмотрим вычисление двойного интеграла

Выражение встречается дважды. Если бы прямой метод раскрытия и решения подзадач, который применялся в предыдущем примере интегрирования, применялся и здесь, это выражение было бы проинтегрировано дважды, что, очевидно, излишне. С другой стороны, потребовались бы значительный объем памяти для хранения решенных подзадач и создание механизма извлечения информации, чтобы определить, не является ли „новая“ подзадача в действительности старой (для обсуждения некоторых технических публикаций по этой теме см. работу Гелернтера и Рочестера, 1958). Другая проблема, возникающая в связи с многократным вхождением подзадач, заключается в том, что надо учитывать как трудность, так и важность подзадачи. Часто решение трудной подзадачи, составляющей часть многих задач более высокого уровня, может оказаться рациональнее, чем постепенное решение легких задач. В случаях когда решение некоторой подзадачи — неизбежный этап решения главной задачи, этот вопрос, очевидно, не возникает.

Предлагались различные алгоритмы для эффективного поиска на графах сведения задачи к подзадачам. Приведем решение, которое дали Ченг и Слейгл (1971); в нем поиск на дереве рассматривается как особый случай задачи нахождения эффективного пути от начального состояния к целевому в пространстве состояний. Элегантность этого алгоритма проявляется в том, что как только

совершен переход от деревьев к графам пространства состояний, доказательство допустимости и оптимальности алгоритма вытекает непосредственно из доказательства допустимости и оптимальности алгоритма эвристического поиска, описанного в предыдущем разделе. В основе алгоритма лежит тот факт, что если дерево решения задачи содержит ветвления только типа ИЛИ, то путь от корня к каждому листу есть решение исходной задачи (для ясности советуем проанализировать рис. 10.4). Далее, граф сведения задачи к подзадачам можно рассматривать как граф задачи в пространстве состояний, если возможно такое представление исходной задачи, при котором она содержит ветвления только типа ИЛИ. Тогда для нахождения пути от корня до ближайшего листа можно применить метод эвристического поиска, оптимальность которого для решения задач в пространстве состояний уже доказана. Как и прежде, надо определить эвристическую функцию для всех таких подзадач х, что где - „истинная" трудность решения подзадачи.

Нам нужна процедура преобразования дерева сведения задачи к подзадачам в граф, в котором все узлы, кроме непосредственно соединенных с листьями, имеют ветвления типа ИЛИ. Листья будут конъюнкциями „основных" подзадач, таких, что если решить все эти подзадачи, связанные с некоторым узлом дерева, то получится решение исходной задачи. Надо определить подходящие функции для прохождения графа. Пусть трудность решения задачи у из множества не зависит от трудностей решения остальных задач из этого множества; тогда трудность решения задач всего множества равна

Если удовлетворяет указанным выше требованиям эвристической функции, то

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

Необходимые конъюнкции подзадач, соответствующие листьям, можно выразить алгебраически. Предположим, что задачу А можно решить, если решены либо подзадачи В и С, либо и (С или В), т. е.

Равенство (47) можно переписать в виде

Если какая-нибудь из конъюнкций решена, то решена задача А. Это преобразование изображено на рис. 10.5.

Рис. 10.5. Преобразование дерева сведения задачи к подзадачам в граф, в котором все внутренние узлы, не соединенные непосредственно с листьями, являются ИЛИ-узлами.

Теперь займемся преобразованием дерева решения задачи. Пусть исходная задача будет корнем дерева. Следующие узлы выделяем, записывая корень или другой узел в терминах подзадач и приводя соответствующее соотношение к дизъюнктивной нормальной форме, как в (48). На каждом шаге для выбора следующего раскрываемого узла (подзадачи) используется функция

где и определены выше. Если подзадачу можно решить сразу, она помечается словом верно. Исходная задача решена, если один из членов в дизъюнктивной нормальной форме этой задачи состоит только из верных подзадач.

На рис. 10.6 показан граф решения абстрактной задачи X с повторяющимися подзадачами. Каждой подзадаче (некорневому узлу) приписывается эвристическая оценка трудности решения. Будем считать, что стоимость выделения задачи как части задачи более высокого уровня равна 1. Работа алгоритма состоит в следующем:

Запишем задачу X через ее подзадачи, т. е.

Вначале поместим эти составляющие с их оценками стоимости решения в список ОТКРЫТ:

Допустим, что мы выбрали подзадачу . Представим ее в виде

Тогда

— непосредственно решаемая задача, так что она помечается словом верно и удаляется. В результате

Далее находим, что задача Е эквивалентна Поэтому, если решена задача то решена и Е.

Рис. 10.6. Решение абстрактной задачи. Число рядом с буквой указывает оценку трудности задачи. Стоимость каждой дуги равна 1. (Задача взята из работы Ченга и Слейгла, 1971, стр. 123.)

Так как задача решена, то один из членов дизъюнктивной нормальной формы исходной задачи также решен, а отсюда следует, что и исходная задача решена.

Этот алгоритм обеспечивает действенный и эффективный поиск на графах сведения сложных задач к подзадачам.