ТИПИС

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

СХЕМА ОБХОДА ТЕРМИНАЛЬНЫХ ВЕРШИН В МЕТОДЕ ПО ЛУЧУ

si

si+1

si+n

sj

1. Если сгенерировано состояние, для которого Fi = 1, то оно записывается в

память М = {si, si+1, …, si+n, … }

2. Если сгенерировано терминальное состояние sj, то возврат осуществляется в начало цепочки, в состояние si

3. Если сгенерировано состояние, для ко-

торого Fi > 1, то определяется новое начало цепочки М, состояние si+p

– – состояния, для которых Fi > 1

– состояния, для которых Fi = 1

– состояния, для которых Fi =

si

si+1

si+n

si+p

Рис. 2.5. Общая схема обхода терминальных вершин методом по лучу

Взависимости от соотношения количества терминальных состояний

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

памяти состояний, для которых выполняется условие Fi >1.

В некоторых практических задачах допускается хранение в памяти до трех и более последовательных состояний, для которых выполняется условие Fi >1. В этом случае цепочка памяти может иметь следующий

вид: М = {si, si+1, si+2, …, si+n, si+p, …, si+r, …}. Мощность цепочки М может быть скорректирована за счет анализа Fi состояний, записанных в память,

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

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

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

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

Если цепочка памяти содержит множество родительских состояний, для

которого выполняется Fi > 1 вида М = {si, si+1, si+2, …, si+n, si+p, …, si+r, …}, на некоторой итерации поиска может быть повторно сгенерировано одно из

родительских состояний (si+p) или одно из его дочерних состояний. В том и другом случае возврат следует осуществить в одно из родительских состояний цепочки М.

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

служить сравнение мощностей ( Fi > 1) родительских состояний, между которыми возникло кольцо, а также мощность образованного кольца относительно мощности цепочки М.

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

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

1.Если для очередного сгенерированного состояния выполняется ус-

ловие si sjt St, то задача решена (выполняется одно из условий решения первой задачи), иначе – переход к п. 2.

2.Если для состояния si формируется множество применимых операторов Fi, то переходим к п. 3.

3.Если Fi = (si – терминальное состояние), то следует вернуться

всостояние (предварительно записанное в память М), для которого выпол-

няется F > 1, и в дальнейшем предусмотреть вариант действий не ведущий к генерации терминального состояния, иначе – п. 4.

4.Если Fi = 1, то переходим к п. 5, иначе – F >1 и переходим к п. 7.

5.Если состояние si имеется в памяти М, то следует вернуться в со-

стояние, записанное в М, для которого выполняется F > 1, и в дальней-

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

шем использовать иной fj Fi, не ведущий к образованию кольца, иначе – переход к п. 6.

6.Состояние si записывается в память М, далее – переход к п. 8.

7.Из М удаляется родительское состояние (для которого F > 1) и все его дочерние (для которых F = 1), а на их место записывается состояние si.

8.Состояние si раскрывается: si fj = si+1, переход к п. 1.

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

Другой способ управления цепочкой памяти подразумевает смену генерации. Для поиска в глубину в память заносится фронт, для которого выполняется Sj >1 нетерминальных состояний или Si = 1 при дополнительном условии, что для si выполняется условие Fi > 1, и последующие фронты, для которых выполняются условия Si = 1, и для si Si выполня-

ется Fi = 1. Возврат осуществляется аналогично поиску по лучу, в начало цепочки (рис. 2.6).

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

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

вметоде Монте-Карло.

В[2] анализируются n-направленные технологии слепого поиска,

т. е. при условии So 1. Предполагается, что если пространство поиска разделить на n-равные подпространства (т. е. So = n), то количество итераций поиска убывает в степени n. Там же отмечается, что увеличить вероятность быстрого достижения цели в условиях n-направленного поиска можно, если использовать генерацию с более широким фронтом.

44		Глава 2. Методы поиска
СХЕМА ОБХОДА ТЕРМИНАЛЬНЫХ ВЕРШИН В МЕТОДЕ В ГЛУБИНУ
	sj	Sj
	Si
si	sj+1	sj+n
si+1
		Если сгенерировано терминальное со-
		стояние, то возврат осуществляется в на-
		чало цепочки, в состояние si Si
si+n		М = (Sj{sj} Si{si, si+1, si+2, …, si+n, …})
	– состояние, для которого Fi >1
sj	– состояния, для которых Fi =1
	– состояния, для которых Fi =
Рис. 2.6. Схема обхода терминальных вершин в методе в глубину

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

Выбор той или иной процедуры генерации зависит:

1) от условия решения задачи: найти все si St, найти одну si St, найти заданноеколичество si St, найти одну или несколько указанных si St;

2) от отношения S и подмножества St , от отношения S и под-

множества So , от отношения подмножества So и подмножества St ; 3) от мощности терминальных вершин и цикличности графа Ср.

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

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

Напомним, что:

1) для генерации по лучу si fj= si+1, фронт Si+1 =1, всегда выполняется переход только в одно состояние;

2) длягенерации в глубину si Fi = Si+1, фронт Si+1 1 зависит от Fi . 3) для генерации в ширину Si Fi = Si+1, фронт Si+1 1 зависит от

(Si Fi) .

Очевидно, что наряду с отмеченными способами генерации, существует способ генерации, особенность которого в применении одного fj Fi ко всем состояниям текущего фронта Si, т. е.

Si fj = Si+1.

Такой способ генерации назовем параллельным. Параллельный способ генерации состояний можно рассматривать как имитацию n-направленного поиска методом получу. И все же параллельный способ генерации имеет свои отличительные математические особенности. Поэтому его следует считать полноправнымпредставителем слепых методовпоиска.

Схема поиска параллельным методом представлена на рис. 2.7.

	siо		СХЕМА ПОИСКА ПАРАЛЛЕЛЬНЫМ МЕТОДОМ
Начальное			Первый
состояние			фронт Si
				Процедура генерации
siо Sо
s1	s2		sn	Si fi = Si+1
Текущие
фронты
Si, Si+1				Процедура проверки
				si+1 Si+1, sjt St
Целевое
		Si+1
состояние

sjt St

sjt

Рис. 2.7. Схема поиска параллельным методом

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

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

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

ров Fi.

2.Если Fi , то выбирается один fj Fi, иначе – Si состоит из тер-

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

Выбор оператора в параллельном методе предполагает три варианта событий, связанных с тем, что для каждого si существует собственное множество операторов Fi:

а) выбрать один fj , применимый для всех si Si. В этом случае необходимо предварительно выделить подмножество операторов Fi*, которое бы содержало оператор, применимый для всех si Si, т. е. объединение из всех Fi для фронта Si;

б) выбрать один fj, применимый и оригинальный для каждого si Si. В этом случае наоборот необходимо предварительно выделить подмножества оригинальных операторов для каждого состояния si относительно всех иных состояний Si;

в) выбрать один fj Fi, применимый для si Si. В этом случае нет необходимости в предварительных действиях.

3.Фронт Si раскрывается: Si fi = Si+1.

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

применимый для очередного фронта состояний Si+1.

Если принять условия, что слепой поиск осуществляется на дереве оригинальных состояний глубиной n и количество дочерних состояний m

(или Si|) у всякого родителя одинаково, то вероятность Р нахождения одного состояния на итерации b (n b) поиска будет представлена следующими выражениями:

1)для поиска по лучу

Р= 1 ( min) – b;

2)для поиска в глубину

Р= 1 ( min) – bm;

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

3) для поиска в ширину

Р = 1 ( mi)n-b.

Вероятность нахождения одного состояния на графе с некоторым Ср на итерации b поиска будет:

1)для поиска в глубину

Р= bСр ( min) – bm;

2)для поиска в ширину

Р = Срb ( mi)n-b.

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

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

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

Одним из способов управления является определение граничной глубины (ограничение числа итераций) [2, 3]. Другой способ – это управление направлением генерации это исключение повторов. Информация, позволяющая управлять генерацией, формируется в результате проведения процедуры проверки.

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

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

Предлагается определить количество вершин во фронте на первой, второй, i-й итерациях поиска.

Генерация осуществляется:

1)на неориентированном кольце, образованном оригинальными состояниями;

2)на «дереве» оригинальных состояний (у всякого «родителя» в ко-

тором по m – «дочек», где m 1);

3) на графе, организация которого соответствует задаче «Перестановка», представленной в прил. Б, при заданном количестве элементов в состояниях равном n, где n 2.

Решение задачи заключается в заполнении ячеек табл. 2.1 для каждого способа генерации.

										Таблица 2.1
Номер				Способ генерации
итерации		(по лучу / в глубину / в ширину / параллельным методом)
		кольцо				дерево				граф
1	1
2	1
3	1
…	1
i	1

Втабл. 2.1 в качестве примера представлено решение задачи для генерации по лучу. В столбце «кольцо» определено количество элементов во фронте на первой, второй, третьей, i-й итерациях поиска. Анализ мощности фронтов позволит определить эффективность слепых методов поиска для задачи выделения организации состояний.

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

изадач для слепых методов.

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

Возможные варианты генерации:

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

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

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

Наличие терминальных состояний является следствием недостаточно хорошего планирования.

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

Неуправляемый поиск востребован всякий раз, когда существенные изменения в объекте происходят быстрей, чем это может зафиксировать ПС.

Вследующем параграфе будут рассмотрены особенности управления процедурой генерации на основе апостериорной информации.

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

§ 2.3. Процедура проверки

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

Наиболее яркими представителями простейших эвристических методов поиска являются:

1)метод кратчайших путей Мура (в действительности определяет минимальноерасстояние, количествоитерацийпоискадоближайшегосостояния);

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

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

снаиболее широким фронтом.

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

Рассмотрим алгоритм поиска методом Мура с генерацией в ширину:

1.Определить для siо So множество применимых операторов Fi .

2.Раскрыть начальное состояние, используя генерацию в глубину

siо Fi = S1 для всех последующих итераций поиска используется генерация в ширину Si-12 Fj = Si.