3.6.1. Алгоритм полного перебора

Рассмотрим метод полного перебора [1, 2]. Суть метода опишем на примере двумерного пространства обобщенных координат. Пусть требуется найти путь в двумерном пространстве, исходящий из q⁰, приходящий в q^Т, удовлетворяющий конструктивным ограничениям и не пересекающий ни одну из запрещенных конфигураций (рис. 3.5).

Дискретизируем пространство обобщенных координат и будем теперь рассматривать только конфигурации, лежащие на узлах сетки. Запрещенные конфигурации обозначим крестиками (конфигурации, недостижимые из-за конструктивных ограничений, тоже считаем запрещенными и тоже обозначаем крестиками). В прямоугольнике, определенном конфигурациями q⁰ и q^T , обозначим каждый узел решетки своей буквой (рис. 3.6).

Узлы сетки будем называть вершинами. В двумерном случае для каждой вершины соседними являются 8 вершин (если все они разрешенные). В случае n-мерного пространства число вершин, являющихся соседними для каждой вершины, будет равно 3ⁿ–1.

Алгоритм полного перебора заключается в следующем:

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

2. Если список ОТКРЫТ пуст, то на выход подаётся сигнал о неудаче поиска, в противном случае переходить к следующему шагу.

3. Взять первую вершину из списка ОТКРЫТ и перенести её в список ЗАКРЫТ; назовём эту вершину n.

4. Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n.

5. Е сли какие-нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2).

Спланируем путь для случая, изображенного на рис.3.6. Соседние вершины к некоторой вершине, например А, будем получать, проделав определенные операции: сначала отступаем вправо, а потом совершаем обход против часовой стрелки.

То есть для вершины А соседними вершинами будут F и E. Выполнение алгоритма состоит в последовательном изменении списков ОТКРЫТ и ЗАКРЫТ (рис. 3.8).

В результате получим путь AEI J.

Алгоритм полного перебора применим для n-мерного пространства состояний. Алгоритм за конечное число шагов либо находит путь, либо сообщает, что путь найден быть не может.

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

Между этими точками могут быть запрещенные точки, которые выпали из поля нашего зрения при наложении сетки. Поэтому сетку желательно делать возможно более густой, что, в свою очередь, приводит к увеличению времени расчета пути и стремлению этого времени к бесконечности. После получения вышеуказанного конечного множества точек необходимо каким-то образом соединить эти точки непрерывными линиями, учитывая при этом требование неналегания на запрещенные точки. Соединять вершины можно методами, предложенными в пп. 3.2–3.5.

ОТКРЫТ	ЗАКРЫТ
A	A:n
AF	AF:n
AE	AE:n
AEI	AEI:n
AED
AEC
AEI J
AEI K

Рис. 3.7