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





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

Часть 7.

<Рис. ><3.18. >< ><Граф >< ><пространства>< ><Рис. ><3.19. >< >< ><Граф >< >< ><И/ИЛИ >< ><для>

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

<исчислении ><высказываний>

<Дуги ><на ><рис. ><3.18 ><соответствуют ><логическим ><импликациям ><(?). ><Утверждения, ><кото><рые ><считаются ><истинными ><(s ><и ><соответствуют ><исходным ><данным ><задачи. ><Логические ><следствия ><из ><данного ><набора ><утверждений ><соответствуют ><достижимым ><узлам. ><Путь ><на ><графе ><отражает ><последовательность ><применения ><правила ><модус ><поненс. ><Например, ><путь ><[s, ><р] ><соответствует ><такому ><ряду ><логических ><выводов.>

<Из ><и >< >< ><следует ><.>

<Из >< ><и>< >< ><р ><следует ><р.>

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

<3.3.2. ><Графы ><И/ИЛИ>

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

<В ><выражениях ><вида ><для ><обеспечения ><истинности ><р ><должны ><быть ><истинны ><как ><, ><так ><и ><. ><В ><выражениях ><вида ><истинность ><или >< ><достаточна ><для ><доказательства ><того, ><что ><р ><- ><истина. ><Поскольку ><импликации ><(?), ><содержащие ><дизъюнктивные ><(v) ><предпосылки, ><могут ><быть ><записаны ><как ><пары ><отдельных ><импликаций, ><это ><выражение ><часто ><записывается ><в ><виде >p, >p. ><Чтобы ><представить ><различные ><отношения ><графи><чески, ><на ><графах ><И/ИЛИ ><различают ><узлы ><и ><(and) ><и ><или ><(or). ><Если ><предпосылки ><>импликаций< ><связаны ><оператором ><л, ><они ><называются ><и-узлами ><графа, ><а ><дуги, ><ведущие ><от ><этих ><узлов, ><соединяются ><кривой. ><На ><рис. ><3.19 ><в ><виде ><графа ><И/ИЛИ ><представлено ><выражение >

<Кривая, ><соединяющая ><дуги ><на ><рис. ><3.19, ><означает, ><что ><для ><доказательства ><р ><должны ><быть ><истинными ><обе ><предпосылки: ><и ><. ><Если ><предпосылки ><соединены ><оператором ><ИЛИ, ><на ><графе ><они ><представляются ><узлами ><или. ><Дуги, ><ведущие ><от ><узлов ><или ><к ><следую->

<><Глава ><3. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний

133

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

<Граф ><И/ИЛИ ><является ><частным ><случаем ><гиперграфа, ><в ><котором ><узлы ><соединены ><не ><отдельными ><дугами, ><а ><множеством ><дуг. ><Приведем ><определение ><гиперграфа.>

<ОПРЕДЕЛЕНИЕ ><ГИПЕРГРАФ>

<Гиперграф ><состоит ><из ><следующих ><элементов. ><- ><множество ><вершин.>

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

<Гипердуги ><также ><называют ><к-коннекторами, ><где ><к ><- ><мощность ><множества ><>порожденных< ><вершин. ><Если ><к= ><1, ><то ><можно ><считать, ><что ><потомок ><является ><вершиной ><ИЛИ. ><Ес><ли ><к> ><1, ><то ><элементы ><множества ><потомков ><являются ><вершинами ><и. ><В ><этом ><случае ><коннек><торы ><изображаются ><в ><виде ><отдельных ><ребер, ><ведущих ><от ><родителя ><к ><каждой ><из ><порож><денных ><вершин ><и ><соединенных ><изогнутой ><линией ><(см. ><рис. ><3.19).>

<>

<Рис. ><3.20. >< >< ><Граф >< ><И/ИЛИ ><выра><жения >

<>

<Рис. ><3.21. ><Граф ><И/ИЛИ ><для ><на><бора ><выражений ><из ><исчисления ><высказываний>

<ПРИМЕР ><3.3.2. ><Поиск ><на ><графе ><И/ИЛИ>

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

<А>

<с>

<а><^b?d>

<а><^><с?е>

<><134><

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

<Истинно ><ли>< >

<Является ><ли ><истиной, ><если ><больше ><не ><истина?>

<Каков ><кратчайший ><путь, ><доказывающий, ><что ><некоторое ><высказывание ><истинно?>

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

><есть ><ложь. ><Что ><это ><значит? ><Что ><необходимо ><знать ><для ><получения ><этого ><заключения?>

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

<В ><примере, ><показанном ><на ><рис. ><3.21, ><для ><определения ><истинности ><с ><помощью ><стратегии ><поиска ><от ><цели ><{goal-directed ><сначала ><доказывается ><истинность ><а ><и ><е. ><Истинность, ><а ><очевидна, ><а ><выражение ><е ><истинно, ><если ><истинны ><и ><с ><и ><а, ><что ><да><но ><по ><условию ><задачи. ><Решающее ><устройство ><прослеживает ><все ><дуги, ><ведущие ><к ><ис><тинным ><предложениям. ><Затем ><истинные ><значения ><передаются ><и-узлу ><для ><>доказательства< ><истинности >

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

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

<3.3.3. ><Примеры ><и ><приложения>

<ПРИМЕР ><3.3.3. ><Система >

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

<><Глава ><3. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний

135

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

<>

<Рис. ><3.22. >< >< ><Фрагмент ><пространства ><состояний ><графа ><И/ИЛИ ><для ><системы ><интегрирования ><[Nilsson, ><1971]>

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

136<><136

<<<ПРИМЕР ><3.3.4. ><Поиск ><от ><цели ><на ><графе ><И/ИЛИ>

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

<1.>< ><(Фред ><- ><это ><колли.)>

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

<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, >

<Цель- ><это ><выражение ><ЗХ ><или ><ЭХ ><место(Фред,Х), ><означающее ><"Where ><(Где ><же ><Фред?). ><Алгоритм ><с ><возвратами ><исследует ><альтернативные ><зна><чения ><этой ><порожденной ><цели: ><"if ><(Если ><Фред ><хороший ><пес, ><и ><Фред ><имеет ><хо><зяина, ><и ><хозяин ><Фреда ><находится ><в ><некотором ><месте, ><то ><Фред ><находится ><в ><том ><же ><месте.) ><Исследуются ><предпосылки ><этого ><правила: ><что ><значит ><"good ><(хороший ><пес) ><и ><т.д. ><Таким ><образом ><создается ><граф ><И/ИЛИ, ><показанный ><на ><рис. ><3.23.>

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

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, ><приводя ><к ><новым ><подцелям>

<Продолжая ><поиск, ><доказываем, ><что ><истинно ><как ><заклю><чение ><правила ><4, ><следует ><из ><правила ><6. ><Дальнейшие ><детали ><поиска ><оставлены ><на ><рассмотрение ><читателю, ><а ><исследуемый ><граф ><И/ИЛИ ><в ><его ><окончательном ><виде ><приведен ><на ><рис. ><3.24.

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 ><рассматривается ><использование ><минимаксного ><подхода ><и ><альфа-бета-усечения ><для ><эвристик ><в ><играх ><со ><многими ><участниками. ><В ><заключительном ><разделе ><проверяется ><общность ><эвристического ><поиска ><и ><еще ><раз ><обосновывается ><его ><>существенная< ><роль ><в ><решении ><задач ><искусственного ><интеллекта.>

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



ПОИСК:




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

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