2.2. Комбинаторный поиск
Для нахождения точного решения многих задач выбора требуется организация полного перебора траекторий задачи. Существует два общих подхода организации такого перебора.
Первый, поиск с возвращением, ищет решение, пытаясь расширить частное решение. На каждом шаге поиска (в каждой ситуации), если расширение текущего частного решения невозможно (наступила тупиковая ситуация), то осуществляется возврат к более короткому частному решению и производится попытка снова продолжить поиск. Процесс заканчивается, когда найдено решение или все ситуации стали тупиковыми.
Второй метод, метод решета, является логическим дополнением к поиску с возвращением. При его использовании осуществляется попытка исключить объекты, не являющиеся решением, вместо того, чтобы искать сами решения.
Поиск с возвращением
Идею поиска с возвращением легче всего понять в связи с задачей прохода через лабиринт или задачей обхода вершин графа - задачей поиска на графе. Различают две стратегии поиска – в глубину и в ширину.
Поиск в глубину на графе G=(V,E) осуществляется по следующим правилам:
1. Начинаем поиск с произвольной вершины r. В качестве текущей вершины v берем вершину r.
2. Из текущей вершины v двигаемся в любую, ранее не пройденную вершину w, если такая вершина найдется (если вершины w нет, см. пункт 3). Запоминаем дугу, по которой мы попали в вершину w. В качестве текущей вершины v берем вершину w.
3. Если из вершины v мы не можем попасть в ранее не пройденную вершину w, то возвращаемся в вершину x, из которой мы попали в v. В качестве текущей вершины v берем вершину x.
4. Процесс поиска (пункты 2, 3) заканчивается, когда мы пытаемся вернуться назад из вершины, с которой начался поиск (вершина r).
Второе правило говорит о том, как надо расширять текущее решение, а третье – о том, как выходить из тупиковой ситуации.
При поиске в ширину порядок исследования дуг графа отличается. Поиск в ширину производится следующим образом:
1. Начинаем поиск с произвольной вершины r. Формируем множество текущих вершин A, включив в него вершину r.
2. Идем в ранее не пройденные вершины по всем дугам с начальной вершиной из множества A. Запоминаем эти дуги. Формируем множество A, включив в него конечные вершины пройденных дуг.
3. Процесс поиска (пункт 2) заканчивается, когда множество A станет пустым.
Процесс поиска с возвращением удобно представлять в виде дерева поиска. Вершины такого дерева соответствуют достижимым ситуациям. Вершина, соответствующая начальной ситуации, называется корнем дерева. Вершины, соответствующие тупиковым ситуациям, называются листьями дерева.
Пример. 4. Необходимо отмерить 6 литров воды, пользуясь водопроводным краном и двумя кувшинами емкостью 5 и 7 литров.
Пусть (a,b) обозначает достижимую ситуацию, в которой первый и второй кувшины содержат a и b литров воды соответственно.
В данной задаче начальная ситуация – (0,0), т.е. оба кувшина пусты. В каждой из ситуации возможны следующие действия:
a) долить первый кувшин;
б) долить второй кувшин;
в) вылить воду из первого кувшина;
г) вылить воду из второго кувшина;
д) вылить воду из первого кувшина во второй, освободив при этом первый кувшин или долив второй;
е) вылить воду из второго кувшина в первый, освободив при этом второй кувшин или долив первый.
Откажемся от выполнения операций, которые не ведут к изменению текущей ситуации (не имеет смысла выливать воду из пустого кувшина или доливать в полный). Также откажемся от рассмотрения уже встречающихся ситуаций, что гарантирует сходимость решающего процесса, и позволяет перечислить все достижимые ситуации.
Дерево поиска изображено на рис. 3. Вершина, соответствующая ситуации (0,0) – корень дерева. Вершины, соответствующие ситуациям (5,7), (0,6) и (0,6) - листья дерева. При построении дерева в ширину гарантируется нахождение кратчайшего пути к решению.
Рассмотренные задачи принадлежат к классу так называемых лабиринтных задач. Для них характерно сильное ограничение информации, используемой при поиске решения. Поэтому, в каждой ситуации приходится рассматривать все возможные действия, за исключением лишь тех действий, которые приводят к уже исследованным ситуациям. Для построения более эффективных алгоритмов необходимо иметь больший объем информации о свойствах искомых решений задачи. Выявление этой информации должно проводиться на основе содержательного исследования конкретных задач.
Разработка методов решения конкретных задач связывается с конкретизацией понятий “ситуация” и “элементарный шаг”, с определением способов конструирования решений, с введением некоторых оптимизирующих правил.
Общим средством повышения эффективности решающего процесса является редуцирование, т.е. упрощение текущей ситуации, сокращающее объем вычислений, проводимых при анализе множества вытекающих из нее вариантов. Конкретные способы редуцирования зависят от класса задач.