ГЛАВА 5. МЕТОДЫ ПОИСКА ПРИ СВЕДЕНИИ ЗАДАЧ К СОВОКУПНОСТИ ПОДЗАДАЧ

5.1. ПРОЦЕССЫ ПЕРЕБОРА (ПОИСКА) НА ГРАФАХ ТИПА «И/ИЛИ»

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

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

Разрешимые вершины

Заключительные вершины (соответствующие элементарным задачам) разрешимы.

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

Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «И», разрешима тогда и только тогда, когда разрешимы все ее дочерние вершины.

Неразрешимые вершины

Вершины, не являющиеся заключительными и не имеющие дочерних вершин, неразрешимы.

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

Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «И», неразрешима тогда и только

тогда, когда неразрешима по крайней мере одна из ее дочерних вершин.

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

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

Все процессы перебора, которые мы будем рассматривать, включают следующие этапы:

(1) Начальная вершина ассоциируется с начальным описанием задачи.

(2) Строятся множества дочерних вершин для начальной вершины с помощью тех операторов сведения задач к подзадачам, которые применимы. Пусть Г — такой комбинированный оператор, применение которого дает нам все дочерние вершины для данной вершины. Мы снова назовем этот процесс применения Г к вершине раскрытием вершины. (Напомним, что если при этом строится более одного множества дочерних вершин типа «И», то каждое множество, - содержащее более одного элемента, группируется под промежуточной вершиной типа «ИЛИ».)

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

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

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

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

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

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

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

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

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

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