Примеры выполнения заданий

Пример 1. Рассмотрим простой пример работы ПС, которая сортирует строку, состоящую из символов a, b и c. В этом примере продукция является допустимой, если ее условие соответствует части строки в рабочей памяти. При выполнении правила подстрока, которая соответствовала его условию, заменяется строкой из правой части правила. В таблице представлено решение этой задачи.

Набор продукций:

 

1. ba → ab

2. ca → ac

3. cb → bc

Итерация	Рабочая память	Конфликтное множество	Применение правила
	cbaca	1, 2, 3
	cabca
	acbca	2, 3
	acbac	1, 3
	acabc
	aacbc
	aabcc	Ø	останов

 

 

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

 

move (1, 8) move (6, 1)

move (1, 6) move (6, 7)

move (2, 9) move (7, 2)

move (2, 7) move (7, 6)

move (3, 4) move (8, 3)

move (3, 8) move (8, 1)

move (4, 9) move (9, 2)

move (4, 3) move (9, 4)

Рис. 2. Шахматная доска 3×3 для задачи хода конем

с допустимыми ходами

 

Записанные на рис.5.2 предикаты move (x, y) составляют базу знаний (базу фактов) для задачи хода конем. Продукционные правила – это факты перемещений move, первый параметр которых определяет условие, а второй параметр определяет действие (сделать ход в поле, в которое конь может перейти). Продукционное множество правил для такой задачи приведено ниже.

P1: If (конь в поле 1) then (ход конем в поле 8)

P2: If (конь в поле 1) then (ход конем в поле 6)
P3: If (конь в поле 2) then (ход конем в поле 9)

P4: If (конь в поле 2) then (ход конем в поле 7)

P5: If (конь в поле 3) then (ход конем в поле 4)

P6: If (конь в поле 3) then (ход конем в поле 8)

P7: If (конь в поле 4) then (ход конем в поле 9)

P8: If (конь в поле 4) then (ход конем в поле 3)

P9: If (конь в поле 6) then (ход конем в поле 1)

P10: If (конь в поле 6) then (ход конем в поле 7)

P11: If (конь в поле 7) then (ход конем в поле 2)

P12: If (конь в поле 7) then (ход конем в поле 6)

P13: If (конь в поле 8) then (ход конем в поле 3)

P14: If (конь в поле 8) then (ход конем в поле 1)

P15: If (конь в поле 9) then (ход конем в поле 2)

P16: If (конь в поле 9) then (ход конем в поле 4)

Допустим, необходимо из исходного состояния (поле1) перейти в целевое состояние (поле 2). Итерации ПС для этого случая игры показаны в табл. 2.

Таблица 2

 

№ итерации	Текущее поле	Целевое поле	Конфликтное множество	Активизация правила
			1, 2
			13, 14
			5, 6
			7, 8
			15, 16
				останов

 

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

 

Задание 5

Построить продукционную систему, которая сортирует строку, состоящую из символов a, b, c, d, e, f, g, h. В этом случае продукция является допустимой, если ее условие соответствует части строки в рабочей памяти. При выполнении правила подстрока, которая соответствовала его условию, заменяется строкой из правой части правила.

 

№ варианта	Строка символов	№ варианта	Строка символов
	fgaabchedfdc		gfcegaabcdfec
	bcfacegacgbcbd		egabcfacegbcbfd
	afbcegacabdfec		cbchafgcbhecab
	fcbegabcfgbcbac		hcabfgchdfdc
	dcebcbadgeacbdf		cacgfbbaedcch
	cegaabcbdfec		efacfaccgbcbcd
	cdcchcacgfbba		adgbdcebcbdfeac
	bfacbegababced		bfacegaadcbc
	ecgdabcfacegb		achfddebchdfdc
	befhacddebchfdc		bchfdaebchefdc

 

Задание 6

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

№ варианта	Исходное состояние	Целевое состояние	№ варианта	Исходное состояние	Целевое состояние