Глава 3

Системы продукций и стратегии поиска в пространстве состояний

1. Системы продукций

1. Компоненты системы продукций

Система продукций (или продукционная система) состоит из трех основных элементов:

• рабочей памяти;

• множества продукционных правил;

• системы управления.

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

Продукционное правило представляет собой пару «условие—действие». Если условие выполняется, т.е. описание текущего состояния рабочей памяти удовлетворяет этому правилу, то правило может быть применено. Примене­ние этого правила изменяет содержимое рабочей памяти.

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

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

2. Основной алгоритм системы продукций

Обозначим текущее состояние рабочей памяти системы продукций через CurrentState.

Следующий алгоритм описывает взаимодействие трех компонентов про­дукционной системы.

function MainAlgorithm; begin

CurrentState := Start ’исходное состояние рабочей памяти until CurrentState = goal do

’пока не достигнуто целевое состояние

begin

а) выбрать некоторое правило P в множестве правил, которые применимы в состоянии CurrentState;

б) CurrentState := P(CurrentState)

’результат применения правила P к CurrentState;

end;

end.

Пример 1. Рассмотрим простой пример работы системы продукций, ко­торая преобразовывает строку, состоящую из символов a,b,c в соответ­ствии со следующими правилами:

1. ab ^ ba

2. ac ^ ca

3. bc ^ cb

Работа такой системы продукций для начального состояния рабочей памяти acabc приведена в табл. 2.

Таблица 2

Шаг	Состояние рабочей памяти	Множество применимых правил	Примененное правило
0	acabc	1,2,3	1
1	acbac	2	2
2	cabac	1,2	1
3	cbaac	2	2
4	cbaca	2	2
5	cbcaa	3	3
6	ccbac	0	stop

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

Так, в примере 1 множество применимых правил на некоторых шагах состоит более чем из одного правила. Множество всех применимых в данном состоянии правил называется конфликтным множеством.

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

В примере 1 применялась стратегия управления, состоящая в выборе из конфликтного множества правила с наименьшим порядковым номером (дру­гими словами, использовалось первое же применимое правило).

3. Проблема представления

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

Приведем пример представления задачи. Рассмотрим задачу о коммиво­яжере. Торговец должен побывать в каждом из пяти городов, обозначенных на карте. Каждая пара городов соединена дорогой с указанием ее длины. Задача состоит в том, чтобы, начиная, например, с города A, найти мини­мальный путь, проходящий через все остальные города только один раз и приводящий обратно в A.

Чтобы поставить эту задачу, определим следующее.

Рабочая память будет содержать список городов, посещенных к данно­му моменту. Таким образом, исходное состояние рабочей памяти является списком [А]. Не допускается появление списков, содержащих название лю­бого города более одного раза, кроме случая, когда после внесения в список названий всех городов А упоминается в нем вторично.

Правила продукций соответствуют решениям:

• идти в город A;

• идти в город B;

• идти в город C;

• идти в город D;

• идти в город E.

Правило не применимо к описанию состояния рабочей памяти, если оно не преобразует ее в какое-либо допустимое состояние. Следовательно, прави­ло, соответствующее тому, чтобы «идти в город А», не применимо к любому списку, в который еще не внесены все города.

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

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

4. Обратные и двусторонние системы продукций

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

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

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

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

Для этого следует включить в рабочую память описания как состояний, так и целей. К части описания состояний применяются П-правила, а к части описания целей — О-правила. При поиске такого типа целевое условие для управляющей системы, которое позволяет сделать вывод о том, что задача решена, должно быть определено как разновидность условия соответствия между частью описания состояний и частью описания цели в рабочей па­мяти. Управляющая система должна также на каждой стадии принимать решения об использовании применимого П- либо О-правила.