Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 83
Текст из файла (страница 83)
7.8. Анализ производительности алгоритмов РРЬЪ и Ьги1)еялт при решении трудных задач: график, на котором показами вероятность того, что елучаино сформированное выеназывиние в форме 3-СР(Р е количеством символов и=ба окажется выполнимым, как функции от отношения выражение/символ, ш/п (а); график усредненного времени прогона алгоритмов РР71 и ыа1АВА т применительно к ! 00 выполнимым сформированным случайным обризом высказываниям в форме 3-Саус п4 60, который показывает ниличие узкого диапазона значений шуп вокруг критической точки (б) На рис.
7.8, б показано время прогона алгоритмов Г)рт,), и )(а1)еядт на участке вокруг этой критической точки, где наше внимание ограничивалось только выпол- " Кюкдое выражение содержит три случайно выбранных различных символа, к кюкдоыу из которых применяется отрицание с вероятностью 50%. 322 Часть 11!.
Знания и рассуждения нимыми задачами. Изучение приведенных результатов позволяет сделать три вывода: во-первых, задачи, приближающиеся к критической точке, являются гораздо более трудными по сравнению с другими случайно сформированными задачами; вовторых, даже при решении самых сложных задач алгоритм )ЭРЬЬ является весьма эффективным — он требует выполнения в среднем нескольких тысяч шагов по сравнению со значением количества шагов 2"=10", которое требуется для перебора истинностной таблицы; в-третьих, во всем этом диапазоне характеристик задач алгоритм )(а1)сБ)(т работает намного быстрее, чем алгоритм г)рь).. Безусловно, эти результаты относятся только к случайно сформированным задачам.
Реальные задачи не обязательно имеют такую же структуру, как случайно сформированные задачи [они могут характеризоваться разными значениями относительного количества положительных и отрицательных литералов, разными плотностями соединений межлу выражениями и т.д.). Тем не менее на практике алгоритм Ха1)сЯАТ и подобные ему алгоритмы очень хорошо справляются также с решением реальных задач и часто не уступают самым лучшим алгоритмам специального назначения для этих задач. Такие решатели задач, как С))а[[, легко справляются с залачами, состоящими из тысяч символов и миллионов выражений.
На основании этих набл)одений можно сделать вывод, что некоторые комбинации эвристики с минимальными конфликтами и поведения со случайным блужданием предоставляют универсальную способность нахолнть решения в большинстве ситуаций, в которых требуется комбинаторное формирование рассуждений. 7.7. АГЕНТЫ, ОСНОВАННЫЕ НА ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ В данном разделе соберем воедино все, что было описано до сих пор, для того, чтобы приступить к созданию агентов, действующих с использованием пропозициональной логики. Злесь будут рассматриваться два вила агентов: во-первых, агенты, в которых применяются алгоритмы логического вывола и база знаний, подобные показанному в листинге 7.1 универсальному агенту, основанному на знаниях, и, вовторых, агенты, которые вычисляют значения логических высказываний непосредственно с помощью логических схем.
В этом разделе будет также продемонстрировано функционирование агентов обоих типов в мире вампуса, а также показано, что оба они страдают от серьезных недостатков. Поиск ям и вампусов с помощью логического вывода Начнем с описания агента, который рассуждает логически о том, где находятся ямы, вампусы и безопасные квадраты. Агент начинает свою работу с базы знаний, в которой описаны "законы" мира вампуса. Он знает, что квадрат [1, 1] не содержит яму или вампуса; это означает, что ... и — ы,,, Для каждого квадрата [х, у) агенту известно высказывание с указанием того, как возникает ветерок: (7.1) В<,у е > (Р,у г 3 Р,у-г '' Р цу ч Р -кх) Для каждого квадрата [х, у) агенту известно высказывание с указанием того, как возникает неприятный запах: (7.2) я,х ФФ (И,хз ч Ю,хг ч и цх ч И г,х) 323 Глава 7. Логические агенты Наконец, он знает, что в мире вампуса существует точно один вампус.
Соответствующее высказывание состоит из двух частей. Прежде всего необходимо указать, что имеется самое меньшее один вампус: Ик1 низ ... ' Исз у в)с4 Затем необходимо указать, что существует самое большее один вампус. Один из способов формулировки этого утверждения состоит в том, что при наличии любых двух квадратов один из них обязательно должен быть свободным от вампуса.
При наличии п квадратов мы получаем п (п-1) /2 таких высказываний, которые подобны по форме высказыванию й~з -, у йгк, Таким образом, для мира с размерами 4х4 описание начинается с общего количества !55 высказываний, содержащих 64 различных символа. Программа агента, приведенная в листинге 7.9, сооб[цает в свою базу знаний с помощью операции Те11 о каждом новом восприятии ветерка и неприятного запаха.
(Она также обновляет некоторые обычные программные переменные для слежения за тем, гле находится агент н где он побывал; дополнительная информация об этом приведена ниже.) Затем программа выбирает среди периферийных квадратов (т.е. квадратов, являющихся соседними по отношению к тем, которые уже посетил агент) такой квадрат, которьпй должен быть проверен в следующую очередь.
Агент может доказать, что периферийный квадрат (1, У] безопасен, если из базы знаний следует высказывание (- р,, б — й),, ) . На втором месте по своей привлекательности находится квадрат, который, возможно, является безопасным; таковым является квадрат, применительно к которому агент не может доказать, что в нем имеется яма или вампус, т.е квадрат, для которого из базы знаний не следует высказывание (Р,, Ч и'ь,) .
Листинг 7.9. Агент для мира вампуса, использующий пропознцнонавьную вотяку для определения ям, вампусов н безопасных квадратов. Процедура попсе-ркоыет формнрует задачу поиска, решением которой является последовательность действий, ведущих от [л, у1 до [з, у] в проходящих только через ранее посещенные квадраты Енпсеаоп РБ-ьлларцз-Адепс(регсерс) кесихпв действие асеТоп апросе: регсерс, список результатов восприятия в форме (агапе)з,вгееае, 01з'Сеет! (("Неприятный запах", "Ветерок","Блеск" )) веас1с: КВ, база знаний, первоначально содержащая лищь определения "законов функционирования" мира вампуса х, у, огйепгагдоп, позиция агента (первоначально 1,1) и его ориентация (первоначально язя)зе — смотрит вправо) убнйеес), массив, показывающий, какие квадраты были посещены, первоначально содержащий значения Еауве асс1оп, последнее по времени действие агента, первоначально не определено р1ап, намеченная последовательность действий, первоначально пустая обновить значения х, у, огйепеаезоп, уйвзеес) с учетом действия ассзоп ЕЕ веепсп ЕЬеп Те11(КВ, В„,.) е1ве Те11(КВ, В„,„) ЕЕ Ьгееле Енеп Те11(КВ, В,„) е1ве Те11(КВ, -В,г) 324 Часть 111.
Знания и рассуждения аг д21есег ПЬеп аседоп ( — дгаЬ е1ве 1г р2еп пе пуст ЕЬеп аестоп < — Рор(р2еп) е1ве 1г дпя некоторого периферийного квадрата [2,3] результат Авх(КВ, ( Р,, л )Уп,)) имеет значение Егие ог дпя некоторого периферийного квадрата [1,2) результат Ав)с(кВ, (Р,, у Ип))) имеет значение га2ве енеп оо р2еп < — А*-огарь-эеагсь(яоисе-ргоь1ет([х,у),ог2епгасдоп, [1,2),тав2еес))) аседпп ~- Рор(р2ап) е1ве асстоп <†случайно выбранный ыаг гееигп асс1оп Вычисление логического слелствия в процедуре Аз)с может быть реализовано с использованием любого из методов, описанных выше в этой главе. Очевидно, что алгоритм тт-Впса'1зз (см.
листинг7.3) является практически не применимым, поскольку в нем прихолится выполнять перебор?" строк. Алгоритм [)Рьь (см. листинг 7.7) осушествляет требуемый' логический вывол за несколько миллисекунд восновном благодаря использованию эвристики с распространением единичных выражений. Может также использоваться алгоритм у)а1)сдлт с учетом Обычных предостережений о его неполноте. В рассматриваемых экземплярах мира вампуса неудачи в поиске модели при использовании 1О 000 инверсий неизменно соответствуют невыполнимости, поэтому вероятность ошибок, вызванных неполнотой этого алгоритма, весьма мала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
