Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 106
Текст из файла (страница 106)
Полный процесс определения магических множеств и перезаписи базы знаний является стишком сложным для того, чтобы мы могли заняться в этой главе его описанием, но основная идея состоит в том, что выполняется своего рода "универсальный" обратный логический вывод от цели лля выяснения того, какие связывания переменных нужно будет ограничивать. Поэтому подход с использованием магических множеств может рассматриваться как гибридный между прямым логическим выводом и обратной предварительной обработкой. 9.4.
ОБРАТНЫЙ ЛОГИЧЕСКИЙ ВЫВОД Во втором большом семействе алгоритмов логического вывода используется подход с обратным логическим выводом, представленный в разделе 7.5. Эти алгоритмы действуют в обратном направлении, от цели, проходя по цепочке от одного правила к другому, чтобы найти известные факты, которые поддерживают доказательство. Мы опишем основной алгоритм, а затем покажем, как он используется в логическом программировании, представляюшем собой наиболее широко применяемую форму автоматизированного формирования рассуждений.
В этом разделе будет также показано, что обратный логический вывод имеет некоторые недостатки по сравнению с прямым логическим выводом, и описаны некоторые способы преодоления этих недостатков. Наконец, будет продемонстрирована тесная связь между логическим программированием и задачами удовлетворения ограничений. Алгоритм обратного логического вывода Простой алгоритм обратного логического вывода, гОь-ВС-Аэ)с, приведен в листинге 9.3. Он вызывается со списком целей, содержащим единственный элемент 400 Часть П). Знания и рассуждения (первоначальный запрос) и возврашает множество всех подстановок, которые удовлетворяют этому запросу.
Список целей можно рассматривать как "стек" целей, ожидающих отработки; если все они могут быть выполнены, то текущая ветвь доказательства формируется успешно. В алгоритме берется первая цель из списка и выполняется поиск в базе знаний всех выражений, положительный литерал которых (или голова) унифицируется с целью. При обработке каждого такого выражения создается новый рекурсивный вызов, в котором предпосылки (или тело) выражения добавляются к стеку целей.
Напомним, что факты представляют собой выражения с головой, но без тела, поэтому, если какая-то цель унифицируется с известным фактом, то к стеку не добавляются какие-то подцели, а сама эта цель считается получившей решение. На рис.
9.4 показано дерево доказательства для получения факта Сгзтйпа1 ( й(ее с) из высказываний, приведенных в уравнениях 9.3 — 9.10. (у/М') () () () Рис. 9 4 Дерево доказательства, сформированное путем обратного логического вывода для доказательства того, чело полковник Уэст совершил преступление. Это дерево следует читать в глубину, слева направо. Чтобы доказать факт Сгзщ1па1 аеас), необходимо доказать четыре коньюнкта, находящихся под ним.
Некоторые из них находятся в базе знаний, а другие требуют дальнейшею обратного логического вывода. Связывания для казкдой успешной унификации показаны после соответствующей подцепи. Обратите внимание на, что после успешного достизсения одной подцепи в коньюнкции ее подстановка применяется для последующих подцелей. Таким образом, к тому времени, как алгоритм роьВб-ля)с достигает последнего коньюнкта, первоначально имевшего форму нов с11е (г ), переменная г улке связана с ноно Листинг 9.3. Простой алгоритм обратного логического вывода гвпос1оп ВОЬ-ВС-Аях(КВ, ооа1я, 0) геспгпя множество подстановок апрмсаь КВ, база знаний поа1я, список конъюнктов, образующих запрос (подстановка 0 уже применена) 0, текущая подстановка, первоначально пустая подстановка () 1ооа1 чеагйаЬ1ее: апяыегя, ответы — множество подстановок, первоначально пустое 1г список аоазя пуст еЬеп геевгп (О) о' ь- ввЬяе(0, Р1кяе(поа1я)) 401 Глава 9.
Логический вывод в логике первого порядка гог евон высказывание г Ьп КВ, гпе Яеапс(агс)ьяе-Арагс(г) (р1 л ... л р„ ~ д) и 8' я в Ппьйу(д, д') является выполнимым пег доа1в < — (рп ...,р ]денс(доа1в)] апвыегв < — ВОЬ-ВС-Авк(КВ, пег доа1в, Сотрове(0', О)) ы апвиегв гевал апвиегв В этом алгоритме используется ск композипия подстановок. Здесь Сол1рояе (О,, О,)— это подстановка, результат которой идентичен результату применения каждой подстановки по очереди, следующим образом: ЯиЬвс(сопрове(01,8~),р) = ЯиЬвс(опвпЬвс(ог,р) ) В данном алгоритме текущие связывания переменных, которые хранятся в подстановке О, компонуются со связываниями, возникающими в результате унификации цели с головой выражения, что приводит к получению нового множества текущих связываний для рекурсивного вызова.
Алгоритм обратного логического вывода в том виде, в каком он был приведен в этом разделе, безусловно, представляет собой алгоритм поиска в глубину. Это означает, что его потребности в пространстве линейно зависят от размера доказательства (если на данный момент пренебречь тем, какой объем пространства требуется для накопления решений). Это также означает, что обратный логический вывод (в отличие от прямого логического вывода) страдает от проблем, обусловленных наличием повторяющихся состояний и неполноты. Эти проблемы и некоторые потенциальные решения будут рассматриваться ниже, но вначале покажем, как обратный логический вывод используется в системах логического программирования.
Логическое программирование Логическое программирование — это технология, позволяющая довольно близко приблизиться к воплощению декларативного идеала, описанного в главе 7, согласно которому системы должны конструироваться путем представления знаний на некотором формальном языке, а задачи решаться путем применения процессов логического вывода к этим знаниям. Такой идеал выражен в следующем уравнении Роберта Ковальского: Алгоритм = Логика е Управление Одним из языков логического программирования, намного превосходящим все прочие по своей распространенности, является Ж Рго!ой. Количество его пользователей насчитывает сотни тысяч. Он используется в основном в качестве языка быстрой разработки прототипов, а также служит для решения задач символических манипуляций, таких как написание компиляторов (1536] и синтаксический анализ текстов на естественном языке [1208).
На языке Рго!о8 было написано много экспертных систем для юридических, медицинских, финансовых и других проблемных областей. Программы Рго!ой прелставляют собой множества определенных выражений, записанных в системе обозначений, немного отличающейся от используемой стандартной логики первого порядка. В языке Рго1о8 прописные буквы применяются для обозначения переменных, а строчные — для обозначения констант. Выражения записываются с головой, предшествующей телу; символ: — служит для обозначения 402 Часть И!. Знания и рассуждения импликации, направленной влево, запятые разделяют литералы в теле, а точка обо- значает конец высказывания, как показано ниже.
сктт1па1(Х) : — атекьсап(х), неароп(х), ве11в(х,у,з), Ьовс11е(2) Язык Рго[оя включает "синтаксические упрощения" (зуп[асбс зцяаг) для обозначения списков и арифметических выражений. Например, ниже приведена программа Рго[оя для предиката аррепс] (х, у, 2), которая выполняется успешно, если список 2 представляет собой результат дополнения списка у списком Х. аррепс( ( [], у, у) . еррепс)((А[Х],у,[А]г]) : — вррепс)(Х,у,а).
На естественном языке эти выражения можно прочитать так: во-первых, дополнение списка у пустым списком приводит к получению того же списка у, и, вовторых, [А~ Е] — это результат дополнения списка у списком [А[х], при условии, что Š— это результат дополнения списка У списком Х. Такое определение предиката аррепс] на первый взгляд кажется весьма подобным соответствующему определению на языке [дйр, но фактически является гораздо более мощным.
Например, в систему можно ввести запрос аррепс[(А, В, [1,2] ) — какие два списка можно дополнить один другим, чтобы получить [1, 2 ]? Система возвратит следующие решения: А=[] В=[1,2] А=[1! В=[2] А=[1,21 В=[] Выполнение программ Рте[од осуществляется по принципу обратного логического вывода с поиском в глубину, при котором попытка применения выражений выполняется в том порядке, в каком они записаны в базу знаний. Но некоторые описанные ниже особенности языка Рте[од выходят за рамки стандартного логического вывода. ° В нем предусмотрено множество встроенных функций для выполнения арифметических операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
