ТИПИС

	§ 1.2. Задачи поиска и преследования цели	21

теллектуальней. В этом случае также можно будет говорить об эффективном управлении методами поиска в n-направленных режимах.

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

Организация пространства поиска существенно влияет на эффективность поиска. Обычно организация процедур, заложенная в методы поиска, описанные в [1–5, 7, 8], не связана и не учитывает организацию пространства поиска. Поэтому методы поиска в [1–5, 7, 8], применяемые на кольце, дереве, графе, в той или иной нетипичной организации пространства поиска, имеют относительные вычислительные достоинства и недостатки. Метод поиска, проявляющий достоинства на дереве проявит те же качества и на более сложной «деревянной» организации пространства, так как фундаментальные принципы организации пространства сохраняются. Иначе, придется обосновать необходимость планирования отдельного вида поиска под частную задачу и организацию пространства поиска (обычно, для цели (задачи), которая обязательно должна изменяться в течение небольшого числа итерации поиска).

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

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

22		Глава 1. Поиск, задачи поиска и пространство состояний

Взаключении параграфа выделим основные задачи поиска:

поиск целевого состояния или состояний;

определение расстояния и выделение оптимального пути до целевого состояния или состояний;

формирование модели распределения и мониторинг целевых состояний.

Задачи, стоящие перед разработчиками методов поиска:

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

разработка встроенного в базовый состав процедур поиска алгоритма, позволяющего корректировать априорную систему оценок;

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

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

стояние, пространство состояний и пространство поиска, а также про-

анализированы свойства типичных организаций состояний пространства поиска.

	§ 1.3. Пространство состояний	23

§ 1.3. Пространство состояний

Процесс решения задачи в дискретном пространстве может быть представлен как последовательный переход из одной дискретной точки пространства (состояния) в другую. Множество всех дискретных состояний образует дискретное пространство состояний (далее просто пространство состояний): S = {s1, s2, …, sm}, где m количество всех состояний множества S. Всякое состояние si S характеризуется множеством признаков K = {k1, k2, …, kn}. Среди множества признаков состояний следует выделить:

1) подмножество родовых признаков состояний KR K, характеризующее всякое состояние пространства состояний. Подмножество родовых признаков формируется путем выделения тождественных признаков, представляющих состояния. Родовые признаки, по сути, выделяют подмноже-

ство состояний из множества состояний, т. е. выполняется условие KR . Состояния, принадлежащие подмножеству, составляют уникальное дочернее подпространство состояний;

2) подмножество видовых признаков состояний KV K выделяет всякое состояние пространства состояний. Для всякого состояния пространства состояний выполняются следующие условия: KV и KV уникально; иначе, будет иметь место такой случай: si sj одно состояние.

В качестве примера рассмотрим следующие состояния: s1(ki, kj, ka, kb), s2(ki, kj, ka, kс), s3(ki, kj, kc, kb) и s4(kd, kf, kg). Отметим, что состояния s1, s2 и s3

24		Глава 1. Поиск, задачи поиска и пространство состояний

в отличие от состояния s4 обладают общими признаками ki и kj. Признаки ki и kj образуют множество KR, следовательно, состояния s1, s2 и s3 составляют пространство состояний. Признаки ka, kb являются видовыми для состоя-

ния s1, ka, kc для состояния s2 и kc, kb для состояния s3, т. е. составляют множества KV данных состояний.

Кроме иерархического отношения «род – вид» пространство состояний можно охарактеризовать отношением «часть – целое»:

N

S = Si,

i 1

где Si подмножества множества S.

Причем должно быть выполнено условие

N Si .

i 1

Отношение «часть – целое» обуславливает то, что пространство состояний включает в свой состав:

1) подмножество So начальных состояний. Это подмножество состояний, из которых осуществляется начало поиска. Для данного подмножества выполняется условие So . Начальные состояния характеризуют актуальное состояние системы;

2) подмножество St целевых состояний. Это подмножество состояний представляет собой множество решений задачи или цель поиска. Для дан-

ного подмножества выполняется условие St ;

3) подмножество Sс текущих состояний. Для данного подмножества обычно выполняется условие Sс (в некоторых случаях Sс формируется за счет состояний множеств So и St).

При выполнении условий Sс = , пунктов 1 и 2 и условия soi fg = stj, где fg оператор преобразования soi So в состояние stj St, достижение целевого состояния выполняется в одно действие. В этом случае, как уже отмечалось, задача является элементарной, и поиска как такового не выполняется. В данном контексте простой задачей будем считать случай, когда ПС известна цепочка операторов Li = (f1, f2, …, fn), применение которой к состоянию soi позволяет перейти в состояние stj St. Причем Li 1 и соответственно Sс .

Важным понятием, используемым при решении задач в пространстве состояний, является понятие пространство поиска – SR. Необходимость

§ 1.3. Пространство состояний	25

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

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

Для любой пары состояний (si, sj) SR всегда найдется одна и более цепочек операторов Li = (f1, f2, …, fn), применение которой к состоянию si приведет к состоянию sj. Причем все текущие состояния, представляющие некоторый путь от состояния si до состояния sj, также будут принадлежать данному пространству SR. Следовательно, множество SR – это всегда связная область.

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

В качестве примера рассмотрим состояния: s1(ki, kj, ka, kb), s2(ki, kj, ka, kс) и s3(ki, kj, kc, kb), образующие пространство состояний на основе общих признаков ki и kj. Анализируя состав видовых признаков состояний, можно отметить, что состояния s1 и s2 имеют общий признак ka, состояния s2 и s3 – признак kc и s1, s3 – признак kb, позволяющие организовать собственные пространства поиска или подклассы состояний SR.

Организацию пространства состояний удобно представить в виде ориентированного графа (в дальнейшем орграфа): G=(X{xi},Y{yj}), где множество вершин орграфа X{xi} сопоставимо с состояниями si S, а множество дуг Y{yj} графа G сопоставимы с операторами fg F, преобразующими состояния множества S.

Представление пространства состояний в виде орграфа позволяет выделить дополнительные свойства и особенность организации состояний

[12–14]. Свойства xi X определяются отношением подмножеств входящих Yin{yj} и выходящих дуг Yout{yj}.

Рассмотрим наиболее показательные условия соотношений множеств Yin{yj} и Yout{yj}, устанавливающие организацию орграфа G.

1. Если для всякой вершины xi X орграфа G выполняются условияYin{yj} = 1 и Yout{yj} = 1, то орграф представляет собой структуру в виде

26		Глава 1. Поиск, задачи поиска и пространство состояний

кольца. Данные условия обуславливают смежность и связность всех вершин орграфа.

2. Если для всякой вершины xi X орграфа G выполняются условияYin{yj} = и Yout{yj} = , то такой граф является несвязанным. Если данные условия выполняются только для некоторых вершин, то орграф является частично связанным.

3.Если для всякой вершины xi X орграфа G выполняются условияYin{yj} =1 и Yout{yj} 1, то орграф представляет собой структуру в виде множества ветвей, расходящихся от корня дерева.

4.Если для всякой вершины xi X орграфа G выполняются условияYin{yj} 1 и Yout{yj} = 1, то орграф представляет собой структуру в виде ветвей, сходящихся к корню дерева.

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

Свойства некоторых вершин также влияют на особенность организации орграфа.

1.Если для некоторой вершины xi X орграфа G выполняются условия Yin{yj} 1 и Yout{yj} = , то такая вершина xi является терминаль-

ной. Терминальная вершина указывает на то, что для соответствующего состояния si множество применимых к нему операторов F = . Такое состояние не может быть далее преобразовано.

2. Если для некоторой вершины xi X орграфа G выполняются условия Yin{yj} = и Yout{yj} 1, то такая вершина xi является корневой. Корневая вершина не может быть порождена ни одной вершиной орграфа G. Так, если корень дерева не представляет собой кольцо, то в дереве есть только одна корневая вершина.

Дополнительно организацию состояний можно отобразить с помощью матриц смежности и инцидентности [12–14]. Матрица смежности позволяет представить бинарные отношения между вершинами орграфа:

[сij] xi, xi+1 = [n · n],

где сij – отношения смежности, которые выражают наличие дуг yj между вершинами орграфа G; n – количество строк и столбцов матрицы смежности (соответствует количеству xi G).

Отношение смежности сij обозначается «1», если между вершинами xi и xi+1 существует дуга yj, иначе – «0».

§ 1.3. Пространство состояний	27

Матрица инцидентности позволяет представить отношения между количеством входящих и выходящих дуг некоторой вершины xi G:

[aij] xi, yj = [n · m],

где aij – отношение инцидентности дуги yj к вершине xi орграфа G; n – количество строк вершин орграфа; m – количество столбцов дуг орграфа.

Отношение aij обозначается «1», если дуга yj выходит из вершины xi, иначе – «0» (если дуга yj входит в вершину xi).

x1	y1
y5
x5	x2					[aij] xi, yj =
y4		y2
x4	x3			x1	x2	x3	x4	x5
y3
			x1	0	1	0	0	1
	[cij] xi, xi+1	=	x2	1	0	1	0	0
			x3	0	1	0	1	0
			x4	0	0	1	0	1
			x5	1	0	0	1	0
						а

	x1	x2	x3	x4	x5
y1	1	0
y2		1	0
y3			1	0
y4				1	0
y5	0				1
			б

Рис. 1.6. Орграф «кольцо»: а – матрица смежности, б – матрица инцидентности

28		Глава 1. Поиск, задачи поиска и пространство состояний

		x1									x1	x2	x3	x4	x5	x6	x7
	y1		y2							x1	0	1	1	0	0	0	0
	x2		x3							x2	1	0	0	1	1	0	0
										x3	1	0	0	0	0	1	1
	y3				y6			[cij] xi, xi+1
		y4	y5							=	0	1	0	0	0	0	0
										x4
x4	x5		x6		x7					x5	0	1	0	0	0	0	0
										x6	0	0	1	0	0	0	0
			x1	x2	x3	x4	x5	x6	x7	x7	0	0	1	0	0	0	0
		y1	1	0
		y2	1		0									б
[aij] xi, yj =		y3		1		0
		y4		1			0
		y5			1			0
		y6			1				0

а

Рис. 1.7. Орграф «дерево»: а – матрица смежности, б – матрица инцидентности

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

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

§ 1.3. Пространство состояний	29

	x1		y1
y3		y2	y5
	y7	x3
			y6
x5

[cij] xi, xi+1 =

								x1	x2	x3	x4	x5
	x2						y1	1	0
							y2	1		0
y4					[aij] xi, yj =		y3	1				0
							y4		1		0
x4							y5		1	0
							y6				1	0
	x1	x2	x3	x4	x5		y7			0		1
									Позб. 2
x1	0	1	1	0	1
x2	1	0	1	1	0
x3	1	1	0	0	1
x4	0	1	0	0	1	Поз. 1
x5	1	0	1	1	0
		а

Рис. 1.8. Произвольный орграф: а – матрица смежности,

б– матрица инцидентности

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

Всякое состояние характеризуется множеством родовых и видовых признаков.

Родовые признаки, по сути, выделяют пространство состояний из множества состояний.

Подмножество видовых признаков состояний выделяет всякое состояние пространства состояний.

Пространство состояний включает в свой состав:

1)подмножество So начальных состояний;

30		Глава 1. Поиск, задачи поиска и пространство состояний

2)подмножество St целевых состояний;

3)подмножество Sс текущих состояний.

В отличие от пространства состояний, пространство поиска – это всегда связная область.

Представление пространства состояний в виде орграфа G = (X{xi}, Y{yj}) позволяет выделить дополнительные свойства и организацию состояний:

1)если Yin{yj} = 1 и Yout{yj} = 1, то орграф представляет собой

кольцо;

2)если Yin{yj} = и Yout{yj} = , то граф является несвязным;

3)если Yin{yj} = 1 и Yout{yj} 1, то орграф представляет собой

расходящееся от корня дерево;

4)если Yin{yj} 1 и Yout{yj} = 1, то орграф представляет собой сходящееся к корню дерево;

5)если Yin{yj} 1 и Yout{yj} = , товершинаявляетсятерминальной;

6)если Yin{yj} = и Yout{yj} 1, то вершина является корневой.

Матрица смежности позволяет представить бинарные отношения между вершинами орграфа.

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

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