Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 107
Текст из файла (страница 107)
Литералы, в которых используются соответствующие функциональные символы, "доказываются" путем выполнения кода, а не осуществления дальнейшего логического вывода. Например, цель "Х ьн 4+3" достигается успешно после связывания переменной Х со значением 7. С другой стороны, попытка достижения цели "5 1в Х+У" оканчивается неудачей, поскольку эти встроенные функции не обеспечивают решения произвольных уравнений'. ° В языке предусмотрены встроенные предикаты, вызывающие при их выполнении побочные эффекты. К ним относятся предикаты ввода-вывода и предикаты аввекс/кескасс для модификации базы знаний.
такие предикаты не имеют аналогов в логике и могут порождать некоторые эффекты, вызываю(цие путаницу, например, если факты подтверждаются (и вводятся в базу знаний) некоторой ветвью дерева доказательства, которая в конечном итоге оканчивается неудачей. 5 Следует отметить, что если бы в некоторой программе Рго)од бьши предусмотрены аксиомы Пеано, то такие цели могли быль решены с помощью логического вывода. 403 Глава 9. Логический вывод в логике первого порядка ° В языке Рго1оя допускается определенная форма отрицания — отрицание как недостижение цели.
Отрицаемая цель пос Р считается доказанной, если системе не удается доказать Р. Таким образом, следующее высказывание: атгое(х) : — пое ореад(х). можно прочитать так: "Любого следует считать живым, если нельзя доказать, что он мертв". ° В языке Рго1оя предусмотрен оператор равенства, "=", но он не обладает всей мощью логического равенства. Цель с оператором равенства достигается успешно, если в ней два терма являются унифицируемыми, а в противном случае попытка ее достижения оканчивается неудачей.
Таким образом, цель Х+У=2 ь3 достигается успешно, после связывания переменной Х со значением 2, а у — со значением 3, а попытка достижения цели дюгпьпдэсах=ечепЫдэсах оканчивается неудачей. (В классической логике последнее равенство может быль или не быть истинным.) Не могут быть подтверждены (введены в базу знаний) какие-либо факты или правила, касающиеся равенства. ° Из алгоритма унификации Рго!оя исключена проверка вхождения.
Это означает, что могут быть сделаны некоторые противоречивые логические выводы; такая проблема возникает редко, за исключением тех ситуаций, когда язык Рго!оя используется для доказательства математических теорем. Решения, принятые при проектировании языка Рго!оя, представляют собой компромисс между стремлениями обеспечить декларативность и вычислительную эффективность (по крайней мере, эффективность в той ее трактовке, которая существовала в период разработки языка Рго!оя).
Мы вернемся к этой теме после рассмотрения того, как реализована система Рго!оя. Эффективная реализация логических программ Подготовка программ Рго1оя к выполнению может осуществляться в двух режимах; интерпретация и компиляция. Интерпретация по существу представляет собой применение алгоритма аког,-вр- хэ)с, приведенного в листинге 9.3, к программе, представленной в виде базы знаний. Предыдущее предложение включает слова "по существу", поскольку в интерпретаторах Рго!оя предусмотрены всевозможные усовершенствования, предназначенные для максимального повышения скорости работы. Здесь рассматриваются только два таких усовершенствования.
Во-первых, вместо формирования списка всех возможных ответов для каждой подцепи перед переходом к следующей подцели интерпретаторы Рго!оя вырабатывают один ответ и "дают обещание" выработать остальные после того, как будет полностью исследован текущий ответ. Такое "обещание" оформляется как 'ъ.
точка выбора (с))о1се ро1п(). После того как в процессе поиска в глубину завершается исследование возможных решений, вытекающих из текущего ответа, и происходит возврат к точке выбора, в этой точке используемые структуры данных дополняются, чтобы в них можно было включить новый ответ для данной подцепи и сформировать новую точку выбора.
Такой подход позволяет экономить и время, и пространство, а также обеспечивает создание очень простого интерфейса для отладки, поскольку постоянно существует лишь единственный путь решения, подлежащий рассмотрению. 404 Часть 1П. Знания и рассуждения Во-вторых, в приведенной в данной главе простой реализации алгоритма РОьцс-Аэ). много времени затрачивается на выработку и компоновку подстановок. В языке Рго!оя подстановки реализуются с использованием логических переменных, позволяющих сохранить в памяти их текущее связывание. В любой момент времени каждая переменная в программе является либо несвязанной, либо связанной с некоторым значением.
Эти переменные и значения, вместе взятые, неявно определяют подстановку для текущей ветви доказательства. Любая попытка продления пути позволяет лишь добавить новые связывания переменных, поскольку стремление ввести другое связывание для уже связанной переменной приводит к неудачному завершению унификации. После того как попытка продления пути поиска оканчивается неудачей, система Рго!од возвращается к предыдущей точке выбора и только после этого получает возможность отменить связывания некоторых переменных. Такая операция отмены выполняется благодаря тому, что данные обо всех переменных, для которых было выполнено связывание, отслеживаются в стеке, называемом 'а.
контрольным стеком (гга!1). по мере того как в функции ггпз йу-Уаг осуществляется связывание каждой новой переменной, эта переменная задвигается в контрольный стек. Если попытка достижения некоторой цели оканчивается неудачей и наступает время возвратиться к предыдущей точке пункта выбора, отменяется связывание каждой из этих переменных по мере их выталкивания из контрольного стека. Но даже в самых эффективных интерпретаторах Рго!оя, в связи с издержками на поиск по индексу, унификацию и формирование стека рекурсивных вызовов, требуется выполнение нескольких тысяч машинных команд в расчете на каждый этап логического вывода. В действительности интерпретатор постоянно ведет себя так, как если бы он никогда до сих пор не видел данную программу; например, ему приходится каждый раз находить выражения, которые согласуются с целью.
С другой стороны, откомпилированная программа Рго1оя представляет собой процедуру логического вывода для конкретного множества выражений, поэтому ей известно, какие выражения согласуются с целью. В процессе компиляции система Рго1од по сути формирует миниатюрную программу автоматического доказательства теоремы ддя каждого отдельного предиката, устраняя тем самым основную часть издержек интерпретации. Эта система позволяет также применять 'оь открытый код для процедуры унификации каждого отдельного вызова, что позволяет избежать необходимости проведения явного анализа структуры терма (подробные сведения об унификации с открытым кодом приведены в [1557)). Наборы команд современных компьютеров плохо согласуются с семантикой Рго!оя, поэтому большинство компиляторов Рго!оя компилирует программу в промежуточный язык, а не непосредственно в машинный язык.
Наиболее широко применяемым промежуточным языком является язык %АМ (%аггеп АЬзггасг МасЫпе— абстрактная машина Уоррена) получивший название в честь Дэвида Г.Д. Уоррена, одного из создателей первого компилятора Рго!оя. Язык %АМ представляет собой абстрактное множество команд, которое подходит для преобразования в него программ Рго!оя и может интерпретироваться или транслироваться в машинный язык. Другие компиляторы транслируют программу Рго!оа в программу на языке высокого уровня, таком как 1.!зр или С, а затем используют компилятор этого языка для трансляции в машинный язык. Например, определение предиката Аррепс) может быть откомпилировано в код, показанный в листинге 9.4. Ниже приведено несколько замечаний, заслуживающих упоминания в этой связи.
405 Глава 9. Логический вывод в логике первого порядка Листинг 9.4. Псевдокод, представляющий собой результат компиляции предиката Аррепе. Функция ыеи-чах1аЬ1е возвращает новую переменную, отличную от всех других переменных, использовавшихся до сих пор. Процедура оа11 ( сопейпнаейоп) продолжает выполнение с заданным продолжением сспедпиаедоп рносеЖхе Аррепс)(ах, у, ах, сспедпиаеуся сга11 ~ — о1ойа1-тта11-Роьпеет() 1х ах = [] аист цп1гу(у, ав) ЕЬеп Са11(сспсдпиаедсп) Певее-тта11(ета11) а г — нем-часьаые(); х +- нем-чагьаые(); в г — нем-чаг1аые() 1х Цпьгу(ах, [а ! х] ) апс Цпьеу(ая, [а ! я1) еьеп Аррепс)(х, у, я, сспс1пиас1сп) ° Выражения предиката Аррепс) преобразуются в процедуру, а этапы логического вывода осуществляются путем вызова этой процедуры, поэтому не приходится выполнять поиск соответствующих выражений в базе знаний.
° Как было описано выше, текущие связывания переменных хранятся в контрольном стеке. На первом этапе выполнения этой процедуры текущее состояние контрольного стека сохраняется в памяти, поэтому оно может быть восстановлено с помощью функции пенес-тха11, если попытка выполнения первого выражения окончится неудачей. Это приводит к отмене всех связываний, сформированных при первом вызове процедуры (гпйту. ° Сложнейшей частью этой программы является использование 'сь продолжений для реализации точек выбора. Продолзюение может рассматриваться как структура данных, в которой упакованы процедура и список параметров, вместе взятые, определяющая, что следует делать дальше, после успешного достижения текущей цели.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
