Geum.ru

Опорный конспект лекции фсо пгу 18. 2/07 Министерство образования и науки Республики Казахстан

Вид материалаКонспект

Содержание


Стратегии поиска решений для систем продукций
Подобный материал:
1   2   3   4   5   6   7   8   9

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

 

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

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


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

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

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

а) затраты на применение правил (стоимость пути к цели);

б) затраты на управление (стоимость поиска правил, ведущих к цели).



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

распределение расходов. Эти тенденции отражены на рис 4.2.

 

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

Обратные и двусторонние системы продукций. Система продукций для решения игры в 8, при всех рассмотренных режимах управления, работает непосредственно от исходного состояния к целевому (т.е. в прямом направлении) и ее можно назвать прямой системой продукций.

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

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

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

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