Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 108
Текст из файла (страница 108)
Дело в том, что после достижения цели не было бы достаточно просто возвратить управление из процедуры, подобной Аррепс[, поскольку успех может быть достигнут несколькими способами, и каждый из них должен быть исследован. Параметр сопсупиа ауоп, определяющий продолжение, позволяет решить эту проблему, поскольку он может быть вызван после каждого успешного достижения цели. В приведенном здесь коде процедуры Аррепс], если первый параметр является пустым, то предикат Аррепс) достиг успеха. Затем вызывается продолжение с помощью процедуры са11 (притом что в контрольном стеке нахолятся все подходящие связывания) для того, чтобы определить, что делать дальше. Например, если процедура Аррепс) вызвана на верхнем уровне дерева доказательства, то структура данных сопсзпиасйоп будет использоваться для вывода информации о связывании переменных.
До того как Уоррен выполнил свою работу по внедрению компиляции в системы логического вывода на языке Рго1оя, средства логического программирования работали слишком медленно для того, чтобы они действительно могли найти широкое применение. Компиляторы, разработанные Уорреном и другими специалистами, позволили достичь скоростей обработки кода Рго!оц, способных конкурировать с языком С в самых различных стандартных эталонных тестах 11536). Безусловно, тот факт, что теперь появилась возможность написать планировщик или синтаксиче- 406 Часть 1П. Знания и рассуждения ский анализатор текста на естественном языке, состоящий из нескольких десятков строк на языке Рго1о8, говорит о том, что этот язык становится более подходящим (по сравнению с языком С) для создания прототипов большинства исслеловательских проектов в области искусственного интеллекта небольших масштабов.
Значительное повышение скорости позволяет также обеспечить распараллеливание работы. Организация параллельного выполнения может осуществляться по двум направлениям. Первое направление, получившее название 'в. ИЛИ-параллелизма, исходит из возможности унификации цели со многими различными выражениями в базе знаний. Каждая из этих операций унификации приводит к появлению независимой ветви в пространстве поиска, которая может привести к потенциальному решению, и поиск решений по всем таким ветвям может осуществляться параллельно.
Второе направление, называемое ',з. И-параллелизмом, исходит из возможности параллельного решения кюкдого конъюнкта в теле некоторой импликации. Задача достижения И-параллелизма является более сложной, поскольку для поиска решений всей конъюнкции требуются совместимые связывания для всех переменных. Поэтому при обработке каждой конъюнктивной ветви необходимо обеспечивать обмен данными с другими ветвями для гарантированного достижения глобального решения. Избыточный логический вывод и бесконечные циклы Теперь рассмотрим, в чем состоит ахиллесова пята языка Рго1о8: несогласованность между организацией поиска в глубину и деревьями поиска, которые включают повторяющиеся состояния и бесконечные пути. Рассмотрим следующую логическую программу, позволяющую определить, существует ли путь между двумя точками в ориентированном графе: рвсн(Х,З) : — Зъпк(Х,З). рвсн(Х,З) : — рвсн(Х,Х), Зъпк(у,г).
На рис. 9.5, а приведен простой граф, состоящий из трех узлов, который описан с помощью фактов 15пк(а, Ь) и 1ъп)с(Ь, с) . При использовании этой программы запрос расЬ (а, с) вырабатывает дерево доказательства, показанное на рис. 9.6, а. С другой стороны, если этн два выражения расположены в таком порядке: раен(Х,З) : — рави(Х,т), 1ьпк(у,е).
раСЬ(Х,З) : — тъпх(Х,г). то система Рго!ой следует по бесконечному пути, как показано на рис. 9.6, б. Поэтому система Рго1о8 является неполной, как и программа автоматического доказательства теоремы для определенных выражений (как показано в этом примере, даже применительно к программам, соответствующим формату языка Т)а(а!о8), поскольку для некоторых баз знаний эта система оказывается неспособной доказать высказывания, которые из них следуют. Следует отметить, что алгоритм прямого логического вывода не подвержен этой проблеме: сразу после вывода фактов расЬ (а, Ь), расЬ ( Ь, с ) и расЬ (а, с ) процесс прямого логического вывода останавливается.
Обратный логический вывод с поиском в глубину сталкивается также с проблемами, обусловленными излишними вычислениями. Например, при поиске пути от узла д, к узлу Н, на рис. 9.5, б система Рго!о8 выполняет 877 этапов логического вывода, большинство из которых связано с поиском всех возможных путей к узлам, не позволяющим достичь цели.
Такая проблема аналогична проблеме повторяющихся состоя- 408 Часть П1. Знания и рассуждения эффективные механизмы сохранения н выборки. В табулированном логическом программировании объединяется целенаправленность обратного логического вывода с эффективностью динамического программирования, присущей прямому логическому выводу. Кроме того, эти системы являются полными применительно к программам в формате ?3а(а!о8, а это означает, что программисту приходится меньше беспокоиться о бесконечных циклах. Логическое программирование в ограничениях В приведенном выше описании прямого логического вывода (раздел 9.3) было показано, как можно представить задачи удовлетворения ограничений (Сопигаш( 5а(В?асйоп Ргоб!еш — С5Р) в виде определенных выражений.
Стандартный язык Рго!о8 позволяет решать подобные задачи точно таким же способом, как и алгоритм поиска с возвратами, приведенный в листинге 5.1. Поскольку поиск с возвратами предусматривает полный перебор областей определения переменных, он может применяться только для решения задач С5Р с конечными областями определения. В терминах Рго!о8 это можно перефразировать таким образом, что для любой цели с несвязанными переменными должно существовать конечное количество решений. (Например, цель Жг г (С(, Ва), КОторая опРеделяет, что штаты Квинсленд и Южная Австралия должны быть окрашены в разные цвета, имеет шесть решений, если допускается применение трех цветов.) Задачи С5Р с бесконечными областями определения (например, с целочисленными или вещественными переменными) требуют применения совсем других алгоритмов, таких как распространение пределов или линейное программирование.
Приведенное ниже выражение выполняется успешно, если подставленные в него три числа удовлетворяют неравенству треугольника. Сгьапд1е(Х,У,2) Х>=0, У>=0, 2>=0, Хьх>=2, 7+2>=Х, Хь2>=У. Если системе Рго!о8 передан запрос г г?апд1е ( 3, 4, 5 ), он будет выполнен безукоризненно.
С другой стороны, после передачи запроса сг?апу1е (3, 4, 2) решение не будет найдено, поскольку подцель 2>=0 не может быть обработана системой Рго!о8. Возникающая при этом сложность состоит в том, что переменные в системе Рго!о8 должны находиться только в одном из двух состоянии: несвязанные или связанные с конкретным термом. Связывание переменной с конкретным термом может рассматриваться как крайняя форма ограничения, а именно как ограничение равенства. 'лх Логическое программирование в ограничениях (Сопзггашг ?.о8!с Рго8гашшш8 — С?.Р) позволяет ограничивать, а не связывать переменные. Решением для программы в логике ограничений является наиболее конкретное множество ограничений, налагаемых на переменные запроса, которое может быть определено с помощью базы знаний.
Например, решением запроса сг?апд1е (3, 4, 2) является ограничение 7>=2>=1. Программы в стандартной логике представляют собой частный случай программ С?.Р, в которых ограничения решения должны быть не ограничениями сравнения, а ограничениями равенства, т.е. связываниями. Системы С?.Р включают различные алгоритмы решения задач с ограничениями для таких вариантов ограничений, которые разрешены к использованию в языке.
409 Глава 9. Логический вывод в логике первого порядка Например, система, позволяюшая использовать линейные неравенства с переменными, имеющими вешественные значения, может включать алгоритм линейного программирования для решения этих ограничений. Кроме того, в системах СЕР принят гораздо более гибкий подход к решению запросов стандартного логического программирования.
Например, вместо использования поиска в глубину, слева направо, с возвратами, в них может применяться любой из более эффективных алгоритмов, описанных в главе 5, включая эвристическое упорядочение конъюнктов, обратный переход, определение условий формирования множества отсечения и т.д. Поэтому в системах СЕР сочетаются элементы алгоритмов удовлетворения ограничений, логического программирования и дедуктивных баз данных.
Кроме того, системы СЕР позволяют воспользоваться преимуществами различных методов оптимизации поиска в задачах С5Р, описанных в главе 5, таких как упорядочение переменных и значений, предварительная проверка и интеллектуальный возврат. В частности, разработаны проекты нескольких систем, позволяюших программисту получить больший контроль над порядком поиска для логического вывода.
Например, язык МК5 [539[, [1321[ позволяет программисту-пользователю записывать 'в. метаправила для определения того, какие конъюнкты должны быть опробованы в первую очередь. Например, пользователь может сформулировать правило с указанием, что в первую очередь следует пытаться достичь цели с наименьшим количеством переменных, или оформить характерные для проблемной области правила, касаюшиеся конкретных предикатов. 9.5. Резол[оция Последнее нз трех рассматриваемых в данной главе семейств логических систем основано на резолюции. Как было показано в главе 7, пропозициональная резолюция — это полная процедура логического вывода ддя пропозициональной логики на основе опровержения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
