5.4. ПЕРЕБОР НА ГРАФАХ ТИПА «И/ИЛИ»

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

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

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

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

Рис. 5.5. (см. скан) Некоторые «И/ИЛИ» графы.

При попытке определить процедуру перебора для графа (а не дерева) типа «И/ИЛИ» возникает ряд осложнений. Во-первых, разумное определение процедуры полного перебора было бы, вероятно, связано с выбором для очередного раскрытия той вершины из списка ОТКРЫТ, которая имеет наименьшую глубину. Теперь, однако, несколько труднее, чем в случае деревьев, дать хорошее определение глубины. Как и для обычных графов, глубина вершины в «И/ИЛИ» графе определяется следующим, образом:

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

Глубина любой другой вершины на 1 больше глубины самой ближайшей ее родительской вершины.

Второе осложнение связано с необходимостью установки указателей, идущих от данной вершины к более чем одной родительской вершине. Все эти указатели могут оказаться необходимыми при определении решающего графа. (Например, на рис. 5.6 обязательно должны содержаться в решении указатели, идущие от вершины 2 к вершинам 1 и 6.) С другой стороны, некоторые из этих кратных указателей могут и не потребоваться в решении (например, на рис. 5.6 в решение не должен входить указатель, идущий от вершины 3 назад к вершине 4).

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

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

Аналогично когда строятся дочерние вершины, следует провести специальную проверку, нет ли уже каких-нибудь из этих вершин в списке ЗАКРЫТ и не были ли они прежде помечены как разрешимые или как неразрешимые. Если при этом мы пришли к уже разрешимой (или неразрешимой) дочерней вершине по новому пути, то небходимо воспользоваться процедурой разметки, чтобы проверить, разрешима ли (или неразрешима ли) начальная вершина.

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