Главная > Интеллектуальные системы > Искусственный интеллект (Э. Хант)
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.3. Фортранная дедуктивная система — автоматическое порождение таблиц связей

11.3.0. Исторические сведения и общий подход

Эффективность программы GPS для конкретной задачи зависит во многом от выбранного определения различий в таблице операторов и различий. Некоторые исследователи занимались задачей автоматического порождения этой таблицы. В частности, Куинлан (Куинлан и Хант, 1968,1969; Куинлан, 1969) создал фортранную дедуктивную систему — программу, сходную с GPS во всем, за исключением того, что таблица операторов и различий здесь выводится из описания операторов.

Хотя можно показать, что представление объектов в FDS соответствует деревьям в GPS, все же при работе с этой программой легче пользоваться лингвистической терминологией. Состояния объектов представляются как цепочки из алфавита терминальных и нетерминальных символов. Нетерминальными являются переменные символы, обозначаемые здесь буквами из конца алфавита, например . К терминальным символам относятся конечное множество констант, знаков унарных и бинарных операций; они определяются заново для каждой задачи. То что в терминах GPS было бы объектом, в терминах FDS есть правильно построенное выражение (п. п. в.). Оно определяется правилами:

(1) Константа или переменная есть п. п. в.

(2) Бинарная операция с двумя п. п. в. после нее есть п. п. в.

(3) Унарная операция с одним п. п. в. после нее есть п. п. в.

Эти правила определяют префиксную, или „обратную бесскобочную" запись. Они также устанавливают соотношение между деревьями в GPS и цепочками в Рассмотрим задачу интегрирования, представленную выше. Можно определить множество Т первичных символов следующим образом:

Выражение

теперь принимает форму

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

Рис. 11.7. Дерево для

Правило подстановки содержится в FDS, как и в программе GPS. Оно позволяет работать с цепочками типа

как с частным случаем цепочки

Эти операторы FDS именуются правилами переписывания цепочек, так как они указывают, что одну цепочку можно заменить другой. Например,

можно применить к чтобы получить или или Как видно из примера (11), правила переписывания имеют форму где - п. п. в. Правило переписывания цепочки

требует двух преобразований в Это

поскольку отношение равенства не обязательно рефлексивно.

С помощью (13) можно также проиллюстрировать, как определяются различия при построении таблицы операторов и различий. Рассмотрим (13а). И правая, и левая части представляют собой п. п. в., а, следовательно, деревья, как показано на рис. 11.7.

Список различий между левой и правой частями этих деревьев таков:

Различия (1) и (2) являются абсолютными различиями, поскольку эти изменения останутся в силе, где бы ни применялось данное правило. Характер же изменения, обусловленного различием (3), нельзя точно определить, пока мы не знаем, к каким структурам нужно применить правило переписывания. Например, если бы это правило нужно было применить к цепочке

то константы В и С поменялись бы местами, а если это же правило используется для получения

то константа В будет заменена бинарной операцией + и соответствующими ей операндами. Это примеры контекстно-зависимых изменений. Когда операторы определены, программа FDS исследует каждый из них, чтобы определить, какие абсолютные и контекстнозависимые изменения он может вызвать. Подробности того, как это делается, сейчас несущественны. (Детальное обсуждение содержится в статье Куинлана и Ханта, 1968.) Дело в том, Что такое задание операторов определяет матрицу операторов и различий, которую программа способна вывести.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление