5.2. МЕТОД ПОЛНОГО ПЕРЕБОРА

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

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

(2) Взять первую вершину из списка ОТКРЫТ и поместить ее в список вершин с названием ЗАКРЫТ; обозначить эту вершину через

(3) Раскрыть вершину построив все ее дочерние вершины. Поместить эти дочерние вершины в конец списка ОТКРЫТ и провести от них указатели к вершине Если дочерних вершин не оказалось, то пометить вершину как неразрешимую и продолжать; в противном случае перейти к (8).

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

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

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

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

избежать ненужных затрат, связанных с попытками разрешить неразрешимые вершины.)

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

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

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

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

(11) Изъять из списка ОТКРЫТ все вершины, являющиеся разрешимыми или имеющие разрешимые предшествующие им вершины. (Этот шаг позволяет избежать ненужных затрат, связанных с поиском более одного пути решения задачи.)

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

Как и для обычных деревьев, глубина вершины в дереве типа «И/ИЛИ» определяется следующим образом:

Глубина начальной вершины равна 0.

Глубина любой другой вершины на 1 больше глубины ее родительской вершины (непосредственно ей предшествующей).

Рис. 5.2. «И/ИЛИ> дерево, показывающее порядок, в котором раскрываются вершины при полном переборе.

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

Пример последовательности, в которой раскрываются вершины в методе полного перебора, приведен на рис. 5.2. Числа, стоящие около вершин, указывают очередность раскрытия вершин, разрешимые вершины зачернены, а найденное дерево решения выделено жирными ветвями. Заметим, что после раскрытия девятой вершины и установления того, что ее дочерние вершины являются заключительными, вершины А, В и С удаляются из списка ОТКРЫТ.