Часть 10.

<Представление ><решения ><задачи ><в ><виде ><пути ><от ><начального ><состояния ><к ><целевому.>

<Алгоритм ><поиска, ><систематически ><проверяющий ><наличие ><альтернативных ><путей ><к ><цели.>

><<Поиск ><с ><возвратами ><или ><другой ><механизм, ><позволяющий ><выходить ><из ><тупиковых

><состояний ><и ><находить ><путь ><к ><цели.>

<Списки, ><содержащие ><точную ><информацию ><о ><рассматриваемых ><в ><данный ><момент

><состояниях, ><в ><том ><числе:>

<а)>< ><список ><позволяющий ><алгоритму ><в ><случае ><необходимости ><исследовать ><ра

><нее ><не ><рассмотренные ><состояния;>

<б)>< ><список ><содержащий ><рассмотренные ><состояния. ><Он ><позволяет ><алгоритму

><избегать ><зацикливаний ><и ><учитывать ><тупиковые ><пути.>

<5.>< ><Список ><можно ><рассматривать, ><как ><стек ><для ><поиска ><в ><глубину, ><очередь ><для

><поиска ><в ><ширину ><или ><приоритетную ><очередь ><для ><"жадного" ><алгоритма ><поиска.>

<В ><данной ><главе ><вводятся ><высокоуровневые ><методы ><для ><построения ><алгоритмов ><поиска. ><Первый ><из ><них ><- ><рекурсивный ><поиск, ><определяющий ><поиск ><в ><глубину ><с ><возвратами ><более ><кратким ><и ><естественным ><способом, ><чем ><в ><главе ><3. ><Этот ><механизм ><составляет ><основу ><многих ><алгоритмов ><в ><разделе ><5.1. ><Применение ><унификации ><в ><процессе ><поиска ><в ><пространстве ><состоя><ний ><расширяет ><возможности ><рекурсивного ><поиска. ><Этот ><алгоритм ><поиска ><по ><образцу ><(раздел ><5.2) ><положен ><в ><основу ><языка ><описанного ><в ><главе ><14, ><и ><многих ><экспертных ><систем, ><рассмотренных ><в ><главе ><7. ><Раздел ><5.3 ><посвящен ><так ><называемым ><продукционным ><сис><темам. ><Это ><общая ><архитектура ><для ><решения ><образно-ориентированных ><проблем, ><которая ><широко ><используется ><как ><для ><моделирования ><человеческого ><образа ><мышления ><при ><решении ><многих ><задач, ><так ><и ><для ><построения ><экспертных ><систем ><и ><других ><приложений ><ИИ. ><Наконец, ><в ><разделе ><5.4 ><рассматривается ><еще ><одно ><представление ><для ><решения ><задач ><искусственного ><ин><теллекта ><-- ><так ><называемая ><модель ><классной ><доски ><(blackboard).>

<5.1. ><Рекурсивный ><поиск>

<><5.1.1. ><Рекурсия>

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

<Рекурсивный ><шаг: ><вызов ><процедуры ><из ><этой ><же ><процедуры ><для ><повторения ><после

><довательности ><действий.>

<Условие, ><которое ><обеспечивает ><выход ><из ><процедуры ><и ><таким ><образом ><предотвра

><щает ><зацикливание ><(рекурсивная ><версия ><бесконечного ><цикла).>

<Оба ><этих ><компонента ><необходимы ><и ><появляются ><во ><всех ><рекурсивных ><определениях ><и ><алгоритмах. ><Рекурсия ><- ><естественный ><инструмент ><управления ><массивами ><данных, ><кото><рые ><имеют ><правильную ><структуру ><и ><неопределенный ><размер, ><например, ><списками, ><де><ревьями ><и ><графами. ><Рекурсия ><особенно ><удобна ><для ><поиска ><в ><пространстве ><состояний.>

<Простой ><пример ><- ><алгоритм ><определения ><принадлежности ><данного ><элемента ><списку. ><Списком ><(list) ><называют ><упорядоченную ><последовательность ><элементов ><и ><фундаменталь><ных ><строительных ><блоков ><структур ><данных. ><Списки ><использовались ><как ><альтернативная ><форма ><записи ><выражений ><исчисления ><предикатов ><(глава ><2) ><и ><для ><представления ><списков ><и ><в ><алгоритмах ><поиска ><из ><главы ><3. ><Процедура ><проверки ><принадлежности ><элемента ><списку ><определяется ><так.>

<><186>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><

<список ><пуст>

< ><%останов>

<= ><первому ><элементу ><списка>

< ><%останов>

< >< ><:= >< ><список ><после >< ><удаления >< ><первого >< ><элемента;

>< >< >< ><%рекурсия>

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

<В ><приведенном ><выше ><алгоритме ><используются ><две ><фундаментальные ><операции ><со ><списком: ><первая ><из ><них ><(head) ><возвращает ><первый ><элемент ><списка, ><вторая ><операция ><(fa/7) ><возвращает ><список, ><полученный ><после ><удаления ><первого ><элемента. ><Эти ><операции ><наряду ><с ><рекурсией ><составляют ><основу ><высокоуровневых ><операций ><со ><списком ><типа ><Данные ><операции ><поддерживаются ><языками ><обработки ><списков ><и ><и ><под><робно ><описаны ><в ><главах, ><посвященных ><каждому ><из ><этих ><языков.>

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

<5.1.2. ><Рекурсивный ><поиск>

<Прямое ><преобразование ><описанного ><в ><главе ><3 ><алгоритма ><поиска ><в ><глубину ><в ><рекур><сивную ><форму ><иллюстрирует ><эквивалентность ><рекурсии ><и ><итерационного ><подхода. ><Этот ><алгоритм ><для ><поддержки ><списка ><состояний ><использует ><глобальные ><переменные ><и >

< ><%переменные ><и >< ><глобальные>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><187>

><<список ><пуст>

<:= ><первый ><элемент ><списка ><равно ><целевому ><состоянию >

< >< ><:= >< >< ><хвост >< >< ><списка >< >< >

< >< ><:= >< ><с >< ><добавлением ><для >< ><каждого ><потомка >< ><не >< ><в >< ><списке ><или >

<%построение ><стека>

<добавить >< ><потомок ><в >< ><начало >< ><списка >< >

< ><%рекурсивный ><вызов>

<Поиск ><в ><ширину ><можно ><описать ><фактически ><тем ><же ><самым ><алгоритмом. ><При ><этом ><не><обходимо ><сохранять ><список ><как ><глобальную ><структуру ><данных ><и ><рассматривать ><список ><как ><очередь, ><а ><не ><как ><стек.>

<Из ><представленного ><алгоритма ><ясно, ><что ><поиск ><в ><глубину ><не ><использует ><все ><возмож><ности ><рекурсии. ><Процедуру ><можно ><упростить, ><используя ><рекурсию ><непосредственно ><(а ><не ><через ><список ><для ><рассмотрения ><состояний ><и ><нахождения ><путей ><в ><их ><простран><стве. ><В ><новой ><версии ><алгоритма ><глобальная ><переменная ><используется ><для ><обна><ружения ><повторяющихся ><состояний ><и ><предотвращения ><циклов. ><Список ><неявно ><ис><пользуется ><в ><записях ><активации ><рекурсивной ><среды.>

< >< ><(current_state)><;>

<%closed ><- ><глобальная >< ><переменная >

< >< ><равно ><целевому >< ><состоянию>

< >< >

<добавить >< >< >< >< ><в >< >< ><список >< >< >< ><имеет >< ><непроверенные ><потомки >

< >< ><:= >< >< ><следующий ><непроверенный ><потомок; >< ><потомок ><не >< ><член >< ><списка >< >

< >< >< >< ><= >< >

< >< >

< ><%поиск ><исчерпан>

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

<><188>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Рекурсия ><позволяет ><обойтись ><без ><списка ><Механизм, ><посредством ><которого ><мож><но ><реализовать ><рекурсию ><на ><каком-либо ><языке ><программирования, ><должен ><включать ><от><дельную ><запись ><активации ><(activation ><[Aho ><и ><1977] ><для ><каждого ><рекурсив><ного ><вызова. ><Каждая ><такая ><запись ><активации ><должна ><содержать ><локальные ><переменные ><и ><состояние ><выполнения ><для ><каждого ><вызова ><процедуры. ><При ><каждом ><рекурсивном ><вызове ><процедуры ><с ><новым ><состоянием ><новая ><запись ><активации ><сохраняет ><параметры ><процедуры ><(состояние), ><все ><локальные ><переменные ><и ><текущее ><состояние ><выполнения. ><В ><рекурсивном ><алгоритме ><поиска ><состояния, ><находящиеся ><на ><рассматриваемом ><пути, ><сохраняются ><в ><после><довательности ><записей ><активации ><рекурсивных ><вызовов. ><Запись ><каждого ><вызова ><содержит ><также ><последнюю ><операцию, ><которая ><была ><сделана ><при ><генерации ><соответствующего ><по><томка. ><Это ><позволяет ><генерировать ><при ><необходимости ><брата ><данного ><потомка.>

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

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

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

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

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><189>

><<5.2. ><Поиск ><по ><образцу>

<><В ><разделе ><5.2 ><рекурсивный ><поиск ><будет ><применен ><к ><пространству ><логического ><выво><да. ><В ><результате ><получим ><общую ><процедуру ><поиска ><для ><исчисления ><предикатов.>

<Допустим, ><необходимо ><построить ><алгоритм, ><который ><определяет, ><является ><ли ><выра><жение ><исчисления ><предикатов ><логическим ><следствием ><некоторого ><набора ><утверждений. ><Это ><предполагает ><поиск ><от ><цели ><с ><применением ><правил ><модус ><поненс, ><определяющих ><пе><реходы ><между ><состояниями. ><Имея ><цель ><(типа ><р(а)), ><алгоритм ><использует ><унификацию ><для ><выбора ><импликаций, ><заключения ><которых ><соответствуют ><цели ><(например, >®< ><р(Х)). ><Поскольку ><алгоритм ><обрабатывает ><импликации ><как ><потенциальные ><правила ><для ><разрешения ><запроса, ><их ><часто ><называют ><просто ><правилами. ><После ><унификации ><цели ><с ><за><ключением ><импликации ><(или ><правила) ><и ><применения ><результирующих ><подстановок ><ко ><всему ><правилу ><предпосылка ><этого ><правила ><становится ><новой ><целью ><(q(a)). ><Ее ><называют ><подцелью. ><Затем ><алгоритм ><повторяется ><для ><подцелей. ><Если ><подцель ><соответствует ><факту ><в ><базе ><знаний, ><поиск ><прекращается. ><Последовательность ><выводов, ><ведущая ><от ><исходной ><цели ><к ><данным ><фактам, ><доказывает ><истинность ><первоначальной ><цели.>

<(current_goal)><;>

<содержится ><в ><списке >

<%проверка ><на ><зацикливание >

<добавить ><в ><список >

<в ><базе ><данных ><остаются ><правила ><или ><факты ><для ><унификации >

<унифицируется ><с ><фактом:>

<- ><это ><конъюнкция(р ><^ ><...): >

<каждого ><конъюнкта >

<вызвать ><для ><конъюнкта; ><успешно ><завершается ><для ><всех>

<конъюнктов ><унифицируется ><с ><заключением ><правила>

<(р ><в ><® ><р) ><: >

<применить ><подстановку ><унификации ><цели>

<к ><предпосылке ><(д);>

<вызвать ><для ><предпосылки; ><завершен ><успешно >

< ><%конец ><оператора >

<><190>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<В ><функции ><поиск ><выполняется ><с ><помощью ><модифицированной ><версии ><рекурсивного ><алгоритма, ><который, ><чтобы ><установить ><соответствие ><двух ><выраже><ний, ><использует ><унификацию ><(подраздел ><2.3.2), ><а ><для ><создания ><потомков ><состояний ><- ><правило ><модус ><поненс. ><Текущее ><состояние ><поиска ><представлено ><переменной ><-><Если ><соответствует ><факту, ><алгоритм ><возвращает ><В ><противном ><случае ><алгоритм ><пытается ><сопоставить ><с ><заключе><нием ><некоторого ><правила, ><рекурсивно ><просматривая ><все ><предпосылки. ><Если ><не ><согласуется ><ни ><с ><одним ><из ><утверждений, ><алгоритм ><возвращает ><Этот ><алгоритм ><также ><обрабатывает ><конъюнктивные ><цели, ><которые ><часто ><встречаются ><в ><предпосылках ><правила.>

<Для ><простоты ><этот ><алгоритм ><не ><решает ><проблему ><согласования ><подстановок ><перемен><ных ><при ><унификации. ><Это ><важно ><при ><разрешении ><конъюнктивных ><запросов ><с ><общими ><переменными ><(например ><р(Х)><^q><(Х)). ><Оба ><конъюнкта ><должны ><быть ><согласованы ><не ><только ><между ><собой, ><но ><и ><с ><унифицированными ><значениями ><переменной ><(подраздел ><2.3.2). ><Эту ><проблему ><мы ><рассмотрим ><в ><конце ><раздела.>

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

<5.2.1. ><Пример ><рекурсивного ><поиска: ><вариант ><задачи ><хода ><конем>

<Использование ><исчисления ><предикатов ><с ><общим ><контроллером ><для ><решения ><задач ><по><иска ><можно ><проиллюстрировать ><на ><примере ><упрощенной ><версии ><задачи ><хода ><конем ><(knight's ><В ><шахматах ><конь ><может ><перемещаться ><на ><два ><поля ><по ><горизонтали ><или ><вертикали ><и ><на ><одно ><поле ><в ><перпендикулярном ><направлении. ><При ><этом ><он ><не ><должен ><выйти ><за ><пределы ><шахматной ><доски. ><Таким ><образом, ><в ><самом ><общем ><случае ><существует ><не ><более ><восьми ><возможных ><ходов ><(рис. ><5.1).>

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

<На ><рис. ><5.2 ><показана ><шахматная ><доска, ><размером ><3x3, ><где ><каждая ><клетка ><помечена ><це><лым ><числом ><от ><1 ><до ><9. ><Для ><простоты ><эта ><схема ><маркировки ><будет ><использоваться ><вместо ><более ><общей ><схемы, ><в ><которой ><каждая ><клетка ><маркируется ><двумя ><цифрами, ><номером ><строки ><и ><номером ><столбца. ><Поскольку ><размер ><шахматной ><доски ><уменьшен, ><мы ><просто ><перечислим ><возможные ><ходы, ><а ><не ><будем ><разрабатывать ><общий ><оператор ><перемещения. ><В ><этом ><случае ><допустимые ><ходы ><на ><доске ><можно ><описать ><с ><помощью ><предиката ><параметрами ><которого ><являются ><номера ><начальной ><и ><конечной ><клетки ><допустимого ><хода. ><Например, ><1,8)>< ><перемещает ><коня ><из ><верхнего ><левого ><угла ><в ><середину ><нижнего ><ря><да. ><Предикаты ><на ><рис. ><5.2 ><описывают ><все ><возможные ><ходы ><для ><шахматной ><доски ><3x3.>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><191>

><<>

<Рис. ><5.1. ><Допустимые ><ходы ><конем ><на ><шахматной ><доске>

<>

<Рис. ><5.2. ><Шахматная ><доска ><3x3 ><с ><допустимыми ><ходами ><для ><упрощенной ><задачи ><хода ><конем>

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

<Другой ><запрос ><позволяет ><определить, ><куда ><конь ><может ><переместиться ><из ><некоторого ><местоположения, ><например, ><из ><клетки ><2. ><В ><этом ><случае ><цель ><унифицируется ><с ><двумя ><различными ><предикатами ><в ><базе ><знаний ><с ><подстановками ><{7/Х} ><и ><{9/Х}. ><Для ><це><ли ><2,3)>< ><результатом ><будет ><так ><как ><в ><базе ><знаний ><не ><существует ><элемента ><(2,3).>< ><Ответом ><на ><запрос ><(5,>< ><) ><тоже ><будет ><потому ><что ><не ><существует ><утверждений, ><задающих ><перемещение ><из ><клетки ><5.>

<Следующая ><задача ><состоит ><в ><построении ><алгоритма ><поиска ><для ><определения ><пути ><по><следовательных ><шагов ><по ><доске. ><Это ><можно ><сделать ><с ><помощью ><импликаций ><исчисления>

<><192>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<предикатов. ><Они ><добавляются ><к ><базе ><знаний ><как ><правила ><для ><создания ><путей ><последова><тельных ><шагов. ><Чтобы ><подчеркнуть, ><что ><эти ><правила ><обеспечивают ><поиск ><от ><цели, ><мы ><изменили ><направление ><стрелки ><импликации. ><Следовательно, ><правила ><будем ><писать ><как ><Заключение ><<- ><Предпосылка.>

<Например, ><путь ><с ><двумя ><ходами ><можно ><записать ><так.>

<" ><[path2(X, ><У) ><><$ Z ><[move(X, >

<Это ><правило ><утверждает, ><что ><для ><всех ><клеток ><и ><существует ><путь ><с ><двумя ><ходами, ><если ><существует ><такая ><клетка ><что ><конь ><может ><переместиться ><из ><в ><а ><затем ><- ><из ><в >

<Общее ><правило ><можно ><применять ><различными ><способами. ><Например, ><оно ><под><ходит ><для ><проверки ><существования ><двухходового ><пути ><из ><одной ><клетки ><в ><другую. ><Если ><функция ><вызывается ><для ><цели ><2(1><,3),>< ><то ><проверяется ><соответ><ствие ><этой ><цели ><последовательности ><правил ><При ><этом ><выполняются ><подста><новки ><для ><предпосылок ><правила. ><Результатом ><является ><конкретное ><правило, ><которое ><оп><ределяет ><условия, ><необходимые ><для ><такого ><пути.>

<2(1,3) ><3Z ><[move(1, ><3)].>

<Затем ><функция ><вызывает ><сама ><себя ><с ><этим ><параметром. ><Посколь><ку ><это ><конъюнкция ><двух ><выражений, ><пытается ><разрешить ><каждую ><подцель ><отдельно. ><Это ><требует ><не ><только ><согласованности ><обеих ><подцелей, ><но ><и ><непро><тиворечивости ><связывания ><всех ><переменных. ><Подстановка ><8 ><вместо ><дает ><возможность ><согласовать ><обе ><подцели.>

<Другой ><запрос ><может ><состоять ><в ><том, ><чтобы ><найти ><все ><клетки, ><которые ><могут ><быть ><достигнуты ><из ><клетки ><2 ><за ><два ><хода. ><Это ><достигается ><вызовом ><для ><цели ><Используя ><подобный ><процесс, ><можно ><найти ><все ><возможные ><подста><новки, ><включая ><{6/><} ><и ><{2/><} ><(с ><промежуточным ><значением ><равным ><7), ><а ><также ><{2/><} ><и ><{4/Y} ><(с ><промежуточным ><значением ><9). ><Дальнейшие ><запросы ><могут ><состоять ><в ><том, ><что><бы ><найти ><путь ><за ><два ><хода ><из ><клетки ><с ><некоторым ><номером ><в ><ту ><же ><самую ><клетку, ><из ><любой ><клетки ><в ><клетку ><5 ><и ><так ><далее. ><Обратите ><внимание ><на ><одно ><из ><преимуществ ><поиска ><по ><об><разцу: ><в ><качестве ><начальной ><цели ><могут ><быть ><взяты ><самые ><разнообразные ><запросы.>

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

<"X, ><[path3(X, >< ><$ ><[move(X, ><^ ><^ >

<Используя ><это ><определение, ><можно ><рассматривать ><такие ><задачи, ><как ><3(1,2), ><,X) ><или ><даже ><Эти ><задачи ><мы ><оставляем ><читателю ><в ><качестве ><уп><ражнений.>

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

"<[path3(X, ><3Z ><[move(X, ><^>< ><

><Это ><дает ><возможность ><получить ><общее ><рекурсивное ><правило.>

"<[><Х, ><3Z ><[move(X, ><^>< >

<Последнее ><правило ><можно ><использовать ><для ><проверки ><существования ><пути ><произ><вольной ><длины. ><Такая ><задача ><может ><быть ><сформулирована ><следующим ><образом: ><"Найти>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><193>

><<путь ><из ><одной ><клетки ><в ><другую, ><делая ><при ><этом ><ход ><из ><начальной ><клетки ><в ><промежуточ><ную, ><а ><затем ><из ><промежуточной ><в ><конечную".>

<Это ><рекурсивное ><правило ><"пути" ><неполно ><в ><том ><смысле, ><что ><в ><нем ><не ><определено ><ус><ловие ><выхода ><из ><рекурсии. ><Поэтому ><любая ><попытка ><определить ><путь ><к ><цели, ><используя ><предикат ><будет ><безуспешной, ><потому ><что ><каждая ><попытка ><найти ><промежуточный ><путь, ><снова ><будет ><приводить ><к ><рекурсивному ><вызову ><. ><Это ><объясняется ><тем, ><что ><не ><определено ><условие ><достижения ><конечного ><состояния. ><Этот ><недостаток ><может ><быть ><исправлен, ><если ><к ><базе ><знаний ><добавить ><условие ><Поскольку ><уни><фицируется ><только ><с ><предикатами ><типа ><3,3) ><или ><5,5), ><то ><оно ><определяет ><не><обходимое ><условие ><завершения ><рекурсии. ><Тогда ><общее ><рекурсивное ><определение ><пути ><задается ><двумя ><формулами ><исчисления ><предикатов.>

<" >

<">< ><[><Х, ><$ ><[move(X, ><^>< >

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

<1,8)>< >< >< ><1,6)>< ><9)>< ><7)>

<4) >< >< ><8)>< ><9)>< ><3)>

<1) >< >< ><7)>< ><2)>< >

< >< ><1)>< ><2)>< ><4)>

<" ><Х ><Х, >

<">< ><У ><[path(X, ><$ ><[move(X, ><^>< >

<Следует ><заметить, ><что ><при ><решении ><задачи ><использовались ><логические ><описания, ><опре><деляющие ><пространство ><состояний, ><и ><процедура ><поиска ><в ><этом ><про><странстве. ><Хотя ><правило ><достаточно ><удовлетворительно ><определяет ><путь, ><оно ><не ><ука><зывает, ><как ><найти ><этот ><путь. ><Действительно, ><на ><шахматной ><доске ><существует ><много ><других ><путей, ><которые ><не ><ведут ><к ><цели, ><но, ><тем ><не ><менее, ><удовлетворяют ><этому ><определению. ><На><пример, ><если ><не ><принимать ><во ><внимание ><механизм ><предотвращения ><зацикливания, ><то ><поиск ><цели ><(><1><,3)>< ><может ><привести ><к ><зацикливанию ><между ><клетками ><1 ><и ><8, ><вместо ><нахожде><ния ><правильного ><пути ><1®8®3. ><Таким ><образом, ><логическими ><следствиями ><базы ><знаний ><являются ><и ><цикл, ><и ><правильный ><(допустимый) ><путь. ><Аналогично, ><если ><рекурсивное ><пра><вило ><будет ><проверяться ><перед ><условием ><выхода ><из ><рекурсии, ><то ><условие ><выхода ><из ><ре><курсии ><3,3) ><будет ><проигнорировано, ><и ><поиск ><продолжится ><безо ><всякого ><смысла.>

<5.2.2. ><Усовершенствование ><алгоритма ><поиска ><по ><образцу>

<Хотя ><начальная ><версия ><функции ><определяет ><правильное ><поведение ><алгоритма ><поиска ><для ><выражений ><исчисления ><предикатов, ><все ><же ><стоит ><обратить ><внимание ><на ><некоторые ><тонкости. ><Они ><включают ><порядок ><рассмотрения ><альтернативных ><вариантов ><и ><корректную ><обработку ><полного ><набора ><логических ><операторов ><(><^><, ><и >?<). ><Логика ><по ><своей ><сути ><декларативна, ><и ><без ><предписаний ><стратегии ><поиска ><она ><определяет ><пространство ><возможных ><выводов, ><но ><не ><указывает ><решателю, ><как ><выделить ><из ><него ><полезные.>

<Для ><реализации ><рассуждений ><средствами ><исчисления ><предикатов ><необходим ><такой ><режим ><управления, ><который ><осуществляет ><систематический ><поиск ><в ><пространстве, ><и ><при>

<><194>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

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

<Другая ><проблема ><заключается ><в ><наличии ><логических ><связок ><в ><предпосылках ><правил, ><например, ><в ><импликациях ><вида: ><р?>< ><или ><Оператор ><л ><означает, ><что ><ре><зультат ><будет ><истиной, ><если ><выражения ><и ><г ><тоже ><истинны. ><Кроме ><того, ><конъюнкты ><в ><выражениях ><должны ><разрешаться ><с ><помощью ><согласованных ><значений ><переменных. ><Так, ><чтобы ><найти ><значение ><выражения ><р(Х)><^q><(Х), ><не ><достаточно ><разрешить ><р(Х) ><и ><ис><пользуя ><подстановку ><{а/Х} ><и ><{b><Оба ><конъюнкта ><должны ><быть ><разрешены ><с ><помощью ><одного ><и ><того ><же ><соответствующего ><значения ><переменной ><С ><другой ><стороны, ><оператор ><(или) ><обеспечивает ><истинность ><для ><всего ><выражения, ><если ><хотя ><бы ><одна ><из ><его ><частей ><является ><истиной. ><Алгоритм ><поиска ><должен ><принимать ><это ><во ><внимание.>

<Последнее ><дополнение ><к ><рассмотренному ><алгоритму ><- ><это ><его ><способность ><находить ><цель, ><используя ><логическое ><отрицание ><. ><Функция ><обрабатывает ><ин><вертированные ><цели, ><разрешая ><вначале ><операнд ><отрицания ><Если ><эта ><подцель ><дости><жима, ><то ><процедура ><возвращает ><Если ><же ><эта ><цель ><недостижи><ма, ><то ><возвращает ><пустое ><множество ><подстановок, ><указывающих ><на ><успех. ><Обратите ><внимание ><на ><то, ><что ><даже ><если ><подцель ><содержит ><переменные, ><то ><ре><зультат ><разрешения ><ее ><отрицания ><не ><может ><содержать ><никаких ><подстановок. ><Это ><связано ><с ><тем, ><что ><отрицание ><® ><принимает ><значение ><"истина", ><только ><если ><его ><операнд ><не ><удов><летворяется. ><Следовательно, ><операция ><отрицания ><не ><может ><возвращать ><никаких ><значе><ний ><связывания ><для ><этого ><операнда.>

<Наконец, ><алгоритм ><должен ><возвращать ><не ><значение ><а ><те ><значения ><связывания, ><которые ><использовались ><при ><решении. ><Например, ><для ><нахождения ><пути ><1, ><сущест><венной ><частью ><решения ><являются ><подстановки ><{6/Х} ><и ><{8/Х}.>

<Окончательная ><версия ><функции ><возвращающая ><множество ><уни><фикаций, ><удовлетворяющих ><каждой ><подцели, ><имеет ><следующий ><вид.>

< >< ><содержится ><в >< >< ><%проверка ><на ><зацикливание>

<добавить >< >< ><в >< ><список >< ><остаются ><унифицирующие ><факты ><или ><правила >

< ><унифицируется >< ><с >< ><фактом: ><унифицирующие ><подстановки;>

< ><инвертирована >< >< ><(? ><р) ><: >

<вызвать ><для ><р; ><возвращает >

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><195>

><< ><{};>< ><%отрицание ><истинно>

< >

<- ><это ><конъюнкция >< >< ><(р ><^ >< ><...): >

<каждого ><конъюнкта >

<вызвать ><для ><конъюнкта; ><возвращает >

<применить >< ><подстановки ><к ><другим ><конъюнктам; >

<возвращает ><для >< ><всех ><конъюнктов ><композицию ><всех ><унификаций; >< >

<- ><это ><дизъюнкция >< >< ><(p >< >< ><...): >< ><каждого ><дизъюнкта>

<вызвать ><для ><дизъюнкта >< ><больше >< ><нет ><дизъюнктов ><или ><возвращает ><подстановки >< >

<унифицируется ><с >< ><заключением >< >< ><(p >< ><: >

<применить >< ><подстановки ><унификации ><цели ><к ><предпосылке >< >< ><(q)><; ><вызвать ><для >< ><предпосылки; ><возвращает ><объединение ><подстановок ><р ><и >< >

< ><%><окончание ><оператора >

< ><%><окончание ><цикла >

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

<5.3. ><Продукционные ><системы>

<><5.3.1. ><Определение ><и ><история ><развития>

<Продукционная ><система ><(production ><- ><это ><модель ><вычислений, ><играющая ><особо ><важную ><роль ><в ><задачах ><искусственного ><интеллекта ><как ><для ><создания ><алгоритмов>

<><196>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<поиска, ><так ><и ><для ><моделирования ><решения ><задач ><человеком. ><Продукционная ><система ><обеспечивает ><управление ><процессом ><решения ><задачи ><по ><образцу ><и ><состоит ><из ><набора ><продукционных ><правил ><(production ><рабочей ><памяти ><(working ><и ><цикла ><управления ><"распознавание-действие".>

<ОПРЕДЕЛЕНИЕ>

<ПРОДУКЦИОННАЯ ><СИСТЕМА>

<Продукционную ><систему ><можно ><определить ><на ><основе ><следующих ><категорий.>

<Набор >< >< ><продукционных >< >< ><правил. >< >< >< ><Их >< >< >< ><часто >< >< >< ><просто >< >< >< ><называют >< >< ><продукциями

><(productions). ><Продукция ><- ><это ><пара ><"условие-действие", ><которая ><определяет ><одну

><порцию ><знаний, ><необходимых ><для ><решения ><задачи. ><Условная ><часть ><правила ><- ><это

><образец ><(шаблон), ><который ><определяет, ><когда ><это ><правило ><может ><быть ><применено

><для ><решения ><какого-либо ><этапа ><задачи. ><Часть ><действия ><определяет ><соответст><вующий ><шаг ><в ><решении ><задачи.>

<Рабочая ><память ><(working ><содержит ><описание ><текущего ><состояния ><ми

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

><рабочей ><памяти.>

<Цикл ><"распознавание-действие". ><Управляющая ><структура ><продукционной ><систе><мы ><проста: ><рабочая ><память ><инициализируется ><начальным ><описанием ><задачи. ><Текущее ><состояние ><решения ><задачи ><представляется ><набором ><образцов ><в ><рабочей ><памяти. ><Эти ><образцы ><сопоставляются ><с ><условиями ><продукционных ><правил; ><что ><порождает ><подмножество ><правил ><вывода, ><называемое ><конфликтным ><множест><вом ><(conflict ><Условия ><этих ><правил ><согласованы ><с ><образцами ><в ><рабочей ><памя><ти. ><Продукции, ><содержащиеся ><в ><конфликтном ><множестве, ><называют ><допусти><мыми. ><Выбирается ><и ><активизируется ><одна ><из ><продукций ><конфликтного ><множест><ва ><(разрешение ><конфликта). >< ><Активизация ><правила ><означает ><выполнение ><его ><действия. ><При ><этом ><изменяется ><содержание ><рабочей ><памяти. ><После ><того ><как ><вы><бранное ><правило ><сработало, ><цикл ><управления ><повторяется ><для ><модифицирован><ной ><рабочей ><памяти. ><Процесс ><заканчивается, ><если ><содержимое ><рабочей ><памяти ><не ><соответствует ><никаким ><условиям.>

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

<Чистая ><продукционная ><модель ><не ><имеет ><никакого ><механизма ><выхода ><из ><тупиковых ><состояний ><в ><процессе ><поиска; ><она ><просто ><продолжает ><работать ><до ><тех ><пор, ><пока ><не ><будут ><исчерпаны ><все ><допустимые ><продукции. ><Многие ><практические ><реализации ><продукционных ><систем ><содержат ><механизмы ><возврата ><в ><предыдущее ><состояние ><ра><бочей ><памяти.>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><197>

><<Схема ><продукционной ><системы ><представлена ><на ><рис. ><5.3.>

<Простой ><пример ><работы ><продукционной ><системы ><представлен ><на ><рис. ><5.4. ><Данная ><продукционная ><система ><сортирует ><строку, ><состоящую ><из ><символов ><и ><с. ><В ><этом ><при><мере ><продукция ><является ><допустимой, ><если ><ее ><условие ><соответствует ><части ><строки ><в ><ра><бочей ><памяти. ><При ><выполнении ><правила ><подстрока, ><которая ><соответствовала ><его ><усло><вию, ><заменяется ><строкой ><из ><правой ><части ><правила. ><Продукционная ><система ><- ><это ><общая ><модель ><вычислений, ><которая ><может ><быть ><запрограммирована ><для ><выполнения ><какой-><либо ><задачи ><на ><компьютере. ><Однако ><настоящее ><ее ><предназначение ><- ><это ><реализация ><ин><теллектуальных ><систем.>

<Впервые ><идея ><разработки ><программ ><компьютерных ><вычислений, ><основанных ><на ><"продукционных ><правилах", ><появилась ><в ><[Post, ><1943]. ><В ><этой ><работе ><модель ><продукцион><ных ><правил ><предложена ><в ><качестве ><формальной ><теории ><вычислений. ><Основа ><этой ><тео><рии ><- ><набор ><правил ><вывода ><для ><строк, ><во ><многом ><аналогичный ><правилам ><синтаксиче><ского ><анализа ><из ><примера ><3.3.6. ><Эта ><теория ><также ><тесно ><связана ><с ><алгоритмами ><Маркова ><[Markov, ><1954] ><и ><подобно ><им ><эквивалентна ><машине ><Тьюринга.>

<Интересное ><приложение ><продукционных ><правил ><к ><моделированию ><человеческого ><мышления ><описано ><в ><работах ><Нюэлла ><и ><Саймона ><из ><технологического ><института ><(теперь ><- ><в ><1960-1970-х ><годах. ><Программы, ><которые ><они ><разработали, ><включая ><Универсальный ><решатель ><задач ><(General ><послужили ><важным ><приложением ><продукционных ><систем ><в ><искусственном ><интеллекте. ><Авторы ><исследовали ><человеческое ><мышление ><в ><процессе ><решения ><различных ><задач, ><таких ><как ><задачи ><по ><логике ><предикатов ><или ><игре ><в ><шахматы. ><Были ><составлены ><и ><разобраны ><на ><элементарные ><компоненты ><протоколы ><(образцы ><по><ведения, ><включая ><словесные ><описания ><процесса ><решения ><задачи, ><движения ><глаз ><и ><т.д.) ><решения ><различных ><задач. ><Эти ><компоненты ><рассматривались ><как ><основные ><биты ><зна><ния ><о ><методах ><решения ><задач ><человеком, ><для ><которых ><был ><реализован ><поиск ><на ><графе ><(так ><называемом ><графе ><поведения ><задачи). ><Для ><осуществления ><поиска ><в ><этом ><графе ><использовалась ><продукционная ><система.>

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

<Следует ><заметить, ><что ><в ><работе ><Ньюэлла ><и ><Саймона ><продукционная ><система ><исполь><зовалась ><не ><только ><для ><реализации ><поиска ><на ><графе, ><но ><и ><для ><представления ><модели ><че><ловеческого ><поведения ><при ><решении ><задачи. ><Продукции ><соответствуют ><навыкам ><реше><ния ><задач ><в ><долгосрочной ><памяти ><человека. ><Подобно ><навыкам ><в ><долгосрочной ><памяти ><эти ><продукции ><не ><изменяются ><при ><работе ><системы. ><Они ><вызываются ><по ><"образцу" ><для ><данной ><специфической ><проблемы, ><а ><новые ><навыки ><могут ><быть ><добавлены ><к ><существую><щей ><базе ><знаний ><без ><соответствующей ><команды ><записи. ><Рабочая ><память ><продукционной ><системы ><соответствует ><краткосрочной ><памяти, ><или ><текущей ><области ><внимания ><челове><ка, ><и ><описывает ><текущую ><стадию ><решения ><задачи. ><Содержание ><рабочей ><памяти ><после ><решения ><задачи ><не ><сохраняется.>

<Эти ><результаты ><описаны ><в ><книгах ><[Newell ><и ><1972] ><и ><[Luger, ><1978], ><[Luger, ><1994].>

<><198>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

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

<>

<Рис. ><5.4. ><Работа ><простой ><продукционной ><системы>

<Ньюэлл, ><Саймон ><и ><другие ><исследователи ><использовали ><продукционные ><правила ><для ><моделирования ><различия ><между ><новичками ><и ><экспертами ><([Larkin ><и ><др., ><1980], ><[Simon ><и ><1978]) ><в ><таких ><областях, ><как ><решение ><алгебраических ><и ><физических ><задач. ><Про><дукционные ><системы ><также ><составляют ><основу ><для ><изучения ><человеческого ><и ><компью><терного ><обучения ><[Klahr ><и ><др., ><1987]. ><На ><этой ><традиции ><построены ><системы ><[Anderson, ><19836] ><и ><[Newell, ><1990].>

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

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>

<199>

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

<В ><результате ><исследования ><продукционных ><систем ><в ><Университете ><Карнеги ><Мел-><лон ><(Carnegie ><появилось ><важное ><семейство ><языков ><для ><систем ><ис><кусственного ><интеллекта. ><Это ><так ><называемые ><-языки ><официальных ><продукцион><ных ><систем ><(Official ><Хотя ><сначала ><они ><предназначались ><для ><мо><делирования ><человеческого ><подхода ><к ><решению ><задач, ><эти ><языки ><оказались ><очень ><эффективными ><для ><программирования ><экспертных ><систем ><и ><других ><приложений ><ис><кусственного ><интеллекта. ><- ><язык ><реализации ><для ><-конфигуратора ><и ><других ><экспертных ><систем, ><разработанных ><в ><Корпорации ><цифрового ><оборудования ><(Digital ><[McDermott, ><1981, ><1982], ><[Soloway ><и ><др., ><1987], ><[Barker ><и ><1989]. ><Широко ><распространены ><-интерпретаторы ><для ><пер><сональных ><компьютеров ><и ><рабочих ><станций. ><Активно ><используется ><созданная ><в ><НА><СА ><объектно-ориентированная ><версия ><продукционной ><системы ><реализован><ная ><на ><языке ><программирования ><С.>

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

<5.3.2. ><Примеры ><продукционных ><систем>