5.5. СТОИМОСТИ ДЕРЕВЬЕВ РЕШЕНИЯ

В переборах в пространстве состояний у нас была возможность воспользоваться для упорядочения процесса раскрытия вершин эвристически выводимыми оценочными функциями. Ключевым понятием при определении этих оценочных функций

было понятие эвристической функции, оценивающей стоимость оптимального пути от некоторой вершины до цели. В «И/ИЛИ» деревьях соответствующее понятие связано с оценкой стоимости дерева решения с корнем в данной вершине. Разумеется, прежде чем решать, как давать оценку стоимости дерева решения с корнем в данной вершине, надо определить, что мы будем понимать под стоимостью «И/ИЛИ» решения.

Нетрудно определить два различных понятия, каждое из которых приписывает определенные стоимости дугам дерева решения: суммарную стоимость, представляющую собой сумму стоимостей всех дуг дереве решения, и максимальную стоимость, определение которой основано на понятии пути по дереву решения. (Назовем путем по дереву с корнем в вершине последовательность вершин дерева, где — заключительная вершина, а вершина — дочерняя для при Сумму стоимостей дуг, связывающих вершины некоторого пути, будем называть стоимостью пути. Максимальная стоимость — это стоимость пути по дереву решения, имеющего максимальную стоимость.

Рис. 5.7. Два решающих дерева и их стоимости.

Эти определения можно пояснить на деревьях решений, показанных на рис. 5.7, на котором числа, стоящие около дуг, указывают стоимости последних. Здесь имеются два решения. Одно из них выделено жирными линиями (решение А), а другое (решение В) — перечеркнутыми линиями. У решения А суммарная стоимость равна 20, максимальная равна 15, а у решения В суммарная стоимость равна 18, максимальная равна 17. Какое из этих решений предпочтительнее, зависит, конечно, от того, какую стоимость мы пытаемся минимизировать.

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

Дерево решения само по себе является поддеревом некоторого неявно заданного «И/ИЛИ» дерева, определяемого

начальным описанием задачи, множеством операторов сведения задачи к подзадачам и множеством элементарных задач. Внутри всего неявно заданного «И/ИЛИ» дерева мы хотим найти дерево решения с минимальной стоимостью. Такое дерево решения будем называть оптимальным деревом. Обозначим через стоимость оптимального дерева решения с корнем в начальной вершине Дадим рекурсивное определение минимальной стоимости через минимальную стоимость дерева решения с корнем в любой вершине Будем обозначать стоимость дуги между вершиной и ее дочерней вершиной через

1. Если — заключительная вершина (отвечающая элементарной задаче), то

2. Если не является заключительной вершиной и имеет в качестве своих дочерных вершин вершины типа «ИЛИ», то

3. Если не является заключительной вершиной и имеет в качестве своих дочерних вершин вершины типа «И», то для суммарных стоимостей

а для максимальных стоимостей

Разумеется, функция не определена, если вершина неразрешима.