Библиотека    Новые поступления    Словарь    Карта сайтов    Ссылки





назад содержание далее

Часть 11.

<ПРИМЕР ><5.3.1. ><И ><снова ><"8-головоломка">

<Пространство ><поиска ><для ><задачи ><"8-головоломка", ><описанной ><в ><главе ><3, ><является ><дос><таточно ><сложным ><и ><интересным. ><В ><то ><же ><время ><оно ><настолько ><мало, ><что ><не ><вызывает ><особых ><трудностей ><в ><рассмотрении. ><"8-головоломка" ><часто ><используется ><для ><изучения ><различных ><стратегий ><поиска, ><например, ><поиска ><в ><глубину ><и ><в ><ширину, ><а ><также ><эвристи><ческих ><стратегий ><(см. ><главу ><4). ><Здесь ><мы ><рассмотрим ><продукционную ><систему.>

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

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

<Пример ><решения ><этой ><задачи ><на ><основе ><поиска ><в ><пространстве ><состояний, ><описанный ><в ><[Nilsson, ><1980], ><проиллюстрирован ><на ><рис. ><5.5 ><и ><5.6. ><Поскольку ><путь ><к ><решению ><может ><находиться ><очень ><глубоко, ><если ><его ><не ><направлять, ><поиск ><был ><ограничен ><предельной ><глу><биной. ><Простой ><прием ><для ><реализации ><предельной ><глубины ><поиска ><- ><следить ><за ><длиной ><текущего ><пути, ><и ><в ><случае ><превышения ><предельной ><длины ><отслеживать ><путь ><в ><обратном ><направлении, ><т.е. ><запускать ><механизм ><поиска ><с ><возвратом. ><На ><рис. ><5.6 ><предельная ><глуби><на ><поиска ><равна ><5. ><Заметим, ><что ><число ><возможных ><состояний ><рабочей ><памяти ><растет ><экс><поненциально ><с ><увеличением ><глубины ><поиска.>

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

><<>

<>

<Начальное ><состояние>

<Целевое ><состояние>

<Продукционное ><множество>

<Условие>

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

<Действие>

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

<® ><переместить ><пустую ><ячейку ><влево ><®>< ><переместить ><пустую ><ячейку ><вверх ><®>< ><переместить ><пустую ><ячейку ><вправо ><®>< ><переместить ><пустую ><ячейку ><вниз>

<Рабочая ><память ><содержит ><текущее ><и ><целевое ><состояние ><игровой ><доски.>

<Режим ><управления>

<Испытать ><каждое ><правило ><по ><порядку.>

<Не ><допускать ><циклов.>

<Завершить ><работу ><при ><нахождении ><цели.>

<Рис. ><5.5. ><"8-головопомка ><" ><как ><продукционная ><система>

<>

<Рис. ><5.6. ><Решение ><задачи ><"8-головоломки" ><с ><помощью ><продукционной ><системы, ><в ><которой ><поиск ><ограничен ><глубиной ><5 ><[Nilsson, ><1980]>

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

<201>

><<ПРИМЕР ><5.3.2. ><Задача ><хода ><конем>

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

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

<№ ><правила> <Условие> <Действие>

<1> <Конь ><в ><поле ><1 ><®> <Ход ><конем ><в ><поле ><8>

<2> <Конь ><в ><поле ><1 ><®> <Ход ><конем ><в ><поле ><6>

<3> <Конь ><в ><поле ><2 ><®> <Ход ><конем ><в ><поле ><9>

<4> <Конь ><в ><поле ><2 >®<> <Ход ><конем ><в ><поле ><7>

<5> <Конь ><в ><поле ><3 ><®> <Ход ><конем ><в ><поле ><4>

<6> <Конь ><в ><поле ><3 ><®> <Ход ><конем ><в ><поле ><8>

<7> <Конь ><в ><поле ><4 ><®> <Ход ><конем ><в ><поле ><9>

<8> <Конь ><в ><поле ><4 ><®> <Ход ><конем ><в ><поле ><3>

<9> <Конь ><в ><поле ><6 ><®> <Ход ><конем ><в ><поле ><1>

<10> <Конь ><в ><поле ><6 ><®> <Ход ><конем ><в ><поле ><7>

<11> <Конь ><в ><поле ><7 >®<> <Ход ><конем ><в ><поле ><2>

<12> <Конь ><в ><поле ><7 ><®> <Ход ><конем ><в ><поле ><6>

<13> <Конь ><в ><поле ><8 ><®> <Ход ><конем ><в ><поле ><3>

<14> <Конь ><в ><поле ><8 >®<> <Ход ><конем ><в ><поле ><1>

<15> <Конь ><в ><поле ><9 ><®> <Ход ><конем ><в ><поле ><2>

<16> <Конь ><в ><поле ><9 ><®> <Ход ><конем ><в ><поле ><4>

<Интересно ><заметить, ><что ><реализация ><предиката ><пути ><в ><задаче ><хода ><конем ><из ><раз><дела ><5.2 ><фактически ><обеспечивает ><построение ><продукционной ><системы! ><С ><этой ><точки ><зрения ><- ><это ><просто ><интерпретатор, ><а ><реальный ><поиск ><фактически ><осуществляется ><с ><помощью ><предиката ><Продукционные ><правила- ><это ><факты ><пе><ремещений ><первый ><параметр ><которых ><определяет ><условие ><(на ><доске ><должно ><быть ><достаточно ><места, ><чтобы ><сделать ><ход), ><а ><второй ><- ><действие ><(поле, ><в ><которое ><конь ><может ><перейти). ><Цикл ><"распознавание-действие" ><(recognize-act) ><реализуется ><с ><помощью ><рекур><сивного ><предиката ><пути ><Рабочая ><память ><содержит ><текущее ><и ><желаемое ><целевое ><со><стояние. ><Ее ><можно ><представить ><параметрами ><предиката ><пути ><На ><данной ><итерации ><конфликтное ><множество ><- ><это ><все ><выражения ><перемещений, ><которые ><унифицируются ><с ><целью ><Эта ><программа ><использует ><простую ><стратегию ><разрешения ><конфлик><тов, ><состоящую ><в ><выборе ><и ><активизации ><первого ><предиката ><перемещения ><в ><базе ><знаний, ><который ><не ><ведет ><к ><повторному ><состоянию. ><Контроллер ><также ><осуществляет ><возвраты ><из>

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

><<тупиковых ><состояний. ><Эта ><версия ><определения ><предиката ><для ><продукционной ><сис><темы ><показана ><на ><рис. ><5.7.>

<Таблица ><5.1. ><Продукционная ><система ><для ><решения ><задачи ><хода ><конем ><на ><поле ><3*3>

<>

<>

<Рис. ><5.7. ><Рекурсивный ><алгоритм ><вычисления ><пути ><в ><продукционной ><системе>

<Продукционные ><системы ><могут ><порождать ><бесконечные ><циклы ><при ><поиске ><на ><графе ><про><странства ><состояний. ><Эти ><циклы ><особенно ><трудно ><определить ><в ><продукционной ><системе, ><по><тому ><что ><правила ><могут ><активизироваться ><в ><любом ><порядке. ><Следовательно, ><зацикливание ><может ><появиться ><при ><работе ><системы, ><но ><его ><не ><легко ><обнаружить ><путем ><проверки ><синтаксиса ><набора ><правил. ><Например, ><при ><использовании ><порядка ><следования ><правил ><в ><задаче ><хода ><конем, ><описанного ><в ><разделе ><5.2, ><и ><стратегий ><разрешения ><конфликтов ><путем ><выбора ><первого ><соответствующего ><правила ><образец ><будет ><соответствовать ><факту ><указывая ><на ><перемещение ><в ><поле ><9. ><На ><следующей ><итерации ><образец ><будет ><сопоставлен ><с ><9,2). ><Алгоритм ><снова ><вернется ><в ><поле ><2, ><образуя ><цикл.>

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

<203>

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

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

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

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

<Модифицированное ><рекурсивное ><определение ><пути ><выглядит ><так.>

<"Xpath(X,X)>

<"X,Y><$ Z ><^ ><><(been(Z)) ><^ >

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

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

<ПРИМЕР ><5.3.3. ><Полная ><задача ><хода ><конем>

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

<Если ><пронумеровать ><строки ><и ><столбцы ><шахматной ><доски, ><то ><можно ><сформулировать ><продукционное ><правило ><для ><хода ><конем: ><вниз ><на ><две ><клетки ><и ><вправо ><на ><одну.>

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

><<УСЛОВИЕ: ><л >

<ДЕЙСТВИЕ: ><= ><+ ><2 ><л ><= >

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

<6) ><^ ><2)) ><^ ><7) ><^ ><1))>

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

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

<ПРИМЕР ><5.3.4. ><Финансовый ><советник ><как ><продукционная ><система>

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

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

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

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

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

<Управление ><посредством ><выбора ><стратегии ><поиска: ><на ><основе ><данных ><или ><отдели>

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

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

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

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

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

<После ><проверки ><соответствия ><действий ><их ><условия ><добавляются ><в ><рабочую ><память, ><формируя ><новые ><подцели ><(или ><состояния) ><поиска.>

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

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

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

<>

<Продукционное ><множество:>

<®®цель>

<®®q>

<начапо®>

<Последовательность ><выполнения:>

<>

<Просмотренная ><часть ><пространства:>

<>

<Рис. ><5.8. ><Поиск ><на ><основе ><данных ><в ><продукционной ><системе>

<На ><рис. ><5.9 ><дан ><пример ><рассуждений ><от ><цели ><на ><том ><же ><наборе ><продукционных ><правил, ><который ><показан ><на ><рис. ><5.8. ><Заметим, ><что ><в ><процессе ><поиска ><от ><цели ><активизируется ><со><всем ><другая ><последовательность ><продукционных ><правил ><и ><исследуется ><не ><то ><пространст><во, ><что ><в ><версии ><поиска ><на ><основе ><данных.>

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

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

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

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

<207>

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

<Можно ><также ><использовать ><комбинацию ><стратегий. ><Например, ><вначале ><вести ><по><иск ><в ><прямом ><направлении ><от ><данных ><до ><тех ><пор, ><пока ><число ><состояний ><не ><станет ><достаточно ><большим. ><Затем ><изменить ><направление ><поиска, ><направив ><его ><от ><цели, ><и ><использовать ><возможные ><подцели ><для ><выбора ><среди ><состояний. ><Опасность ><такого ><подхода ><состоит ><в ><том, ><что ><при ><использовании ><эвристического, ><или ><"жадного", ><ал><горитма ><поиска ><(глава ><4) ><просмотренные ><части ><графа ><могут ><не ><совпасть ><друг ><с ><дру><гом. ><Тогда ><потребуется ><более ><длительный ><поиск, ><чем ><при ><простом ><подходе ><(рис. ><5.10). ><Однако ><если ><коэффициент ><ветвления ><пространства ><не ><изменяется ><и ><ис><пользуется ><исчерпывающий ><поиск, ><комбинированная ><стратегия ><поиска ><может ><значи><тельно ><сузить ><исследуемое ><пространство, ><как ><показано ><на ><рис. ><5.11.>

<Продукционное ><множество:>

<®®цель>

<®®р>

<начало®>

<Последовательность ><выполнения:>

<Номер ><итерации> <Рабочая ><память> <Множество ><конфликтов> <Примененное ><правило>

<0> <цель> <1> <1>

<1> <цель, ><р, > <1,2,3,4> <2>

<2> <цель, ><р, > <1,2,3,4,5> <3>

<3> <цель, ><р, ><л, > <1,2,3,4,5> <4>

<4> <цель, ><р, ><и> <1,2,3,4,5> <5>

<5> <цель, ><и, > <1,2,3,4,5,6> <6>

<6> <цель, ><р, ><начало> <1,2,3,4,5,6> <останов>

<>

<Просмотренная ><часть ><пространства:>

<>

<Рис. ><5.9. ><Поиск ><от ><цели ><в ><продукционной ><системе>

<><208>

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

><<>

<Рис. ><5.10. ><Двунаправленный ><расширенный ><поиск>

<>

<Рис. ><5.11. ><Двунаправленный ><поиск, ><отсекающий ><большую ><часть ><пространства, ><исследуе><мую ><при ><однонаправленном ><поиске>

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

<209>

><<Управление ><поиском ><с ><помощью ><структуры ><правил>

<Структура ><правил ><в ><продукционной ><системе, ><включая ><различия ><между ><условием ><и ><действием, ><а ><также ><порядок ><проверки ><условий, ><определяет ><метод ><исследования ><про><странства. ><Описывая ><исчисление ><предикатов ><как ><язык ><представления, ><мы ><подчеркива><ли ><декларативный ><характер ><его ><семантики. ><Таким ><образом, ><выражения ><исчисления ><предикатов ><всего ><лишь ><определяют ><истинные ><отношения ><в ><области ><формулировки ><за><дачи ><и ><не ><делают ><никаких ><утверждений ><относительно ><порядка ><интерпретации ><их ><ком><понентов. ><Следовательно, ><некоторое ><частное ><правило ><может ><иметь ><вид ><"X ><(foo(X) ><^>< ><(Х) >®< ><тоо(Х)). ><Согласно ><правилам ><исчисления ><предикатов ><альтернативная ><форма ><того ><же ><правила ><может ><быть ><такой ><(foo(X) >®< ><тоо(Х) ><Эквивалент><ность ><этих ><двух ><выражений ><может ><быть ><продемонстрирована ><с ><помощью ><таблицы ><истинности ><(раздел ><2.1).>

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

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

<Несмотря ><на ><то ><что ><выражения ><"X(foo(X) ><®® ><тоо(Х)) ><и ><"X ><(foo(X) ><®® ><тоо(Х) ><- ><логически ><эквивалентны, ><при ><реализации ><поиска ><они ><обрабатыва><ются ><не ><одинаково.>

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

<Управление ><поиском ><через ><разрешение ><конфликтов>

<Продукционные ><системы ><(как ><и ><все ><системы, ><основанные ><на ><знаниях) ><позволяют ><представлять ><эвристики ><непосредственно ><в ><правилах, ><описывающих ><знания. ><Кроме ><того, ><они ><предлагают ><другой ><метод ><эвристического ><управления ><- ><через ><разрешение ><конфликтов. ><Простейшая ><подобная ><стратегия ><сводится ><к ><тому, ><чтобы ><выбирать ><пер><вое ><соответствующее ><правило ><из ><рабочей ><памяти. ><Однако ><для ><разрешения ><конфлик><тов ><(conflict ><потенциально ><может ><быть ><применена ><любая ><стратегия. ><На><пример, ><в ><поддерживаются ><следующие ><стратегии ><разрешения ><конфликтов ><[Brownston ><и ><др., ><1985].>

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

><<Рефракция ><(><Рефракция ><означает, ><что ><после ><активизации ><правила ><оно ><не

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

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

<Специфичность ><(><Согласно ><этой ><стратегии ><целесообразнее ><использовать

><более ><конкретное, ><а ><не ><более ><общее ><правило. ><Одно ><правило ><более ><специфично

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

<5.3.4. ><Преимущества ><продукционных ><систем ><для ><ИИ>

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

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

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

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

<Управление ><на ><основе ><образцов ><(pattern-directed ><Задачи, ><решаемые ><с ><по><мощью ><программ ><ИИ, ><требуют ><особой ><гибкости ><при ><выполнении ><программы. ><Это ><вызва><но ><еще ><и ><тем ><фактом, ><что ><правила ><в ><продукционной ><системе ><могут ><запускаться ><в ><любой ><последовательности. ><Описание ><задачи, ><представляющее ><текущее ><состояние ><мира, ><опре><деляет ><конфликтное ><множество ><и, ><следовательно, ><конкретный ><путь ><поиска ><и ><решения.>

<Возможности ><эвристического ><управления ><поиском. ><Несколько ><методов ><эвристи><ческого ><управления ><были ><описаны ><в ><предыдущем ><разделе.>

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

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

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

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

<Правдоподобная ><модель ><решения ><задачи ><человеком. ><Среди ><первых ><моделей, ><исполь><зующих ><продукционные ><системы, ><были ><модели ><нахождения ><решения ><задач ><человеком ><[Newell ><и ><1972]. ><Эти ><системы, ><главным ><образом, ><использовались ><в ><качестве ><модели ><че><ловеческой ><деятельности ><в ><различных ><областях ><научных ><исследований ><(глава ><16).>

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

<5.4. ><Архитектура ><"классной ><доски">

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

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

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

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

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

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

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

<Подход ><"классной ><доски" ><к ><организации ><большой ><программы ><изначально ><был ><реализован ><в ><системе ><[Erman ><и ><др., ><1980], ><[Reddy, ><1976]. ><- ><это ><программа ><понимания ><речи. ><Первоначально ><она ><была ><разработана ><как ><внешний ><интерфейс ><для ><базы ><данных ><публикаций ><по ><теории ><вычислительных ><систем. ><Пред><полагалось, ><что ><абонент ><библиотеки ><может ><обратиться ><к ><компьютеру ><на ><английском ><языке ><с ><запросом ><типа: ><"Есть ><ли ><у ><вас ><какие-нибудь ><работы ><авторов ><Фейгенбаума ><(Feigenbaum) ><и ><Фельдмана ><(Feldman)?". ><Компьютер ><должен ><ответить ><на ><этот ><вопрос, ><предоставив ><информацию ><из ><базы ><данных ><библиотеки. ><Понимание ><речи ><требует ><ин><теграции ><ряда ><различных ><процессов, ><которым ><необходимы ><различные ><знания ><и ><ал><горитмы. ><Сложность ><этих ><алгоритмов ><и ><знаний ><может ><расти ><экспоненциально. ><Об><работка ><сигналов, ><распознавание ><фонем, ><слогов ><и ><слов, ><синтаксический ><анализ ><и ><се><мантический ><анализ ><- ><все ><эти ><процессы ><связаны ><друг ><с ><другом ><в ><процессе ><интерпретации ><речи.>

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

><<>

<Рис. ><5.12. ><Архитектура ><"классной ><доски ><">

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

< ><Форма ><волны ><(временная ><диаграмма) ><акустического ><сигнала.>

< ><Фонемы ><или ><возможные ><звуковые ><сегменты ><акустического ><сигнала.>

< ><Слоги, ><которые ><могут ><быть ><составлены ><из ><фонем.>

< ><Возможные ><слова, ><результат ><анализа ><первого ><.>

< ><Возможные ><слова, ><результат ><анализа ><второго ><(обычно ><рассматриваются>

<слова ><из ><различных ><частей ><данных).>

< ><Генерация ><возможных ><последовательностей ><слов.>

< ><Связывание ><последовательности ><слов ><в ><фразы.>

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

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

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

<><214>

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

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

<Когда ><программа ><содержала ><базу ><данных ><около ><1000 ><слов, ><она ><работала ><дос><таточно ><хорошо, ><хотя ><немного ><медленно. ><Когда ><же ><база ><данных ><была ><расширена, ><данные ><оказались ><слишком ><сложными ><для ><источников ><знания, ><и ><не ><могли ><их ><обработать. ><Сис><тема ><[Balzer ><и ><другие, ><1980], ><[Erman ><и ><др., ><1981] ><- ><это ><обобщение ><подхода, ><принятого ><в ><-П. ><Временное ><измерение ><в ><-Ш ><не ><используется, ><но ><различ><ные ><уровни ><анализа ><сохранены. ><"Классная ><доска" ><в ><-Ш ><предназначена ><для ><взаимо><действия ><с ><реляционной ><базой ><данных ><общего ><назначения. ><На ><самом ><деле, ><-Ш ><- ><это ><оболочка ><для ><проектирования ><экспертных ><систем ><(см. ><подраздел ><7.1.1).>

<Важным ><нововведением ><в ><-Ш ><стало ><отделение ><планировщика ><и ><превращение ><его ><в ><контроллер ><("классную ><доску") ><для ><первичной ><классной ><доски ><предметной ><области. ><По><явление ><второй ><"классной ><доски" ><позволило ><разделить ><процесс ><планирования ><и ><реализовать ><его ><с ><помощью ><многочисленных ><источников ><знаний ><подобно ><тому, ><как ><сама ><задача ><разделяет><ся ><на ><различные ><уровни ><анализа. ><За ><разные ><аспекты ><процедуры ><решения ><(например, ><когда ><и ><как ><применять ><знания ><о ><предметной ><области) ><стали ><отвечать ><различные ><Таким ><образом, ><вторая ><"классная ><доска" ><позволяет ><сравнить ><и ><сбалансировать ><разные ><решения ><отдельных ><за><дач ><[Nii ><и ><1979], ><[Nii, ><1986a], ><[Nii, ><19866]. ><Существует ><и ><альтернативная ><модель ><"классной ><доски", ><согласно ><которой ><важные ><части ><базы ><знаний ><остаются ><на ><"классной ><доске", ><а ><не ><распределяются ><по ><источникам ><знаний ><[Skinner ><и ><1991].>

<5.5. ><Резюме ><и ><дополнительная ><литература>

<><В ><главе ><5 ><обсуждалась ><реализация ><стратегий ><поиска, ><описанных ><в ><главах ><3 ><и ><4. ><Таким ><образом, ><ссылки, ><перечисленные ><в ><заключительной ><части ><глав ><3 ><и ><4, ><относятся ><также ><и ><к ><этой ><главе. ><В ><главе ><5 ><представлена ><рекурсия ><как ><важный ><инструмент ><программирования ><поиска ><на ><графе, ><а ><затем ><в ><рекурсивной ><форме ><реализован ><алгоритм ><поиска ><с ><возвратами ><(backtrack ><из ><главы ><3. ><Поиск ><по ><образцу ><(pattern-directed ><с ><использова><нием ><унификации ><и ><правил ><вывода ><упрощает ><реализацию ><поиска ><в ><пространстве ><логиче><ского ><вывода.>

<Было ><показано, ><что ><продукционная ><система ><является ><естественной ><структурой ><для ><моделирования ><решения ><задач ><и ><реализации ><алгоритмов ><поиска. ><Эта ><глава ><завершается ><примерами ><реализации ><продукционных ><систем, ><осуществляющих ><поиск ><на ><основе ><дан><ных ><и ><от ><цели. ><Действительно ><продукционные ><системы ><всегда ><были ><важной ><парадигмой ><для ><программирования ><задач ><ИИ, ><начиная ><с ><работ ><Ньюэлла ><и ><Саймона ><и ><их ><коллег ><из ><[Newell ><и ><1976], ><[Klahr ><и ><др., ><1987]. ><Продукционная ><система ><также ><является ><важной ><структурой, ><поддерживающей ><исследования ><в ><области ><когнитивистики ><(науки ><о ><мышлении) ><[Newell ><и ><1972], ><[Luger, ><1994].>

<Конкретные ><реализации ><продукционных ><систем ><описаны ><в ><[Brownston ><и ><др., ><1985] ><и ><[Waterman ><и ><1978].>

<Ранние ><исследования ><по ><модели ><"классной ><доски" ><описаны ><в ><работах, ><посвященных ><системе ><-П,- ><[Reddy, ><1976], ><[Erman ><и ><др., ><1980]. ><Дальнейшее ><развитие ><мето><дологии ><"классной ><доски" ><описано ><в ><работах ><[Lesser ><и ><1983], ><[Nii, ><1986a], ><[Nii, ><19866], ><посвященных ><системе ><-Ш, ><и ><[Engelmore ><и ><1988].>

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

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

<5.6. ><Упражнения>

<><1.>< ><Алгоритм ><проверки ><вхождения ><из ><подраздела ><5.1.1 ><рекурсивно ><определяет, ><является

><ли ><данный ><элемент ><членом ><списка.>

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

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

<Различие ><между ><атомами ><и ><элементами ><состоит ><в ><том, ><что ><элемент ><сам ><может ><быть ><списком. ><(Дополнительная ><информация ><содержится ><в ><разделе ><15.1.)>

<Напишите ><рекурсивный ><алгоритм ><поиска ><в ><ширину ><(с ><использованием ><списков >

><и ><Можно ><ли ><с ><учетом ><рекурсии ><обойтись ><при ><поиске ><в ><ширину ><без ><списка

><Объясните.>

<Проследите ><выполнение ><рекурсивного ><алгоритма ><поиска ><в ><глубину ><(без ><использова><ния ><списка ><в ><пространстве ><состояний, ><показанном ><на ><рис. ><3.10.>

<В ><древнеиндийской ><чайной ><церемонии ><принимают ><участие ><три ><человека: ><взрослый, ><слуга

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

<Используя ><определения ><перемещения ><и ><пути ><для ><задачи ><хода ><конем ><из ><раздела ><5.2,

><проследите ><выполнение ><алгоритма ><для ><следующих ><целей:>

<а)path(1,9); ><6)path(1,5); >

<Если ><предикаты ><выполняются ><по ><порядку, ><то ><в ><алгоритме ><поиска ><часто ><быва><ют ><зацикливания. ><Как ><обнаружить ><цикл ><и ><реализовать ><возврат ><в ><этом ><случае?>

<Запишите ><на ><языке ><псевдокода ><версию ><алгоритма ><с ><поиском ><в ><ши><рину ><(раздел ><5.2). ><Оцените ><временную ><и ><пространственную ><эффективность ><этого ><ал><горитма.>

<Используя ><в ><качестве ><модели ><правило ><из ><примера ><5.3.3, ><запишите ><восемь ><правил ><пе><ремещения ><для ><полной ><версии ><игры ><хода ><конем ><8x8.>

<Используя ><целевое ><и ><начальное ><состояния, ><показанные ><на ><рис. ><5.5, ><промоделируйте

><ход ><решения ><"8-головоломки" ><продукционной ><системой ><с ><использованием ><следую><щих ><стратегий:

216>

><<а)>< ><поиск ><от ><цели;>

<б)>< ><поиск ><на ><основе ><данных.>

<9. ><Рассмотрите ><задачу ><финансового ><советника, ><описанную ><в ><главах ><2, ><3 ><и ><4. ><Используя ><исчисление ><предикатов ><в ><качестве ><языка ><представления, ><решите ><следующие ><задачи.>

<Опишите ><задачу ><явно ><в ><виде ><продукционной ><системы.>

<Сгенерируйте ><пространство ><состояний ><и ><содержимое ><рабочей ><памяти ><при ><реше><нии ><задачи, ><описанной ><в ><примере ><из ><главы ><3, ><на ><основе ><данных.>

<Решите ><эту ><же ><задачу, ><используя ><стратегию ><поиска ><от ><цели.>

<В ><подразделе ><5.3.3 ><представлены ><общие ><стратегии ><разрешения ><конфликтов ><на ><основе

><рефракции ><(refraction), ><новизны ><(recency) ><и ><специфичности ><(specificity). ><Предложите

><и ><обоснуйте ><еще ><две ><такие ><стратегии.>

<Предложите ><две ><прикладные ><задачи, ><для ><решения ><которых ><можно ><использовать

><структуру ><"классной ><доски". ><Кратко ><охарактеризуйте ><организацию ><"классной ><доски"

><и ><источников ><знания ><для ><каждой ><задачи.>

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

>

назад содержание далее



ПОИСК:




© FILOSOF.HISTORIC.RU 2001–2021
Все права на тексты книг принадлежат их авторам!

При копировании страниц проекта обязательно ставить ссылку:
'Электронная библиотека по философии - http://filosof.historic.ru'
Сайт создан при помощи Богданова В.В. (ТТИ ЮФУ в г.Таганроге)