Часть 7.

<колли (Фред).>

<2.>< ><(Сэм ><- ><хозяин ><Фреда.)>

<(Сегодня ><суббота).

>

<(Холодно ><в ><субботу.)

><-><(warm(saturday><)><.>

<(Фред ><дрессированный.)

>

<(Спаниели ><- ><хорошие ><собачки, ><а

><колли ><такие ><же ><обученные.)

>

><рошая ><и ><имеет ><хозяина, ><тогда ><она ><находится ><рядом ><с ><хозяином.)>

<[gooddog(X)Amaster(X,Y)Alocation(Y,Z)?location(X,Z)]>

<(Если ><в ><субботу ><тепло, ><то ><Сэм ><на

><ходится ><в ><парке.)

><(day(saturday)Awarm(saturday))?location(sam,park).>

<(Если ><в ><субботу ><не ><тепло, ><то

><Сэм ><находится ><в ><музее.)>

<(day(saturday)^¬(warm(saturday)))?location(sam, >

<Рассмотрим ><этот ><поиск ><детально. ><Это ><пример ><поиска ><от ><цели ><с ><использованием ><ис><числения ><предикатов. ><Он ><иллюстрирует ><роль ><унификации ><(объединения) ><при ><порожде-

137>

<<нии ><области ><поиска. ><Необходимо ><решить ><задачу: ><"Где ><же ><Фред?". ><Эту ><задачу ><можно ><сформулировать ><так: ><найти ><подстановку ><для ><переменной ><если ><она ><существует, ><при ><ко><торой ><или ><место(Фред,Х) ><является ><логическим ><следствием ><началь><ных ><утверждений.>

<Раз ><уж ><необходимо ><определить ><расположение ><Фреда, ><то ><первыми ><будут ><исследованы ><те ><предложения, ><в ><заключении ><которых ><содержится ><выражение ><т><Итак, ><первым ><будет ><рассмотрено ><высказывание ><7. ><Заключение ><этого ><высказывания ><(или ><затем ><объединяется ><с ><выражением ><с ><помощью ><подстановок ><(fred/X,X/Z}). ><Предпосылки ><этого ><правила ><при ><том ><же ><наборе ><подстановок ><составляют ><м-потомки ><основной ><цели.>

<хорошаясобака(Фред)лхозяин(Фред,У)лместо(У,Х).>

<>

<Рис. ><3.23. ><Подграф ><решения, ><показывающий, ><что ><Фред ><в ><музее>

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

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

<Первая ><из ><этих ><или-вершин ><- ><. ><База ><данных ><не ><содержит ><этого ><утвер><ждения, ><поэтому ><решающее ><устройство ><должно ><предположить, ><что ><это ><ложь. ><Другая ><или-><вершина- ><это ><(collie(fred)Atrained(fred)), ><т.е. ><Фред- ><это ><колли ><и ><Фред ><дрессиро><ван. ><Обе ><эти ><предпосылки ><должны ><быть ><истинны. ><Так ><и ><есть ><в ><соответствии ><с ><высказы><ваниями ><1 ><и ><5.

138>

<< ><Итак, ><доказано, ><что ><выражение ><истинно. ><Затем ><решающее ><устройство ><исследует ><вторую ><предпосылку ><высказывания ><7: ><Применяя ><подстановку ><(fred/X) ><к ><выражению ><получим ><а ><затем ><объединим ><это ><выражение ><с ><фактом ><(высказывание ><2). ><Это ><порождает ><>унифицированную< ><(обобщающую) ><замену ><{sam/Y}, ><которая ><также ><обеспечивает ><значение ><третьей ><подцели ><высказывания ><7, ><создавая ><новую ><цель >

<Разрешая ><эту ><цель, ><предположим, ><что ><решающее ><устройство ><проверяет ><правила ><по ><порядку. ><Цель ><вначале ><будет ><унифицирована ><с ><заключением ><>высказывания< ><7. ><Заметим, ><что ><каждый ><раз ><исследуется ><одно ><и ><то ><же ><правило ><с ><различными ><>значениями< ><связывания ><для ><Напомним, ><если ><является ><фиктивной ><переменной ><(глава ><2), ><то ><она ><может ><иметь ><любое ><значение ><(любой ><ряд, ><начинающийся ><с ><прописной ><буквы). ><Поскольку ><диапазон ><действия ><конкретного ><значения ><какой-либо ><переменной ><>ограничивается< ><пределами ><предложения, ><в ><котором ><содержится ><эта ><переменная, ><то ><исчисление ><предикатов ><не ><имеет ><никаких ><глобальных ><переменных. ><Иначе ><эту ><мысль ><можно ><выразить ><так: ><значения ><переменных ><передаются ><другим ><предложениям ><как ><параметры, ><не ><>имеющие< ><фиксированной ><области ><действия ><(памяти). ><Таким ><образом, ><многократные ><>повторения< ><в ><различных ><правилах ><в ><этом ><примере ><указывают ><на ><различные ><формальные ><пара><метры ><(раздел ><12.3).>

<Разрешая ><предпосылки ><правила ><7 ><с ><вновь ><выведенными ><значениями ><связывания, ><>решатель< ><отвергнет ><их, ><потому ><что ><Сэм ><не ><является ><хорошей ><собакой. ><Здесь ><алгоритм ><по><иска ><вернется ><назад ><к ><цели ><и ><проверит ><заключение ><правила ><8. ><Но ><и ><эта ><попытка ><потерпит ><неудачу, ><вызывая ><еще ><один ><возврат ><назад. ><Затем ><последует ><>объединение< ><(унификация) ><с ><заключением ><высказывания ><9 ><,>

<Поскольку ><предпосылки ><предложения ><9 ><подтверждаются ><другими ><высказываниями ><(предложения ><3 ><и ><4), ><то ><заключение ><9 ><истинно. ><Результаты ><унификации ><передаются ><вверх ><по ><дереву ><и ><приводят ><к ><заключительному ><ответу ><$Х ><откуда ><по><лучим >

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

<ПРИМЕР ><3.3.5. ><Финансовый ><советник ><(повторно)>

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

139>

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

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

<Цель ><консультаций ><состоит ><в ><том, ><чтобы ><определить ><наилучший ><способ ><инвестиций. ><Это ><представлено ><выражением ><исчисления ><предикатов ><ЗХ ><где ><- ><целевая ><переменная, ><которую ><мы ><стремимся ><связать. ><Были ><приведены ><три ><правила ><(1,2 ><и ><3) ><которые ><дают ><заключения ><об ><инвестициях, ><поэтому ><запрос ><будет ><унифицирован ><(объединен) ><с ><заключениями ><этих ><правил. ><Если ><для ><первоначального ><исследования ><вы><брать ><правило ><1, ><то ><его ><предпосылка ><становится ><подце><лью, ><т.е. ><дочерней ><вершиной, ><которую ><необходимо ><достичь.>

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

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

<Аналогично ><подцель ><ведет ><к ><запросу ><пользователя, ><затем ><ответ ><(иждивенцев ><2) ><добавляется ><к ><логическому ><описанию. ><Подцель ><ставится ><в ><соответствие ><выражению ><путем ><подстановки ><{2/У}. ><Затем ><алгоритм ><поиска ><оценивает ><истинность ><выражения ><¬><).>

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

140>

<<>

<Рис. ><3.24. ><Поиск, ><осуществляемый ><системой ><финансового ><советника ><на ><графе ><И/ИЛИ>

<ПРИМЕР ><3.3.6. ><Синтаксический ><анализатор ><и ><генератор ><предложений>

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

141

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

<1.>< ><Предложение>< ><- ><это ><именная ><конструкция ><пр ><(noun ><за ><которой ><следует

><глагольная ><конструкция ><(verb >

<Именная ><конструкция ><- ><это ><существительное ><(п).

><пр?п>

<Именная ><конструкция ><пр ><- ><это ><артикль ><за ><которым ><следует ><существительное ><п.

>

<Глагольная ><конструкция ><(verb ><- ><это ><глагол,

>

<Глагольная ><конструкция ><- ><это ><глагол, ><за ><которым ><следует ><именная ><конструкция.

><пр>

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

<а ><- ><артикль.

>

<- ><артикль.

>

<Человек ><- ><существительное.

><т?тап>

<Собака ><- ><существительное.

>

<Любить ><- ><глагол ><(verb).

>

<Кусать ><- ><глагол.

>bites>

<Приведенные ><выше ><правила ><подстановки ><определяют ><граф ><И/ИЛИ ><(рис. ><3.25). ><(предложение) ><- ><корень ><графа. ><Элементам, ><стоящим ><в ><левой ><части ><правил ><подстановки, ><соответствуют ><м-вершины ><этого ><графа. ><Несколько ><правил ><с ><одинаковым ><заключением ><формируют ><вершины ><или. ><Заметим, ><что ><листья, ><или ><узлы-терминалы, ><>графа< ><- ><это ><грамматически ><правильные ><слова ><английского ><языка.>

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

142>

<<>

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

<Рис. ><3.25. ><Граф ><И/ИЛИ ><для ><простой ><грамматики ><из ><примера ><3.3.6. ><Для ><упрощения ><графа ><некоторые ><вершины ><(пр, ><и ><т.д.) ><дублируются>

<Синтаксический ><анализ ><предложения ><"The ><с ><помощью ><дерева ><>грамматического< ><разбора ><приведен ><на ><рис. ><3.26. ><Это ><дерево ><является ><поддеревом ><графа ><И/ИЛИ, ><пока><занного ><на ><рис. ><3.25, ><и ><построено ><в ><процессе ><поиска. ><Алгоритм ><синтаксического ><анализа ><на ><основе ><данных ><осуществляет ><поиск ><путем ><сопоставления ><правых ><частей ><правил ><подстановки ><с ><элементами ><предложения ><и ><пробует ><найти ><одинаковые ><пары. ><Как ><только ><соответствие ><>найдено<, ><часть ><выражения, ><соответствующая ><правой ><части ><правила, ><заменяется ><образцом ><из ><его ><>левой< ><части. ><Это ><продолжается ><до ><тех ><пор, ><пока ><предложение ><не ><будет ><сведено ><к ><символу ><(указывающему ><на ><успешное ><завершение ><синтаксического ><анализа), ><или ><пока ><не ><будут ><исчерпаны ><правила, ><которые ><можно ><применить ><к ><предложению ><(что ><указывает ><на ><не><удачу). ><Проследим ><путь ><синтаксического ><анализа ><предложения ><"The >

<Правило ><7 ><- ><это ><первое ><правило, ><которое ><можно ><применить, ><записывая ><как >

><(артикль). ><Получаем ><предложение: >

<Правило ><7 ><применяется ><на ><следующей ><итерации ><и ><получается >

<Применение ><правила ><8 ><порождает ><предложение ><п.>

<Правило ><3 ><выводит ><предложение ><пр.>

<Правило ><9 ><порождает ><пр.>

<В ><результате ><применения ><правила ><3 ><получим ><пр ><пр.>

<Правило ><11 ><порождает ><пр ><пр.>

<Правило ><5 ><порождает ><пр >

<Правило ><1 ><приводит ><это ><предложение ><к ><заключению ><подтверждая ><кор

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

143>

<<>

<Рис. ><3.26. ><Представление ><предложения ><"The ><в ><виде ><дерева ><>грамматического< ><разбора. ><Заметим, ><что ><оно ><определяет ><поддерево ><графа, ><показанного ><на ><рис. ><3.25>

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

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

<В ><приведенном ><выше ><примере ><мы ><рассмотрели ><очень ><простой ><алгоритм ><поиска ><на ><графе ><И/ИЛИ ><- ><неинформированный ><метод. ><Однако ><для ><этого ><примера ><можно ><>реализовать< ><очень ><интересную ><стратегию ><поиска. ><Метод ><хранения ><текущего ><выражения ><и ><упоря><доченное ><нахождение ><подходящих ><правил- ><примеры ><использования ><продукционной ><системы ><для ><осуществления ><поиска ><и ><основная ><тема ><главы ><5.>

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

<- ><это ><пр, ><за ><которым ><следует ><(правило ><1). ><Заменяя ><пр ><на ><п ><(правило ><2), ><получаем ><п >

<Подстановка ><- ><первого ><значения ><из ><множества ><п ><(правило ><8) ><- ><приводит ><к >

144<><144>

<<<Теперь ><для ><пр ><поиск ><успешен, ><и ><рассматривается ><Правило ><3 ><заменяет ><на ><>получаем< >

<Правило ><10 ><заменяет ><на >

<найдено ><как ><первое ><допустимое ><предложение.>

<Если ><необходимо ><получить ><все ><допустимые ><предложения, ><этот ><поиск ><можно ><>систематично< ><повторять, ><пока ><не ><будут ><испытаны ><все ><варианты, ><т.е. ><пока ><не ><будет ><исследовано ><все ><пространство ><состояний. ><Затем ><можно ><генерировать ><предложения ><"a ><"the ><и ><т.д. ><Всего ><при ><исчерпывающем ><поиске ><(полном ><переборе) ><можно ><по><строить ><84 ><корректных ><предложения. ><Они ><включают ><такие ><семантические ><аномалии, ><как ><"the ><(человек ><кусает ><собаку).>

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

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

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

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

<Графы ><И/ИЛИ ><позволяют ><осуществлять ><поиск ><в ><пространстве ><состояний, ><реализуя ><логические ><рассуждения. ><Стратегии ><поиска, ><описанные ><в ><главе ><3, ><были ><>проиллюстрированы< ><рядом ><примеров, ><в ><том ><числе ><на ><примере ><системы ><финансового ><советника, ><>представленного< ><в ><главе ><2.>

<Основные ><принципы ><поиска ><на ><графах ><обсуждаются ><в ><учебниках ><по ><теории ><алгоритмов, ><в ><том ><числе ><в ><[Cormen, ><1990], ><[Helman ><и ><1986], ><[Sedgewick, ><1983], ><[Horowitz ><и ><1978]. ><Алгоритмы ><поиска ><на ><графах ><И/ИЛИ ><представлены ><также ><в ><главе ><12, ><и ><реализованы ><в ><главах, ><посвященных ><языкам ><и >

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

145>

<<[Winston, ><1992] ><и ><[Charniak ><и ><1985]. ><В ><[Pearl, ><1984] ><представлены ><алгоритмы ><поиска ><и ><заложены ><основы ><материала, ><приведенного ><в ><главе ><4. ><Развитие ><новых ><приемов ><поиска ><на ><графах ><- ><это ><традиционная ><и ><широко ><обсуждаемая ><тема ><на ><ежегодных ><конфе><ренциях ><по ><ИИ.>

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

<><Гамильтонов ><путь- ><это ><путь, ><проходящий ><через ><каждую ><вершину ><графа ><только

><один ><раз. ><Какие ><условия ><необходимы ><для ><существования ><такого ><пути? ><Существует ><ли

><такой ><путь ><на ><карте ><Кенигсберга?>

<Представьте ><в ><виде ><графа ><задачу ><переправы ><человека, ><волка, ><козы ><и ><капусты ><из ><раз

><дела ><14.3 ><(см. ><рис. ><14.1 ><и ><14.2). ><Пусть ><узлы ><представляют ><расположение ><объектов

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

><и ><капуста ><- ><на ><восточном. ><Приведите ><преимущества ><стратегий ><поиска ><в ><ширину ><и ><в

><глубину ><для ><этого ><пространства.>

<Приведите ><пример ><задачи ><о ><коммивояжере, ><в ><которой ><стратегия ><ближайшего ><соседа

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

><стику ><для ><этой ><задачи.>

<Пройдите ><"вручную" ><алгоритм ><с ><возвратами ><для ><графа, ><показанного ><на ><рис. ><3.27. ><Начните

><с ><состояния ><А. ><Проследите ><значения ><списков ><по ><пути ><к ><решению.>

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

><выбору.>

<Определите, ><какой ><алгоритм ><поиска ><(от ><цели ><или ><на ><основе ><данных) ><предпочтитель

><нее ><для ><решения ><каждой ><из ><следующих ><задач. ><Обоснуйте ><ваш ><ответ.>

<Диагностика ><неисправностей ><автомобиля.>

<Вы ><встретили ><даму, ><которая ><утверждает, ><что ><она ><ваша ><дальняя ><родственница ><и ><у

><вас ><есть ><общий ><предок ><по ><имени ><адмирал ><Ушаков. ><Вы ><хотели ><бы ><проверить ><ее

><заявление.>

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

><знает ><имени ><вашего ><общего ><предка, ><но ><знает, ><что ><это ><было ><не ><более ><восьми ><поколе

><ний ><назад. ><Вы ><хотели ><бы ><найти ><этого ><предка ><или ><доказать, ><что ><его ><не ><существовало.>

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

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

><водной ><лодки ><от ><маленькой ><субмарины, ><кита ><от ><стаи ><рыб.>

<Экспертная ><система, ><которая ><поможет ><человеку ><классифицировать ><растения ><по

><виду, ><роду ><и ><т.д.>

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

<Запишите ><алгоритм ><с ><возвратами ><для ><графа ><И/ИЛИ.>

<Решите ><задачу ><о ><хорошей ><собаке ><из ><примера ><3.3.4 ><с ><помощью ><стратегии ><поиска ><на

><основе ><данных.>

<10. ><Приведите ><еще ><один ><пример ><задачи ><поиска ><на ><графе ><И/ИЛИ ><и ><сформируйте ><фраг><мент ><пространства ><поиска.

146>

<<Проследите ><траекторию ><выполнения ><алгоритма ><на ><основе ><данных ><для ><системы

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

<Добавьте ><к ><правилам ><английской ><грамматики, ><описанным ><в ><примере ><3.3.6, ><правила

><для ><прилагательных ><и ><наречий.>

<Добавьте ><к ><описанию ><английской ><грамматики ><из ><примера ><3.3.6 ><правила ><для ><фраз ><с

><предлогами.>

<Добавьте ><правила ><составления ><сложноподчиненных ><предложений ><вида

><и >

<>

<Рис. ><3.27. ><Поиск ><на ><графе

147<<>

<>

<Эвристический ><поиск>

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

<разумной ><последовательности ><действий...>

<- ><Ньюэлл ><и ><Саймон, ><лекция ><по ><случаю ><вручения ><премии ><Тьюринга, ><1976>

<Я ><аккуратный...>

<Аккуратный... ><О, ><да,>

<Аккуратный ><во ><всех ><отношениях...>

<- ><Либер ><и ><Столлер ><(Lieber ><и >

<4.0. ><Введение>

<><В ><[Polya, ><1945] ><эвристика ><определяется ><как ><"изучение ><методов ><и ><правил ><открытий ><и ><изобретений". ><Это ><слово ><имеет ><греческий ><корень, ><глагол ><означает ><"исследовать". ><Когда ><Архимед ><выскочил ><из ><ванны, ><держа ><золотой ><венец, ><он ><закричал ><"Эврика!", ><что ><значит ><"Я ><нашел!". ><В ><пространстве ><состояний ><поиска ><эвристика ><определяется ><как ><набор ><правил ><для ><выбора ><тех ><ветвей ><из ><пространства ><состояний, ><которые ><с ><наибольшей ><>вероятностью< ><приведут ><к ><приемлемому ><решению ><проблемы.>

<Специалисты ><по ><искусственному ><интеллекту ><используют ><эвристику ><в ><двух ><ситуациях.>

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

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

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

<К ><сожалению, ><подобно ><всем ><правилам ><открытия ><и ><изобретения, ><эвристика ><может ><ошибаться. ><Эвристика ><- ><это ><только ><предложение ><следующего ><шага, ><который ><будет ><>сделан< ><на ><пути ><решения ><проблемы. ><Такие ><предположения ><часто ><основываются ><на ><опыте ><или ><интуиции. ><Поскольку ><эвристика ><использует ><такую ><ограниченную ><информацию, ><как ><>описание< ><текущих ><состояний ><в ><списке ><то ><она ><редко ><способна ><предсказать ><дальнейшее ><поведение ><пространства ><состояний. ><Эвристика ><может ><привести ><алгоритм ><поиска ><к ><субоп­><тимальному ><решению ><или ><не ><найти ><решение ><вообще. ><Это ><ограничение ><присуще ><>эвристическому< ><поиску ><и ><не ><может ><быть ><устранено ><"лучшей" ><эвристикой ><или ><более ><>эффективным< ><алгоритмом ><поиска ><[Garey ><и ><1979].>

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

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

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

<Рассмотрим ><игру ><в ><"крестики-нолики" ><(рис. ><5). ><Исчерпывающий ><поиск ><(полный ><>перебор< ><вариантов) ><в ><этой ><игре ><затруднителен, ><но ><возможен. ><На ><каждый ><из ><девяти ><первых ><ходов ><существует ><восемь ><возможных ><ответов. ><На ><которые, ><в ><свою ><очередь, ><можно ><>ответить< ><семью ><различными ><вариантами ><и ><т.д. ><Простой ><анализ ><позволяет ><найти ><общее ><число ><возможных ><состояний, ><которые ><следует ><рассмотреть ><в ><исчерпывающем ><поиске, ><- ><9х8х7х..., ><или ><9!.

150>

<<>

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

<Учитывая ><симметрию ><задачи, ><можно ><уменьшить ><пространство ><поиска. ><Проблема ><множества ><возможных ><конфигураций ><в ><действительности ><сводится ><к ><поиску ><возможных ><симметричных ><конфигураций ><игровой ><доски. ><Таким ><образом, ><существует ><не ><девять, ><а ><только ><три ><возможных ><первых ><хода ><- ><в ><угол, ><на ><верхнюю ><центральную ><клетку ><и ><в ><центр ><решетки. ><Редукции ><на ><втором ><уровне ><и ><далее ><сокращают ><размерность ><пространства ><до ><12x7!, ><как ><показано ><на ><рис. ><4.1. ><Симметрия ><игрового ><пространства, ><подобная ><>рассмотренной< ><выше, ><может ><быть ><описана ><как ><математический ><инвариант, ><и ><если ><она ><существу­><ет ><в ><задаче, ><то ><может ><быть ><успешно ><использована ><для ><значительного ><уменьшения ><про­><странства ><состояний. ><Простая ><эвристика ><может ><свести ><на ><нет ><необходимость ><поиска: ><мы ><можем ><делать ><такие ><ходы ><на ><доске, ><в ><которых ><крестики ><имеют ><наибольшее ><количество ><выигрышных ><линий. ><(Первые ><три ><состояния ><игры ><"крестики-нолики" ><просчитаны ><имен­><но ><таким ><образом, ><рис. ><4.2.) ><Если ><число ><потенциальных ><побед ><равно, ><берется ><первое ><из ><таких ><состояний. ><Затем ><алгоритм ><выбирает ><состояние ><с ><наивысшим ><эвристическим ><>значением<. ><Для ><хода ><берем ><центральную ><клетку. ><Заметим, ><что ><при ><этом ><отбрасываются ><не ><только ><остальные ><возможные ><ходы, ><но ><и ><их ><потомки. ><Отсюда ><следует, ><что ><после ><первого ><хода ><размерность ><пространства ><состояний ><уменьшается ><на ><2/3 ><(рис. ><4.3).>

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

151>

<<>

<Рис. ><4.2. ><Применение ><эвристики ><"наибольшего ><числа ><выигрышных ><линий" ><к ><первым ><потомкам ><в ><игре ><"крестики-нолики">

<>

<Рис. ><4.3. ><Эвристическая ><редукция ><пространства ><состояний ><в ><игре ><"крестики-нолики ><">

<Хотя ><точное ><количество ><возможных ><состояний ><в ><игре ><вычислить ><трудно, ><верхний ><предел ><этого ><количества ><состояний ><может ><быть ><вычислен, ><если ><допустить, ><что ><>максимальное< ><число ><ходов ><в ><игре ><- ><9, ><и ><каждый ><ход ><имеет ><по ><8 ><потомков. ><В ><действительности ><число ><состояний ><будет ><гораздо ><меньше, ><так ><как ><доска ><заполняется, ><и ><с ><каждым ><ходом ><число ><возможных ><ответов ><уменьшается. ><Более ><того, ><оппонент ><делает ><половину ><всех ><>ходов<. ><Несмотря ><на ><это, ><грубый ><верхний ><предел ><- ><9x8, ><или ><72 ><состояния, ><что ><на ><4 ><порядка ><меньше ><величины ><9!.>

<><152>

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

><<В ><следующем ><разделе ><(разделе ><4.1) ><представлен ><алгоритм ><эвристического ><поиска ><и ><продемонстрированы ><его ><характеристики ><с ><использованием ><различных ><эвристик ><для ><>игры< ><в ><"пятнашки" ><над ><8 ><числами ><(назовем ><ее ><8-головоломка). ><В ><разделе ><4.2 ><мы ><обсудим ><такие ><теоретические ><понятия, ><относящиеся ><к ><эвристическому ><поиску, ><как ><допустимость ><и ><монотонность. ><В ><разделе ><4.3 ><рассматривается ><использование ><минимаксного ><подхода ><и ><альфа-бета-усечения ><для ><эвристик ><в ><играх ><со ><многими ><участниками. ><В ><заключительном ><разделе ><проверяется ><общность ><эвристического ><поиска ><и ><еще ><раз ><обосновывается ><его ><>существенная< ><роль ><в ><решении ><задач ><искусственного ><интеллекта.>