5.7. АЛГОРИТМ УПОРЯДОЧЕННОГО ПЕРЕБОРА ДЛЯ ДЕРЕВЬЕВ ТИПА «И/ИЛИ»

Мы можем теперь дать перечень шагов, определяющий алгоритм упорядоченного перебора для деревьев «И/ИЛИ». Эти шаги лишь немного отличаются от этапов метода полного перебора:

(1) Поместить начальную вершину в список вершин с названием ОТКРЫТ и вычислить

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

(3) Выбрать некоторую концевую вершину дерева которая имеется в списке ОТКРЫТ, и поместить ее в список вершин с названием ЗАКРЫТ. Обозначить эту вершину через

(4) Если — заключительная вершина, то пометить вершину как разрешимую и продолжать. В противном случае перейти к (9).

(5) Применить к то процедуру разметки разрешимых вершин.

(6) Если начальная вершина помечена как разрешимая, то на выход выдается То в качестве дерева решения; в противном случае продолжать.

(7) Изъять из списка ОТКРЫТ все вершины, имеющие разрешимые предшествующие им вершины.

(8) Перейти к (2).

(9) Применить к оператор Г и построить все дочерние вершины для Если дочерних вершин нет, то пометить

вершину как неразрешимую и перейти к следующему этапу. В противной случае перейти к (14).

(10) Применить к процедуру разметки неразрешимых вершин.

(11) Если начальная вершина помечена как неразрешимая, то на выход подается сигнал о неудаче. В противном случае продолжать далее.

(12) Изъять из списка ОТКРЫТ все вершины, имеющие неразрешимые предшествующие им вершины.

(13) Перейти к (2).

(14) Поместить эти дочерние вершины в список ОТКРЫТ и провести от них указатели назад к вершине Вычислить величины для этих вершин. Пересчитать величины Н для вершины и для предшествующих ей вершин.

(15) Перейти к (2).

Блок-схема этой процедуры изображена на рис. 5.8. (Заметим, что в частном случае, когда не возникает вершин типа «И», в этой процедуре перебор дерева осуществляется способом, идентичным методу упорядоченного перебора в пространстве состояний. Кроме того, если стоимости дуг равны единице, для концевых вершин и используется определение максимальной стоимости, то эта процедура приводит к тем же результатам, что и процедура полного перебора.)

На рис. 5.9 приведена последовательность гипотетических деревьев перебора, иллюстрирующая работу нашего алгоритма упорядоченного перебора. Предположим, что раскрытие начальной вершины привело к дереву перебора, изображенному на рис. 5.9, а. Число, стоящее рядом с вершиной, указывает величину . Для концевых вершин эти величины служат эвристическими оценками суммарных стоимостей решений соответствующих задач. Величины Я для других вершин этого дерева получаются в результате применения определения для суммарных стоимостей в предположении об единичной стоимости ребер. Исходя из этих значений Я, можно получить потенциальное дерево решения то, которое по оценке должно быть верхней частью оптимального дерева решения. Это дерево то выделено жирными ветвями.

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

(кликните для просмотра скана)

(кликните для просмотра скана)

одного раскрытия мы, наконец, получаем дерево решения, выделенное на рис. 5.9, г жирными ветвями. Суммарная стоимость этого дерева равна 9, как показывают вычисления с использованием окончательных значений