Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 81
Текст из файла (страница 81)
л а„должно быть истинным и в ней же выражение Ь должно быть ложным. Но это противоречит нашему предположению о том, что алгоритм достиг фиксированной точки! Поэтому можно сделать вывод, что множество атомарных высказываний, полученное логическим путем к моменту достижения фиксированной точки, определяет модель первоначальной базы знаний Кв. Более того, любое атомарное высказывание г7, которое следует из базы знаний 7гп, должно быть истинным во всех ее моделях, а также, в частности, в данной модели.
Итак, любое высказывание гг, которое следует из базы знаний, должно быть выведено логически данным алгоритмом. Прямой логический вывод представляет собой пример применения обшего понятия формирования логических рассуждений, 'ю. управляемых данными, т.е. рассуждений, в которых фокус внимания вначале сосредоточен на известных данных. Прямой логический вывод может использоваться в любом агенте для получения заключений на основе поступающих результатов восприятия, часто даже без учета какого- либо конкретного запроса. Например, агент для мира вампуса может сообшать с помощью операции те11 результаты своих восприятий базе знаний с использованием инкрементного алгоритма прямого логического вывода, в котором новые факты могут добавляться к "повестке дня" для инициализации новых процессов логического вывода. У людей формирование рассуждений, управляемых данными, в определенной степени происходит по мере поступления новой информации. Например, находясь дома и услышав, что пошел дождь, человек, который собирался на пикник, может решить, что придется его отменить.
Но такое решение вряд ли будет принято, если он узнает, что оказался мокрым семнадцатый лепесток самой крупной розы в саду его соседа; люди держат процессы прямого логического вывода под тщательным контролем, поскольку в противном случае их просто затопил бы поток логических заключений, не имеюших ничего общего с реальностью.
Алгоритм обратного логического вывода, как указывает само его название, действует в обратном направлении от запроса. Если удается сразу же узнать, что высказывание, содержащееся в запросе ц, является истинным, то не нужно выполнять никакой работы. В противном случае алгоритм находит те импликации в базе знаний, из которых следует гг. Если можно доказать, что все предпосылки одной из этих импликаций являются истинными (с помощью обратного логического вывода), то высказывание гг также является истинным. Будучи применен к запросу а, показанному на рнс. 7.7, этот алгоритм будет проходить вниз по графу до тех пор, пока не достигнет множества известных фактов, которые образуют основу для доказательства.
Разработку подробного алгоритма оставляем читателю в качестве упражнения; как и в случае алгоритма прямого логического вывода, эффективная реализация этого алгоритма выполняет свою работу за линейное время. Обратный логический вывод представляет собой одну из форм 'ж рассуждения, направляемого целями. Такая форма является полезной при получении ответов на конкретные вопросы, наподобие следуюших: "Что теперь мне следует делать?" и "Где же находятся мои ключи?" Зачастую стоимость обратного логического вывода намного меньше по сравнению со стоимостью, линейно зависящей от размера базы знаний, поскольку в этом процессе затрагиваются только факты, непосредственно относящиеся к делу.
Вообше говоря, агент должен разделять работу между процессами прямого и обратного формирования рассуждений, ограничивая прямое формирование рассужде- 316 Часть П1. Знания и рассуждения ний выработкой фактов, которые, по всей вероятности, будут относиться к запросам, подлежащим решению с помощью обратного логического вывода. 7.6. ЭФФЕКТИВНЫЙ ПРОПОЗИЦИОНАЛЬНЫЙ ЛОГИЧЕСКИЙ ВЪ|ВОД В данном разделе рассматриваются два семейства эффективных алгоритмов пропозиционального логического вывода, основанного на проверке по модели: олин подход основан на поиске с возвратами, а другой — на поиске с восхождением к вершине. Указанные алгоритмы входят в состав основного "инструментария" пропозициональной логики.
Этот раздел может быть пропущен при первом чтении настоя ще й главы. Рассматриваемые здесь алгоритмы предназначены для проверки выполнимости. Выше уже отмечалась связь между поиском модели, обеспечивающей выполнимость логического высказывания, и поиском решения задачи удовлетворения ограничения, поэтому, скорее всего, нет ничего удивительного в том, что эти два семейства алгоритмов весьма напоминают алгоритмы поиска с возвратами, описанные в разделе 5.2, и алгоритмы локального поиска, которые представлены в разделе 5.3.
Тем нс менее приведенные здесь алгоритмы являются чрезвычайно важными сами по себе, поскольку в компьютерных науках существует очень много комбинаторных задач, которые можно свести к проверке выполнимости пропозиционального высказывания. Любое усовершенствование алгоритмов проверки выполнимости влечет за собой колоссальные последствия, связанные с повышением нашей способности справляться со всеми сложными задачами в целом. Полный алгоритм поиска с возвратами Первый рассматриваемый здесь алгоритм часто называют ж алгоритмом Дэвиса— Патнем в честь авторов оригинальной статьи, в которой он был опубликован, Мартина Дэвиса и Хилари Патнем |336].
Затем этот алгоритм фактически стал одной из версий, описанных Дэвисом, Логеманом и Лавленлом [335Ь поэтому мы будем называть его )зре). по первым буквам фамилий всех четырех авторов. Алгоритм ))Р).г. принимает на входе некоторое высказывание в конъюнктивной нормальной форме — высказывание, представленное как множество выражений. Как и алгоритмы ВасКсгасКТпд-Беахс)з и тт-епса11в?, он фактически выполняет рекурсивный перебор в глубину всех возможных моделей. Но в этом алгоритме реализованы три описанных ниже усовершенствования, и этим он отличается от простой схемы, применяемой в алгоритме тт-епса11в?.
° Раннее завершение. Алгоритм обнаруживает, должно ли данное высказывание быть истинным или ложным, даже с помощью частично завершенной модели. Выражение является истинным, если истинен любой его литерал, даже притом что для других литералов еще не определены истинностные значения; поэтому об истинности всего высказывания в целом можно судить еще до того, как модель будет составлена полностью. Например, высказывание (л и в) л (А и с) является истинным, если истинен литерал л, незави- Глава 7. Логические агенты 317 симо от значений литералов в и С.
Аналогичным образом, высказывание является ложным, если ложно любое его выражение, а это происходит, если каждый литерал этого выражения является ложным. Опять-таки, такая ситуация может возникнуть задолго до того, как модель будет полностью составлена. Раннее завершение позволяет обойтись без исследования целых поддеревьев в пространстве поиска.
° Эвристика чистого символа. сь Чистым символом называется символ, который всегда появляется с одним и тем же "знаком" во всех выражениях. Например, в трех выражениях (А м -В), (-В ч -С) и (С м А) символ А является чистым, поскольку он появляется только в виде положительных литералов, чистым можно также считать символ в, который появляется только в виде отрицательных литералов, а символ С считается нечистым. Можно легко показать, что если некоторое высказывание имеет модель, то это — модель с чистыми символами, значения которым присвоены так, чтобы их литералы приняли значение Сгие, поскольку при таком условии ни одно выражение не может стать ложным.
Следует отметить, что при определении чистоты символа алгоритм может игнорировать выражения, в отношении которых уже известно, что они истинны в модели, составленной до сих пор. Например, если модель содержит присваивание В=Еа2яе, то выражение ( В м С) уже является истиннылц а символ С становится чистым, поскольку присутствует только В Выражении ( С м А) .
° Эвристика единичного выражения. Единичное выражение было определено ранее как выражение только с одним литералом. В контексте алгоритма РРЬЬ оно также относится к выражениям, в которых в данной модели всем литералам, кроме одного, уже было присвоено значение ~а)эе. Например, если модель содержит присваивание В=Га2яе, то выражение (В м С) становится единичным выражением, поскольку оно эквивалентно выражению (Ра2ве ч — С), или просто — С. Очевидно, для того, чтобы зто выражение приняло истинное значение, литералу Сдолжно быть присвоено значение га2эе. Эвристика единичного выражения предусматривает присваиванне значений всем таким символам до того, как происходит переход к обработке оставшейся части высказывания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
