2. Опишите стратегию “подъема на гору”.

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

Проиллюстрируем работу системы управления в соответствии со стратегией «подъеме на гору» на примере игры в 8.

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

Н апример, значение этой функции для исходного состояния на рис. 1.8. равно – 4, а значение ее для нулевого состояния 0. Нетрудно вычислимо значение этой функции для описания любого состояния.

Рис. 1.8. Последовательность состояний, через которые проходит система продукций

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

Билет №15

1.Опишите структуру ядра продукционного правила.

Основным элементом продукции является ее ядро: А В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака секвенции . Обычное прочтение ядра продукции выглядит так: ЕСЛИ А, ТО В, более сложные конструкции ядра допускают в правой ча­сти альтернативный выбор, например, ЕСЛИ А, ТО В, ИНАЧЕ В₂. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В ничего сказать нельзя). Возможны и другие интерпретации ядра продук­ции, например А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.

Термин «продукция» принадлежит американскому логику Э.Посту [Post, 1943]. В понимании Поста в качестве продукции выступала только та ее часть, которую называют теперь ядром. Запись «ЕСЛИ А, ТО В» трактовалась, как оператор замены цепочки А цепочкой В в некотором слове, т.е. продукции были тем, что позже стали называть подстановками и использовать при описании различных уточнений понятия алгоритма.

"Если-то"-правила обычно оказываются весьма естественным выразительным средством представления знаний. Кроме того, они обладают следующими привлекательными свойствами:

· модульность: каждое правило описывает небольшой, относительно независимый фрагмент знаний;

· возможность инкрементного наращивания: добавление новых правил в БЗ происходит относительно независимо от других правил;

· удобство модификации (как следствие модульности): старые правила можно изменять на новые относительно независимо от других правил;

· применение правил способствует прозрачности системы.