![]() |
![]() |
||
![]() |
![]() ![]() ![]() ![]() ![]() Часть 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>
<Интересно ><заметить, ><что ><реализация ><предиката ><пути >
<><202>< ><Часть >
><<тупиковых ><состояний. ><Эта ><версия ><определения ><предиката > <Таблица ><5.1. ><Продукционная ><система ><для ><решения ><задачи ><хода ><конем ><на ><поле ><3*3> <> <> <Рис. ><5.7. ><Рекурсивный ><алгоритм ><вычисления ><пути ><в ><продукционной ><системе>
<Продукционные ><системы ><могут ><порождать ><бесконечные ><циклы ><при ><поиске ><на ><графе ><про><странства ><состояний. ><Эти ><циклы ><особенно ><трудно ><определить ><в ><продукционной ><системе, ><по><тому ><что ><правила ><могут ><активизироваться ><в ><любом ><порядке. ><Следовательно, ><зацикливание ><может ><появиться ><при ><работе ><системы, ><но ><его ><не ><легко ><обнаружить ><путем ><проверки ><синтаксиса ><набора ><правил. ><Например, ><при ><использовании ><порядка ><следования ><правил > <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний> <203>
><<Чтобы ><предотвратить ><зацикливание, ><функция >
<В ><продукционной ><системе ><список ><уже ><обследованных ><состояний >
<Предположим, ><что ><функция >
<Предикат > <Модифицированное ><рекурсивное ><определение ><пути ><выглядит ><так.> <"Xpath(X,X)>
<"X,Y>
<В ><этом ><определении >
<Заметим, ><что ><исчисление ><предикатов ><используется ><как ><язык ><описания ><продукционных ><правил ><и ><элементов ><рабочей ><памяти. ><Процедурная ><сущность ><продукционных ><систем ><тре><бует, ><чтобы ><цели ><в ><определении ><предиката > <ПРИМЕР ><5.3.3. ><Полная ><задача ><хода ><конем> <Решение ><задачи ><хода ><конем ><можно ><обобщить ><для ><полной ><шахматной ><доски ><раз><мером ><8x8. ><Поскольку ><не ><имеет ><смысла ><нумеровать ><ходы ><в ><такой ><сложной ><задаче, ><заменим ><16 ><ходов ><набором ><из ><8 ><правил, ><генерирующих ><допустимые ><ходы ><конем. ><Эти ><ходы ><(продукции) ><соответствуют ><8 ><возможным ><вариантам ><перемещения ><коня ><(см. ><рис. ><5.1).> <Если ><пронумеровать ><строки ><и ><столбцы ><шахматной ><доски, ><то ><можно ><сформулировать ><продукционное ><правило ><для ><хода ><конем: ><вниз ><на ><две ><клетки ><и ><вправо ><на ><одну.>
<><204>< ><Часть >
><<УСЛОВИЕ: >
<ДЕЙСТВИЕ: >
<Если ><для ><представления ><продукций ><использовать ><исчисление ><предикатов, ><то ><игровую ><доску ><можно ><определить ><предикатом >
<Здесь >
<Функция > <ПРИМЕР ><5.3.4. ><Финансовый ><советник ><как ><продукционная ><система> <Во ><второй ><и ><третьей ><главе ><мы ><разработали ><модель ><небольшой ><системы ><"финансового ><советника". ><Для ><представления ><знаний ><о ><финансовом ><состоянии ><вкладчика ><было ><исполь><зовано ><исчисление ><предикатов, ><а ><для ><определения ><наилучшего ><способа ><вложения ><денег ><применялся ><поиск ><на ><графе. ><Продукционная ><система ><является ><естественным ><средством ><для ><реализации ><такой ><модели. ><Импликации ><логических ><описаний ><составляют ><продукци><онные ><правила. ><Вся ><конкретная ><информация, ><в ><том ><числе ><зарплата ><клиента, ><число ><ижди><венцев ><и ><т.п., ><помещается ><в ><рабочую ><(оперативную) ><память. ><Правила ><начинают ><функ><ционировать, ><как ><только ><удовлетворяются ><их ><предпосылки. ><Из ><противоречивой ><совокуп><ности ><правил ><выбирается ><некоторое ><правило. ><Оно ><выполняется, ><а ><его ><заключение ><добавляется ><в ><рабочую ><память. ><Это ><продолжается ><до ><тех ><пор, ><пока ><в ><рабочую ><память ><не ><будут ><добавлены ><все ><возможные ><заключения ><верхнего ><уровня. ><Действительно, ><многие ><оболочки ><экспертных ><систем ><являются ><продукционными ><системами ><с ><поддержкой ><до><полнительных ><возможностей. ><Среди ><них: ><интерфейс ><пользователя, ><поддержка ><рассужде><ний ><с ><неопределенностью, ><редактирование ><базы ><знаний ><и ><контроль ><выполнения ><поиска.> <5.3.3. ><Управление ><поиском ><в ><продукционных ><системах> <Модели ><продукционных ><систем ><предоставляют ><дополнительные ><возможности ><по ><до><бавлению ><эвристического ><управления ><к ><алгоритму ><поиска. ><Эти ><дополнительные ><удобства> <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><205> ><<включают ><выбор ><стратегии ><(на ><основе ><данных ><или ><от ><цели), ><выбор ><самой ><структуры ><пра><вил ><и ><стратегий ><для ><разрешения ><конфликтов.> <Управление ><посредством ><выбора ><стратегии ><поиска: ><на ><основе ><данных ><или ><отдели> <Поиск ><на ><основе ><данных ><начинается ><с ><описания ><задачи ><(например, ><в ><виде ><набора ><ло><гических ><аксиом, ><признаков ><болезни ><или ><массива ><данных, ><который ><необходимо ><интер><претировать), ><затем ><из ><имеющихся ><данных ><выводятся ><новые ><знания. ><Это ><осуществляется ><путем ><применения ><правил ><вывода, ><например, ><допустимых ><ходов ><в ><игре ><или ><других ><опе><раций, ><генерирующих ><новые ><состояния ><в ><текущем ><описании ><мира, ><и ><добавления ><резуль><татов ><к ><описанию ><рассматриваемой ><задачи. ><Этот ><процесс ><продолжается ><до ><тех ><пор, ><пока ><не ><будет ><достигнуто ><целевое ><состояние.> <Такое ><представление ><рассуждений ><на ><основе ><данных ><подчеркивает ><их ><соответствие ><мо><дели ><продукционной ><системы. ><"Текущее ><состояние ><мира" ><(это ><исходные ><данные, ><которые ><приняты ><как ><истина ><или ><выведены ><как ><истина ><с ><помощью ><правил ><вывода) ><помещается ><в ><ра><бочую ><память. ><Затем ><в ><цикле ><"распознавание-действие" ><текущее ><состояние ><сравнивается ><с ><(упорядоченным) ><набором ><продукций. ><Если ><эти ><данные ><соответствуют ><условиям ><одного ><из ><правил ><вывода ><(унифицируются ><с ><ними), ><применение ><этого ><правила ><добавляет ><новую ><пор><цию ><информации ><к ><текущему ><состоянию ><мира ><(изменяя ><рабочую ><память).>
<Все ><продукционные ><правила ><имеют ><форму > <На ><рис. ><5.8 ><представлен ><простой ><пример ><поиска ><на ><основе ><данных ><для ><набора ><продукционных ><правил, ><записанных ><в ><виде ><импликаций ><исчисления ><высказываний. ><Стратегия ><разрешения ><конфликтов ><- ><это ><простая ><стратегия ><выбора ><допустимого ><правила, ><которое ><сработало ><раньше ><всего ><(или ><совсем ><не ><активизировалось). ><Поиск ><прекращается, ><когда ><цель ><достигнута. ><Кроме ><того, ><на ><рисунке ><также ><представлены ><порядок ><активизации ><правил ><и ><состояния ><рабочей ><памяти ><в ><процессе ><выполнения, ><а ><также ><граф ><пространства ><поиска.>
<До ><сих ><пор ><мы ><рассматривали ><функционирование ><продукционных ><систем ><на ><основе ><данных. ><Однако ><существуют ><продукционные ><системы, ><осуществляющие ><поиск ><от ><цели. ><В ><главе ><3 ><говорилось ><о ><том, ><что ><поиск ><от ><цели ><начинается ><с ><цели ><и ><возвращается ><назад ><к ><фактам, ><соответствующим ><данной ><цели. ><Чтобы ><реализовать ><это ><в ><продукционной ><систе><ме, ><цель ><помещается ><в ><рабочую ><память, ><а ><затем ><проверяется ><ее ><соответствие ><действиям >
<После ><проверки ><соответствия ><действий >
<Затем ><проверяется ><соответствие ><новых ><состояний ><заключениям >
<><206>< ><Часть > ><< ><(активизированных) ><в ><процессе ><поиска, ><окажутся ><истинными. ><Эти ><условия ><и ><цепочка ><правил, ><ведущих ><к ><исходной ><цели, ><составляют ><доказательство ><ее ><истинности.> <> <Продукционное ><множество:>
<®®цель>
<начапо®> <Последовательность ><выполнения:> <> <Просмотренная ><часть ><пространства:> <> <Рис. ><5.8. ><Поиск ><на ><основе ><данных ><в ><продукционной ><системе> <На ><рис. ><5.9 ><дан ><пример ><рассуждений ><от ><цели ><на ><том ><же ><наборе ><продукционных ><правил, ><который ><показан ><на ><рис. ><5.8. ><Заметим, ><что ><в ><процессе ><поиска ><от ><цели ><активизируется ><со><всем ><другая ><последовательность ><продукционных ><правил ><и ><исследуется ><не ><то ><пространст><во, ><что ><в ><версии ><поиска ><на ><основе ><данных.>
<Как ><следует ><из ><вышеописанных ><примеров, ><продукционная ><система ><обеспечивает ><естественную ><реализацию ><поиска ><от ><цели ><и ><на ><основе ><данных. ><Продукционные ><пра><вила ><- ><это ><закодированный ><набор ><правил ><вывода ><(знаний ><в ><экспертной ><системе, ><ос><нованной ><на ><правилах) ><для ><изменения ><состояния ><внутри ><графа. ><Если ><текущее ><со><стояние ><мира ><(набор ><истинных ><утверждений, ><описывающих ><мир) ><соответствует ><ус><ловиям >
<С ><другой ><стороны, ><если ><проверяется ><соответствие ><цели ><части >
<Поскольку ><набор ><правил ><может ><активизироваться ><или ><на ><основе ><данных ><или ><от ><цели, ><можно ><сравнить ><эффективность ><этих ><подходов. ><Сложность ><поиска ><для ><обеих ><стратегий ><измеряется ><таким ><понятием, ><как ><коэффициент ><ветвления ><(branching > <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний> <207>
>< <Можно ><также ><использовать ><комбинацию ><стратегий. ><Например, ><вначале ><вести ><по><иск ><в ><прямом ><направлении ><от ><данных ><до ><тех ><пор, ><пока ><число ><состояний ><не ><станет ><достаточно ><большим. ><Затем ><изменить ><направление ><поиска, ><направив ><его ><от ><цели, ><и ><использовать ><возможные ><подцели ><для ><выбора ><среди ><состояний. ><Опасность ><такого ><подхода ><состоит ><в ><том, ><что ><при ><использовании ><эвристического, ><или ><"жадного", ><ал><горитма ><поиска ><(глава ><4) ><просмотренные ><части ><графа ><могут ><не ><совпасть ><друг ><с ><дру><гом. ><Тогда ><потребуется ><более ><длительный ><поиск, ><чем ><при ><простом ><подходе ><(рис. ><5.10). ><Однако ><если ><коэффициент ><ветвления ><пространства ><не ><изменяется ><и ><ис><пользуется ><исчерпывающий ><поиск, ><комбинированная ><стратегия ><поиска ><может ><значи><тельно ><сузить ><исследуемое ><пространство, ><как ><показано ><на ><рис. ><5.11.> <Продукционное ><множество:>
<®®цель>
<начало®> <Последовательность ><выполнения:> <Номер ><итерации> <Рабочая ><память> <Множество ><конфликтов> <Примененное ><правило> <0> <цель> <1> <1>
<1> <цель, ><р, >
<2> <цель, ><р, >
<3> <цель, ><р, >
<4> <цель, ><р, > <5> <цель, >
<6> <цель, ><р, > <> <Просмотренная ><часть ><пространства:> <> <Рис. ><5.9. ><Поиск ><от ><цели ><в ><продукционной ><системе> <><208>
<Часть > ><<> <Рис. ><5.10. ><Двунаправленный ><расширенный ><поиск> <> <Рис. ><5.11. ><Двунаправленный ><поиск, ><отсекающий ><большую ><часть ><пространства, ><исследуе><мую ><при ><однонаправленном ><поиске> <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний> <209> ><<Управление ><поиском ><с ><помощью ><структуры ><правил>
<Структура ><правил ><в ><продукционной ><системе, ><включая ><различия ><между ><условием ><и ><действием, ><а ><также ><порядок ><проверки ><условий, ><определяет ><метод ><исследования ><про><странства. ><Описывая ><исчисление ><предикатов ><как ><язык ><представления, ><мы ><подчеркива><ли ><декларативный ><характер ><его ><семантики. ><Таким ><образом, ><выражения ><исчисления ><предикатов ><всего ><лишь ><определяют ><истинные ><отношения ><в ><области ><формулировки ><за><дачи ><и ><не ><делают ><никаких ><утверждений ><относительно ><порядка ><интерпретации ><их ><ком><понентов. ><Следовательно, ><некоторое ><частное ><правило ><может ><иметь ><вид ><"X ><(foo(X) ><^>< > <Хотя ><эти ><формулировки ><логически ><эквивалентны, ><они ><не ><ведут ><к ><одинаковым ><резуль><татам, ><если ><интерпретируются ><как ><продукции ><(продукционные ><правила), ><потому ><что ><реа><лизация ><продукционной ><системы ><обеспечивает ><определенный ><порядок ><проверки ><соот><ветствия ><и ><активизации ><правил. ><По ><этой ><причине ><форма ><представления ><правил ><определя><ется ><удобством ><(или ><возможностями) ><проверки ><соответствия ><правилам ><в ><конкретной ><задаче. ><Это ><является ><результатом ><выбора ><способа ><интерпретации ><правил ><продукционной ><системой. ><Продукционная ><система ><налагает ><на ><декларативный ><язык ><описания ><правил ><процедурную ><семантику.> <Поскольку ><продукционная ><система ><проверяет ><правила ><в ><определенном ><порядке, ><про><граммист ><может ><управлять ><поиском ><через ><структуру ><и ><порядок ><следования ><правил ><в ><про><дукционном ><наборе.>
<Несмотря ><на ><то ><что ><выражения ><"X(foo(X) >???????????«? goо(Х) ><®® ><тоо(Х)) ><и ><"X ><(foo(X) ><®® ><тоо(Х) > <Квалифицированные ><специалисты ><кодируют ><наиболее ><значащие ><(ключевые) ><эв><ристики, ><руководствуясь ><своими ><профессиональными ><знаниями. ><В ><очередности ><предпосылок ><содержится ><важная ><процедурная ><информация, ><необходимая ><для ><ус><пешного ><решения ><проблемы. ><Очень ><важно, ><чтобы ><эта ><формулировка ><(форма ><выра><жения) ><сохранялась ><при ><написании ><программы. ><Например, ><когда ><механик ><говорит: ><"Если ><двигатель ><не ><вращается, ><и ><фары ><не ><горят, ><проверьте ><аккумулятор", ><водителю ><предлагается ><определенная ><последовательность ><действий. ><В ><логически ><эквивалент><ном ><предложении ><"Двигатель ><вращается ><или ><фары ><горят, ><или ><проверьте ><аккумуля><тор" ><эта ><информация ><теряется. ><Такая ><формулировка ><правил ><не ><выдерживает ><крити><ки, ><так ><как ><при ><управлении ><поиском ><необходимо, ><чтобы ><система ><вела ><себя ><логично, ><а ><последовательность ><активизации ><правил ><была ><понятной.> <Управление ><поиском ><через ><разрешение ><конфликтов>
<Продукционные ><системы ><(как ><и ><все ><системы, ><основанные ><на ><знаниях) ><позволяют ><представлять ><эвристики ><непосредственно ><в ><правилах, ><описывающих ><знания. ><Кроме ><того, ><они ><предлагают ><другой ><метод ><эвристического ><управления ><- ><через ><разрешение ><конфликтов. ><Простейшая ><подобная ><стратегия ><сводится ><к ><тому, ><чтобы ><выбирать ><пер><вое ><соответствующее ><правило ><из ><рабочей ><памяти. ><Однако ><для ><разрешения ><конфлик><тов ><(conflict >
<><210>< ><Часть >
><<Рефракция ><(> ><может ><быть ><запущено ><снова, ><пока ><не ><изменятся ><элементы ><рабочей ><памяти, ><соответ><ствующие ><его ><условиям. ><Рефракция ><препятствует ><зацикливанию.>
<Новизна ><(>
<Специфичность ><(> ><более ><конкретное, ><а ><не ><более ><общее ><правило. ><Одно ><правило ><более ><специфично ><(конкретно) ><чем ><другое, ><если ><оно ><содержит ><больше ><условий, ><а ><значит, ><соответству><ет ><меньшему ><количеству ><образцов ><в ><рабочей ><памяти.> <5.3.4. ><Преимущества ><продукционных ><систем ><для ><ИИ> <Как ><видно ><из ><предыдущих ><примеров, ><продукционная ><система ><обеспечивает ><общую ><струк><туру ><осуществления ><поиска. ><Благодаря ><ее ><простоте, ><модифицируемости ><и ><гибкости ><в ><приме><нении ><знаний ><для ><решения ><задач ><продукционная ><система, ><как ><оказалось, ><может ><быть ><важным ><механизмом ><для ><конструирования ><экспертных ><систем ><и ><других ><приложений ><ИИ. ><Главные ><преимущества ><продукционных ><систем ><искусственного ><интеллекта ><описаны ><ниже.> <Разделение ><знания ><и ><управления. ><Продукционная ><система ><- ><изящная ><модель ><раз><деления ><знания ><и ><управления ><в ><компьютерной ><программе. ><Управление ><обеспечивается ><циклом ><"распознание-действие" ><продукционной ><системы. ><При ><этом ><знания ><о ><методах ><решения ><задач ><сосредоточены ><непосредственно ><в ><правилах. ><Преимущество ><такого ><разде><ления ><заключается ><в ><простоте ><изменения ><базы ><знаний, ><при ><котором ><не ><требуется ><изме><нять ><код ><программы ><управления. ><И, ><наоборот, ><это ><позволяет ><изменять ><код ><управляющей ><части ><программы, ><не ><трогая ><набор ><правил ><вывода.> <Естественное ><соответствие ><поиску ><в ><пространстве ><состояний. ><Компоненты ><продукци><онной ><системы ><естественно ><отображаются ><в ><логическую ><структуру ><поиска ><в ><пространстве ><со><стояний. ><Последовательные ><состояния ><рабочей ><памяти ><составляют ><вершины ><графа ><простран><ства ><состояний. ><Правила ><вывода ><- ><набор ><возможных ><переходов ><между ><состояниями. ><Разре><шение ><конфликтов ><обеспечивает ><выбор ><перехода ><(ветви) ><в ><пространстве ><состояний. ><Эти ><правила ><упрощают ><выполнение, ><отладку ><и ><документирование ><алгоритмов ><поиска.> <Модульность ><продукционных ><правил. ><Важный ><аспект ><в ><моделировании ><продукци><онных ><систем ><- ><это ><отсутствие ><синтаксического ><взаимодействия ><между ><продукционны><ми ><правилами. ><Правила ><могут ><только ><влиять ><на ><активизацию ><других ><правил, ><изменяя ><об><разец ><в ><рабочей ><памяти. ><Правила ><не ><могут ><"вызывать" ><другие ><правила ><непосредственно, ><как ><подпрограммы. ><При ><этом ><они ><не ><могут ><устанавливать ><значения ><переменных ><в ><других ><продукционных ><правилах. ><Область ><действия ><переменных ><этих ><правил ><ограничена ><от><дельным ><правилом. ><Эта ><синтаксическая ><независимость ><способствует ><инкрементальной ><разработке ><экспертных ><систем ><путем ><последовательного ><добавления, ><удаления ><или ><изме><нения ><знаний ><(правил) ><системы.>
<Управление ><на ><основе ><образцов ><(pattern-directed > <Возможности ><эвристического ><управления ><поиском. ><Несколько ><методов ><эвристи><ческого ><управления ><были ><описаны ><в ><предыдущем ><разделе.> <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><211>
><<Трассировка ><и ><трактовка. ><Модульность ><правил ><и ><итерационный ><характер ><их ><вы><полнения ><облегчают ><контроль ><за ><работой ><продукционной ><системы. ><На ><каждой ><стадии ><цикла ><"распознание-действие" ><рассматривается ><некоторое ><правило. ><Поскольку ><каждое ><правило ><соответствует ><отдельной ><"порции" ><(chunk) ><знаний ><о ><методах ><решения ><задач, ><со><держание ><правила ><должно ><давать ><ясную ><интерпретацию ><текущего ><состояния ><системы ><и ><действия. ><Более ><того, ><цепочка ><правил, ><используемых ><в ><процессе ><решения, ><отражает ><как ><путь ><на ><графе, ><так ><и ><"цепочку ><рассуждений", ><приводящую ><к ><решению ><задачи ><человека-><эксперта. ><В ><главе ><7 ><это ><будет ><описано ><детально. ><Напротив, ><единая ><линия ><управления ><или ><процедура, ><написанная ><на ><традиционном ><языке ><программирования, ><например, > <Независимость ><от ><выбора ><языка. ><Модель ><управления ><продукционной ><системой ><не ><зависит ><от ><представления ><правил ><и ><рабочей ><памяти, ><если ><это ><представление ><поддержива><ет ><сравнение ><с ><образцами. ><Мы ><описали ><продукционные ><правила ><как ><импликации ><исчис><ления ><предикатов ><вида ><А > ><В, ><где ><истинность ><А ><и ><правило ><вывода ><модус ><поненс ><позво><ляют ><сделать ><заключение ><В. ><Существует ><немало ><преимуществ ><применения ><логического ><представления ><знаний ><и ><обоснования ><правил ><вывода, ><однако ><модель ><продукционной ><сис><темы ><может ><работать ><и ><с ><другими ><представлениями.> <Исчисление ><предикатов ><обеспечивает ><преимущество ><логически ><обоснованного ><выво><да, ><однако ><немало ><задач ><требует ><рассуждений, ><которые ><не ><обоснованы ><в ><логическом ><смысле. ><Для ><них ><необходимы ><вероятностные ><рассуждения, ><правила ><умолчания ><и ><недос><товерные ><свидетельства. ><В ><главах ><6, ><7 ><и ><8 ><мы ><обсудим ><альтернативные ><правила ><вывода, ><предоставляющие ><такие ><возможности. ><Независимо ><от ><типа ><используемых ><правил ><вывода, ><продукционная ><система ><обеспечивает ><средства ><поиска ><в ><пространстве ><состояний.>
<Правдоподобная ><модель ><решения ><задачи ><человеком. ><Среди ><первых ><моделей, ><исполь><зующих ><продукционные ><системы, ><были ><модели ><нахождения ><решения ><задач ><человеком ><[Newell ><и >
<Поиск ><на ><основе ><образцов ><(pattern-directed > <5.4. ><Архитектура ><"классной ><доски"> <><Методология ><"классной ><доски" ><(blackboard) ><- ><заключительный ><механизм ><(алгоритм) ><управления, ><представленный ><в ><этой ><главе. ><Если ><необходимо ><исследовать ><состояния ><в ><про><странстве ><логического ><вывода ><некоторым ><детерминированным ><способом, ><применение ><про><дукционных ><систем ><обеспечивает ><значительную ><гибкость, ><позволяя ><одновременно ><предста><вить ><в ><рабочей ><памяти ><множество ><частных ><решений ><и ><выбрать ><следующее ><состояние ><путем ><разрешения ><конфликтов. ><Методология ><"классной ><доски" ><расширяет ><возможности ><продук><ционных ><систем, ><позволяя ><организовать ><рабочую ><память ><в ><виде ><отдельных ><модулей, ><каж><дый ><из ><которых ><соответствует ><подмножеству ><продукционных ><правил. ><"Классная ><доска" ><ин-> <><212>< ><Часть ><И. ><Искусственный ><интеллект ><как ><представление ><и ><поиск> ><<><тегрирует ><отдельные ><наборы ><продукционных ><правил ><и ><координирует ><действия ><многочис><ленных ><решателей ><задач ><в ><пределах ><единой ><глобальной ><структуры.> <Решение ><многих ><задач ><требует ><координации ><ряда ><различных ><типов ><знания. ><На><пример, ><программа ><понимания ><(распознавания) ><речи ><должна ><сначала ><обработать ><фрагменты ><речи, ><представленные ><в ><виде ><оцифрованной ><волны. ><Далее ><в ><процессе ><распознавания ><необходимо ><выделить ><в ><этом ><речевом ><фрагменте ><отдельные ><слова, ><сформировать ><их ><в ><предложения ><и, ><наконец, ><синтезировать ><семантическое ><представ><ление ><полученного ><значения.>
<При ><взаимодействии ><множества ><процессов ><в ><ходе ><решения ><одной ><большой ><задачи ><может ><возникнуть ><немало ><сопутствующих ><проблем. ><Примером ><этого ><служит ><задача ><слияния ><(объединения) ><показаний ><датчиков ><[Lesser ><и > <Архитектура ><"классной ><доски" ><(стратегия ><решения ><сложных ><системных ><задач ><с ><при><влечением ><разнородных ><источников ><знаний, ><взаимодействующих ><через ><общее ><информа><ционное ><поле) ><- ><модель ><управления, ><которая ><успешно ><применяется ><для ><решения ><этой ><и ><других ><задач, ><требующих ><координации ><различных ><процессов ><или ><источников ><знания. ><"Классная ><доска" ><- ><центральная ><глобальная ><база ><данных, ><предназначенная ><для ><связи ><не><зависимых ><асинхронных ><источников ><знаний. ><На ><рис. ><5.12 ><дано ><схематичное ><представле><ние ><архитектуры ><"классной ><доски".>
<На ><рис. ><5.12 ><каждый ><источник ><знаний >
<Подход ><"классной ><доски" ><к ><организации ><большой ><программы ><изначально ><был ><реализован ><в ><системе > <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><213> ><<> <Рис. ><5.12. ><Архитектура ><"классной ><доски ><">
<Архитектура ><"классной ><доски" ><позволила ><скоординировать ><в ><системе >
<слова ><из ><различных ><частей ><данных).>
<Эти ><процессы ><можно ><визуализировать ><в ><виде ><компонентов ><(см. ><рис. ><5.12). ><При ><обра><ботке ><устной ><речи ><форма ><волны ><произнесенного ><сигнала ><рассматривается ><на ><самом ><ниж><нем ><уровне. ><Обработку ><этих ><данных ><выполняют ><определенные ><источники ><знаний. ><Ре><зультаты ><их ><анализа ><переносятся ><на ><доску ><и ><используются ><другими ><процессами. ><Из-за ><неоднозначности ><разговорного ><языка ><на ><каждом ><уровне ><доски ><могут ><присутствовать ><многочисленные ><конкурирующие ><гипотезы. ><Источники ><знаний ><более ><высоких ><уровней ><пытаются ><устранить ><неоднозначности ><конкурирующих ><гипотез.>
<Процесс ><анализа ><в >
<Один ><из > <><214>
<Часть >
><<зультаты ><деятельности ><каждого >
<Когда ><программа >
<Важным ><нововведением ><в > <5.5. ><Резюме ><и ><дополнительная ><литература>
<><В ><главе ><5 ><обсуждалась ><реализация ><стратегий ><поиска, ><описанных ><в ><главах ><3 ><и ><4. ><Таким ><образом, ><ссылки, ><перечисленные ><в ><заключительной ><части ><глав ><3 ><и ><4, ><относятся ><также ><и ><к ><этой ><главе. ><В ><главе ><5 ><представлена ><рекурсия ><как ><важный ><инструмент ><программирования ><поиска ><на ><графе, ><а ><затем ><в ><рекурсивной ><форме ><реализован ><алгоритм ><поиска ><с ><возвратами ><(backtrack >
<Было ><показано, ><что ><продукционная ><система ><является ><естественной ><структурой ><для ><моделирования ><решения ><задач ><и ><реализации ><алгоритмов ><поиска. ><Эта ><глава ><завершается ><примерами ><реализации ><продукционных ><систем, ><осуществляющих ><поиск ><на ><основе ><дан><ных ><и ><от ><цели. ><Действительно ><продукционные ><системы ><всегда ><были ><важной ><парадигмой ><для ><программирования ><задач ><ИИ, ><начиная ><с ><работ ><Ньюэлла ><и ><Саймона ><и ><их ><коллег ><из >
<Конкретные ><реализации ><продукционных ><систем ><описаны ><в ><[Brownston ><и ><др., ><1985] ><и ><[Waterman ><и >
<Ранние ><исследования ><по ><модели ><"классной ><доски" ><описаны ><в ><работах, ><посвященных ><системе > <><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><215>
><<Исследования ><по ><продукционным ><системам, ><планированию ><и ><структурам ><"классной ><доски" ><остаются ><областью ><активных ><исследований ><в ><искусственном ><интеллекте. ><Интере><сующемуся ><читателю ><рекомендуем ><обратиться ><к ><последним ><трудам ><конференций > <5.6. ><Упражнения> <><1.>< ><Алгоритм ><проверки ><вхождения ><из ><подраздела ><5.1.1 ><рекурсивно ><определяет, ><является ><ли ><данный ><элемент ><членом ><списка.> <Составьте ><алгоритм, ><вычисляющий ><число ><элементов ><в ><списке.> <Составьте ><алгоритм, ><вычисляющий ><число ><атомов ><в ><списке.> <Различие ><между ><атомами ><и ><элементами ><состоит ><в ><том, ><что ><элемент ><сам ><может ><быть ><списком. ><(Дополнительная ><информация ><содержится ><в ><разделе ><15.1.)>
<Напишите ><рекурсивный ><алгоритм ><поиска ><в ><ширину ><(с ><использованием ><списков >
><и >
>
<Проследите ><выполнение ><рекурсивного ><алгоритма ><поиска ><в ><глубину ><(без ><использова><ния ><списка >
<В ><древнеиндийской ><чайной ><церемонии ><принимают ><участие ><три ><человека: ><взрослый, ><слуга
><и ><ребенок. ><Они ><выполняют ><четыре ><задачи: ><поддерживают ><огонь, ><подают ><пирожки, ><нали><вают ><чай ><и ><читают ><стихи. ><Эти ><задачи ><перечислены ><в ><порядке ><убывания ><важности. ><В ><нача><ле ><церемонии ><все ><четыре ><задачи ><выполняет ><ребенок. ><Затем ><они ><по ><одной ><переходят ><к ><слу><ге ><и ><взрослому. ><В ><конце ><церемонии ><все ><четыре ><задачи ><выполняет ><взрослый. ><Никто ><не ><мо><жет ><браться ><за ><менее ><важную ><задачу, ><чем ><те, ><которые ><он ><уже ><выполняет. ><Сгенерируйте ><последовательность ><шагов ><передачи ><задач ><от ><ребенка ><к ><взрослому. ><Запишите ><рекурсив><ный ><алгоритм ><выполнения ><последовательности ><этих ><шагов.>
<Используя ><определения ><перемещения ><и ><пути ><для ><задачи ><хода ><конем ><из ><раздела ><5.2,
><проследите ><выполнение ><алгоритма >
<а)path(1,9); ><6)path(1,5); >
<Если ><предикаты >
<Запишите ><на ><языке ><псевдокода ><версию ><алгоритма >
<Используя ><в ><качестве ><модели ><правило ><из ><примера ><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–2023 Все права на тексты книг принадлежат их авторам! При копировании страниц проекта обязательно ставить ссылку: 'Электронная библиотека по философии - http://filosof.historic.ru' |