Лекция 13

6.4. Пример работы продукционной системы.

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

Достигается в пять ходов.

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

9! = 362880

181440 181440

Множество продукционных правил:

1. Если пустая клетка не находится в верхнем ряду, то можно передвинуть ее вверх (т.е.) Правило <1>

2. Если пустая клетка не находится в нижнем ряду, то можно передвинуть ее вниз (т.е.) Правило <2>

3. Если пустая клетка не находится в левом ряду, то можно передвинуть ее влево (т.е.) Правило <3>

4. Если пустая клетка не находится в правом ряду, то можно передвинуть ее вправо (т.е.) Правило <4>

Различные виды стратегий:

1. Безвозвратная стратегия. Для реализации этой стратегии используется градиентный метод поиска максимума функции.

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

У Находим экстремум

х₁ Х

Рис.55. Градиентный метод поиска экстремума функции

Требования к функции:

- непрерывность

- гладкость

- одноэкстремальность

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

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

Значение функции Значение функции Значение функции

Схема 3. Безвозвратная стратегия

Возвратные стратегии.

1) Стратегия с возвращением

Правила остаются прежними, но рассматриваются в другом порядке:

1. Если пустая клетка не находится в левом ряду, то можно передвинуть ее влево (т.е.) Правило <3>

2. Если пустая клетка не находится в верхнем ряду, то можно передвинуть ее вверх (т.е.) Правило <1>

3. Если пустая клетка не находится в правом ряду, то можно передвинуть ее вправо (т.е.) Правило <4>

4. Если пустая клетка не находится в нижнем ряду, то можно передвинуть ее вниз (т.е.) Правило <2>

Условия возвращения:

1. Порождается описание, которое уже встречалось.

2. Было сделано некоторое произвольно выбранное число шагов (6), но целевое описание не построено.

3. Не существует применяемых правил.

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

И так далее…

Схема 4. Возвратная стратегия

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

2) Стратегия управления с поиском на графе

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

1

2 2

3 3 3 3 3 3 3

Рис.56. Дерево решений

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

Дата добавления: 2015-06-27