ТИПИС

31

Глава 2

МЕТОДЫ ПОИСКА

32		Глава 2. Методы поиска

§ 2.1. Классификация методов поиска

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

Первая задача. Поиск состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Вторая задача. Определение расстояния, т. е. ограничение направления поиска или граничной глубины поиска Hi до заданного состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Третья задача. Выделение оптимального пути как цепочки Li = (f1, f2, …, fn) до заданного состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Четвертая задача. Определение модели распределения целевых состояний в пространстве поиска.

Пятая задача. Мониторинг состояний в пространстве поиска. Выделенные задачи позволяют разделить методы поиска на классы.

Кроме этого, особенность разделения методов поиска на классы базируется на

§ 2.1. Классификация методов поиска	33

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

Результат структурирования методов поиска на основе организации процедур и задач поиска представлен на рис. 2.1 в виде классификации.

МЕТОДЫ ПОИСКА

Слепые методы поиска

Поиск по лучу

Поиск в глубину

На основе

генерации

Параллельный метод

Простейшие Эвристиче-		Поиски в ширину
ские методы поиска

Метод Мура

На основе проверки

Метод ветвей и границ

Эвристические методы на основе оценочной функции

			Алгоритм А*
На основе
планирования
			Минимаксная процедура
	Рис. 2.1. Классификация методов поиска

Особенность процедуры генерации позволяет выделить представителей класса слепых методов поиска:

а) по лучу – (si fj = si+1); б) в глубину – (si Fi = Si+1);

в) параллельный метод – (Si fj = Si+1); г) в ширину – (Si Fi = Si+1).

34		Глава 2. Методы поиска

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

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

Существует множество представителей класса простейших эвристических методов поиска [5]. В каждом методе процедура проверки имеет свои особенности. Наиболее яркими с этой точки зрения являются методы Мура и метод ветвей и границ. Особенность данных методов практически перекрывает всю разновидность свойств иных простейших эвристических методов поиска. Так, метод Мура ориентирован на проверку состояний. Результат проверки определяет направление следующей генерации. Метод ветвей и границ ориентирован на проверку операторов, преобразующих состояния. Результат проверки определяет граничную глубину поиска, т. е. количество проводимых итераций поиска. С помощью простейших эвристических методов поиска на основе процедуры проверки, позволяющей сохранять апостериорную информацию, можно выполнить первую и вторую задачу поиска, т. е. найти не только необходимое состояние, но и расстояние до него относительно начального.

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

§ 2.1. Классификация методов поиска	35

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

Дополнительно под планированием подразумевают ограничения, накладываемые на пространство поиска, т. е. ограничения формирующие пространство поиска [3, 5]. В этом случае поиск в ограниченном пространстве называют перебором, выполняемым только с помощью метода Мура или минимаксной процедуры, но отнюдь не полным перебором. Методы, представленные в классификации на рис. 2.1, не могут гарантировать полного перебора. Методы полного перебора – это эвристические методы, прежде всего ориентированные на анализ свойств всех состояний пространства поиска. По этой причине методы полного перебора следует рассматривать как методы преследования цели [6, 8]. Обычно результатом работы методов полного переборы является математическая модель, характеризующая динамику оцениваемых свойств состояний пространства поиска.

Вэтом контексте следует отметить, что практически все представленные методы поиска могут быть реализованы только в предварительно организованном (спланированном) пространстве.

В[3] представлено множество моделей организации пространства поиска. Это прежде всего факторизованные пространства с постоянным или изменяющимся множеством иерархических подпространств, альтернативные пространства, динамические миры и множественные модели. Планирование поиска в заранее организованном пространства должно позволить значительно сократить ресурс ПС, необходимый для поиска.

Дальнейшая детализация классификации методов поиска имеет интеграционный характер. Например, относительно процедуры генерации методы поиска разделяются на методы поиска с круговым обзором (применяется генерация в ширину) и секторным обзором (все остальные случаи [7, 8]). Соответственно, наименьший сектор обзора пространства поиска имеет метод, использующий генерацию по лучу.

Взависимости от организации пространства состояний тот или иной способ обзора (генерации), проверки, планирования выполняемого в одно-

36		Глава 2. Методы поиска

направленном или n-направленном режиме поиска может иметь относительное преимущество.

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

Первая задача. Поиск состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Вторая задача. Определение граничной глубины, т. е. ограничение

направления поиска или кратчайшего расстояния Hi до заданного состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Третья задача. Определение оптимального пути как цепочки Li = (f1, f2, …, fn) до заданного состояния, нескольких заданных, всех состояний St на дереве или графе из одного, нескольких заданных, всех состояний So.

Четвертая задача. Определение модели распределения целевых состояний в пространстве поиска.

Пятая задача. Мониторинг состояний в пространстве поиска.

Видовым отличием классов методов поиска являются:

1)для слепых методов поиска – способы генерации;

2)для простейших эвристических методов поиска – способы накопления апостериорной информации о пространстве поиска;

3)для эвристических методов поиска на основе оценочной функции (априорной информации) – механизмы планирования поиска.

Методы поиска также различаются:

–применяемым обзором (методы с секторным и круговым обзором);

–режимом поиска (однонаправленные и n-направленные методы поиска);

–способом мониторинга пространства поиска (методы полного и неполного перебора).

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

§ 2.2. Процедура генерации	37

§ 2.2. Процедура генерации

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

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

Вметоде по лучу выполняется следующий алгоритм поиска:

1.Для очередного состояния si формируется множество применимых операторов Fi.

2.Если Fi , то выбирается один fj Fi, иначе – si является терминальным состоянием.

Если в организации пространства поиска имеются терминальные состояния, то следует ввести в алгоритм поиска механизм возврата в родительские состояния. Обычно следует вернуться на один шаг, чтобы вы-

брать иной fi Fi-1 для si-1, т. е. оператор, не порождающий терминальное состояние. Более подробное внимание алгоритмам обхода терминальных состояний будет уделено далее.

3.Состояние si раскрывается: si fj = si+1 (далее результат генерации будем обозначать термином фронт).

4.Если выполняется условие si+1 sjt St, то задача решена (выполняется одно из условий решения первой задачи), иначе – переход к п. 1 применительно для очередного состояния si+1.

38			Глава 2. Методы поиска
Начальное	о		СХЕМА ПОИСКА ПО ЛУЧУ
состояние	si
siо Sо		Операторы
	si	один fj Fi
Текущее
состояние si,			Процедура генерации
si+1
	si+1		si fj = si+1
Целевое
состояние
sjt St			Процедура проверки
	sjt		si+1 sjt St
	Рис. 2.2. Схема поиска по лучу
Схема поиска в глубину представлена на рис. 2.3.
Начальное	siо	СХЕМА ПОИСКА В ГЛУБИНУ
		Состояние
состояние
siо Sо		одно si Si
Текущие	si	Si	Процедура генерации
фронты			si Fi = Si+1
Si, Si+1
Целевое	Si+1		Процедура проверки
состояние
sjt St			si+1 Si+1, sjt St
	sjt
	Рис. 2.3. Схема поиска в глубину

§ 2.2. Процедура генерации	39

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

1.Для одной si Si формируется множество применимых операто-

ров Fi.

2.Если Fi = , то si является терминальным состоянием (при нали-

чии терминальных состояний используют иную sj Si).

3.Состояние si раскрывается: si Fi = Si+1.

4.Если выполняется условие si+1 Si+1, sjt St, то задача решена

(выполняется одно из условий решения первой задачи), иначе – переход к п. 1, но применительно для очередного фронта состояний Si+1.

В методе в ширину реализуется следующий алгоритм поиска:

1. Для всех si Si формируется множество применимых операторов Fi. 2. Если для всех si Si, Fi = , то решения не существует, иначе – п. 3.

3. Si раскрывается: Si Fi = Si+1.

4. Если выполняется условие si Si+1, sjt St, то задача решена (выполняется одно из условий решения первой задачи), иначе – переход к п. 1, применительно для очередного фронта состояний Si+1.

Схема поиска в ширину представлена на рис. 2.4.

	siо		СХЕМА ПОИСКА В ШИРИНУ
Начальное			Фронт
состояние			Si
siо Sо				Процедура генерации
	Si			Si Fi = Si+1
Текущие
фронты
Si, Si+1				Процедура проверки
		Si+1		si Si+1, sjt St
Целевое

состояние

sjt St

sjt

Рис. 2.4. Схема поиска в ширину

40		Глава 2. Методы поиска

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

фронта неопределенно зависит от Si и Fi . Неопределенность приводит к случайному принципу наполнения фронта состояниями.

Кроме этого, некоторые состояния могут многократно дублироваться

вочередном фронте. Определим это явление как цикличность, представ-

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

Для некоторых игровых задач при использовании в поиске генерации

вширину эта величина принимает вполне конкретные значения.

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

На практике для методов поиска, использующих секторные способы обзора при наличии терминальных состояний и колец в памяти ПС, необходимо хранить «родительские» состояния (фронты). Общая схема обхода терминальных состояний и способ формирования памяти в методе по лучу представлена на рис. 2.5.

Для поиска по лучу в память М записывается цепочка состояний. Началом цепочки является очередное состояние, для которого выполняет-

ся Fi >1, а продолжение составляют его дочерние состояния, для которых выполняется Fi = 1.

Далее состояния, для которых выполняется F > 1, будем называть состояниями возврата и обозначать в тексте полужирными символами

вида si, а состояния, для которых F = 1, – обычным шрифтом.

Так, цепочка (М = {si, si+1, si+2, …, si+n, …}) увеличивается при условии, что для сгенерированных дочерних состояний состояние si продолжа-

ет выполняться условие Fi = 1.

Если на некоторой итерации поиска будет сгенерировано терминальное состояние, то возврат осуществляется в начало цепочки М (рис. 2.5, слева). Далее, при выборе очередного оператора для состояния si необходимо исключить направление поиска, ведущее к терминальному состоянию.

Цепочка состояний хранится в памяти до тех пор, пока не будет сге-

нерировано дочернее состояние, для которого выполняется Fi > 1. В этом случае формируется новая цепочка, начиная с состояния si+p, т. е. М = {si+p, …} (рис. 2.5, справа), а предыдущая цепочка, началом которой было состояние si, полностью удаляется из памяти.