Глава 3. МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

3.1. ПРОЦЕССЫ ПОИСКА НА ГРАФЕ

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

Начальная вершина соответствует описанию начального состояния.

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

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

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

Этапы, указанные выше, описывают просто основные элементы процесса перебора подобно описанию, даваемому

блок-схемой недетерминированной программы. При полном описании процесса перебора нужно еще задать порядок, в котором следует раскрывать вершины. Если вершины раскрываются в том же порядке, в котором они порождаются, то получается процесс, который называется полным перебором (breadth-first process). Если же сначала раскрывается всегда та вершина, которая была построена самой последней, то получается процесс перебора в глубину (depth-first process). Процессы полного перебора и перебора в глубину можно назвать также процедурами слепого перебора, поскольку расположение цели не влияет на порядок, в котором раскрываются вершины.

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

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