Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 82
Текст из файла (страница 82)
Одним из важных следствий из этой эвристики является то, что любая попытка доказать (путем опровержения) истинность литерала, который уже находится в базе знаний, немелленно приводит к успеху (упр. 7.16). Следует также отметить, что присваивание значения одному единичному выражению может привести к созданию еше одного единичного выражения; например, после присваивания символу С значения Га1эе единичным становится выражение (С м А), что влечет за собой присваивание истинного значения символу А. Такое "каскадное" распространение форсированных присваиваний называется Ъ.
распространением единичных выражений. Оно напоминает процесс прямого логического вывода с применением хорновских выражений, а в действительности, если рассматриваемое высказывание в конъюнктивной нормальной форме содержит только хорновские выражения, то алгоритм )ЗРЬЬ по сути свОДится К аЛгоритму прямОгО лОгического вывода (см.
упр. 7.17). 318 Часть 1П. Знания и рассуждения Алгоритм Г)РЬЬ приведен в листинге 7.7. В этом листинге показана самая важная структурная часть алгоритма, которая описывает сам процесс поиска, но не представлены структуры данных, которые необходимо сопровождать для обеспечения эффективности каждого этапа поиска, а также исключены все программистские "хитрости", которые можно было бы ввести для повышения производительности: изучение выражений, эвристики выбора переменных и операции рандомизированного перезапуска.
После включения всех этих усовершенствований алгоритм г)рьь, несмотря на свой почтенный возраст, становится одним из самых быстрых алгоритмов проверки выполнимости, которые когда-либо были разработаны. В частности, реализация С[)а[1 этого алгоритма используется для решения задач проверки качества аппаратного обеспечения с миллионом переменных. Листинг 7.7. Алгоритм ппьь дна проверки выполнимости высказывания в пропознцнонвяьной логике. Принципы работы функций Рйпд-Риге-вутьо1 н Рапп-цпйе-с1апве описаны в тексте; ваа(цая нз ннх возвращает снмвол (плн неопределенное значение), а также нстннностное значение, которое должно быть прпсвоено этому символу.
Еак н влгорптм тт-епеай1вт, этот алгоритм работает с частично составленными моделями йцпоьйоп ПРЬЬ-ЕасйзййаЬ1ет(я) гееигпв значение Сгие или га1яе йприев: я, высказывание в пропозициональной логике с1аияея ь — множество выражений высказывания я, преобразованного в форму представления СИР яутЬо1я ч- список пропозициональных символов в высказывании я гегигп РРЬЬ(с1аияея, яутЬо1я, []) йппоейоп прьь(с1аияея, яутьо1я, тобе1) гееигпв значение стае или Га1яе ьй каждое выражение в множестве с1аияея имеет значение сгие в модели тобе1 еиеп геепгп Сгие йй какое-то выражение в множестве с1аияея имеет значение йа1яе в модели тог)е1 Еиеп гевигп йа1яе Р, га1ие ь- Рйпг)-риге-эутЬо1(яутЬо1я, с1аияея, тес)е1) йй значение Р не является пустым еиеп гегигп прьь (с1аияея,яутЬо1я-р, ехсепг)(Р,га1ие,тобе1) ) Р, га1ие ь- Рйпг)-цп1Ь-О1аияе(с1апяея, тог)е1) йй значение Р не является пустым еиеп геемгп Ррьь(с1аияея,яутьо1я-Р,ехсепд(Р,га1пе,тес)е1)) Р < — Рйгве(яутЬо1я); геяе ь- неве(яутЬо1я) гевмгп Г)РЬЬ(с1аияея, геяг, Ехеепс)(Р, Сгие, тог)е1)) ог ))Рьь(с1аияея, геяе, ехеепс)(Р, йа1яе, тоде1)) Алгоритмы локального поиска До сих пор в данной книге было представлено несколько алгоритмов локального поиска, включая алгоритмы НШ-~11тЫ пд (с.
176) и Езтп1аьес)-Аппеа11пд (с. 18!). Эти алгоритмы могут непосредственно применяться для решения задач проверки выполнимости, при условии, что будет выбрана правильная функция оценки. Поскольку цель состоит в том, чтобы найти присваивание, обеспечиваюшее выполне- Глава 7. Логические агенты 3)9 ние каждого выражения, для этой цели может использоваться любая функция оценки, которая подсчитывает количество невыполненных выражений. Фактически именно этот критерий и применяется в алгоритме м1п-СопШссз для задач СЗР (с.
227). Все эти алгоритмы делают шаги в пространстве полных присваиваний, каждый раз меняя на противоположное (инвертируя) истинностное значение одного символа. Это пространство обычно содержит много локальных минимумов, для выхода из которых требуются различные формы рандомизации. В последние годы было проведено множество экспериментов с тем, чтобы можно было найти приемлемый компромисс между стремлением к "жадному" выбору наилучшего преемника и необходимостью выходить из локальных минимумов с помощью случайного выбора очередного преемника. Одним из простейших и наиболее эффективных алгоритмов, которые были созданы в результате всей этой работы, является алгоритм, получивший название иа1хяйт (листинг 7.8).
при каждой итерации этот алгоритм выбирает одно невыполненное выражение, а в этом выражении выбирает один символ для инвертирования. В данном алгоритме происходит случайным образом переключение между двумя способами выбора символа для инвертирования его истинностного значения: вопервых, этап с "минимизацией конфликтов", в котором минимизируется количество невыполненных выражений в новом состоянии, и, во-вторых, этап "случайного передвижения", в котором один из символов выбирается случайным образом. Листинг 7.8. Алгоритм иа1мяат для проверки выполнимости путем инвертирования значений переменных случайным образом. Существует много версий этого алгоритма Еипов1оа Иа1хядт(с1аияея, р, тах Е11ря) гееигая выполняющую высказывание модель тоне1 или индикатор отказа Еа11ига Епригн; с1аияея, множество выражений в пропозиииональной логике р, вероятность выбора решения сделать ход со "случайным перемещением", которая, как правило, составляет около 0,5 тах Е11ря, количество инверсий, которые разрешено выполнить, прежде чем отказаться от дальнейших попыток тоие1 ь- случайно выбранное присваивание значений егия/еа1яе символам в выражениях Еог Е = 1 Ео тах Е11ря ао ЕЕ в модели тоде1 выполняется множество с1аияея гиен гевпгп тойе1 с1аияе ь- выбранное случайным образом выражение из множества с1аияея, которое имеет значение Еа1яе в модели тойе1 м1ги ргоЬаЪ111ву р инвертировать в модели тоба1 значение случайно выбранного символа из выражения с1аияе е1яе инвертировать значение того символа из выражения с1аияе, который максимизирует количество выполненных выражений в множестве с1аияея геппгп Еа11иге Действительно ли такой алгоритм, как вга1КБлт, способен выполнять производительную работу? Очевидно, что если он возвращает некоторую модель, то входное высказывание в самом деле выполнимо.
А что если он возвращает индикатор неудачи Еа11иге? К сожалению, в этом случае невозможно определить, верно ли, что зго Часть ПЕ Знания и рассуждения высказывание является невыполнимым, или просто этому алгоритму требуется предоставить больше шансов добиться успеха. При этом можно попытаться присвоить параметру с определением максимального количества инверсий гпах Гггря бесконечно большое значение. В данном случае можно легко показать, что алгоритм ха1кялт в конечном итоге вернет какую-то модель (если она существует), при условии, что вероятность этого р>0.
Это связано с тем, что всегда существует последовательность инверсий, ведущая к присваиванию, которое обеспечивает выполнение высказывания, и такая последовательность в конечном итоге вырабатывается в результате случайного выбора этапов перемещения. К сожалению, если параметр шах Г11рв имеет бесконечно большое значение, а высказывание является невыполнимым, данный алгоритм никогда не заканчивает свою работу! Из этого следует, что шгоритмы локального поиска, подобные ьга1)спят, являются наиболее полезными, когда можно действительно рассчитывать на то, что решение существует; например, задачи, которые рассматривались в главах 3 и 5, обычно имеют решения. С другой стороны, локальный поиск не всегда может обнаружить невыполнимость, а именно это требуется, когда задача состоит в том, чтобы определить, следует ли какое-то высказывание из базы знаний.
Например, агент не может надежно использовать локальный поиск для доказательства того, что некоторьш квалрат в мире вампуса безопасен. Вместо этого он может лишь утверждать: "Я размышлял об этом в течение часа, но так и не мог найти хотя бы один из возможных миров, в котором данный квадрат не является безопасным". А поскольку данный алгоритм локального поиска обычно позволяет действительно быстро найти модель, если она существует, то агент, использующий этот алгоритм, должен учитывать, что неудача в попытке найти модель высказывания с помощью данного алгоритма скорее всего свидетельствует о невыполнимости данного высказывания. Безуслов|ю, такой результат — нечто иное, чем доказательство, и агент должен трижды полу- мать, прежде чем рискнуть своей жизнью, основываясь на подобных результатах. Трудные задачи определения выполнимости Теперь рассмотрим, какие показатели производительности демонстрируют алгоритмы ир1.1, и УГа1кьлт на практике.
Нас особенно интересуют трудные задачи, поскольку легкие могут быть решены с помощью любого старого алгоритма. В главе 5 мы ознакомились с некоторыми удивительными открытиями в области решения задач определенного типа. Например, задача с и ферзями (которая когда-то рассматривалась как чрезвычайно сложная) при ее решении с помощью алгоритмов поиска с возвратами оказалась тривиально простой для методов локального поиска, таких как метод с минимальными конфликтами. Это связано с тем, что решения этой задачи распределены в пространстве присваиваний очень плотно и для любого начального присваивания гарантируется, что решение находится недалеко.
Таким образом, задача с п ферзями является простой потому, что она 'в. недостаточно ограниченна. Если речь идет о решении задач проверки выполнимости, представленных в коньюнктивной нормальной форме, то среди них недостаточно ограниченными можно считать такие задачи, которые содержат относительно немного выражений, ограничиваю- Глава 7. Логические агенты 32! щих значения переменных. Например, ниже представлено выработанное случайным об- разом" высказывание в форме 3-С)ь) г с пятью символами и пятью выражениями. ( —,Рч ВчС) л (Вч Ач С) л ( Сч ВчЕ) л (Еч — РчВ) л (В ° Еч С) Моделями этого высказывания являются 16 из 32 возможных вариантов присваивания, поэтому в среднем для поиска модели потребуются только две случайно выбранных гипотезы.
Так где же найти сложные задачи? Можно предположить, что если количество выражений будет увеличено, притом что количество символов останется постоянным, то задача станет более ограниченной и поиск решений окажется более затрулнительным. Допустим, что т — количество выражений, а п — количество символов.
На рис. 7.8, а показана вероятность того, что случайно сформированное высказывание в форме 3-С)х)Г является выполнимым, как функция от отношения "выражение/символ", т(п, при постоянном значении п, равном 50. Как и слеловшю ожидать, при малых значениях т)п эта вероятность близка к 1, а прн больших значениях т!и вероятность близка к О. На кривой вероятности начинается ловольно резкий спад приблизительно после достижения значения т(а=о.3. )3ьлсказыва~шя в форме СХГ, приближаюшиеся к этой тв. критической точке, можно назвать "по пи выполнимыми", или "почти невыполнимыми". Можно ли считать, по именно здесь находятся трудные задачи? 2000 моо )600 й )400 о )200 )ооо й ВОО 600 400 200 о о В О,В 0,6 й 0,4 и В $ 0,2 ) 2 3 4 5 6 7 Отношение "вырвжеиие)символ", т(в 0 ) 2 3 4 5 6 7 Отношение "вырвжение(символ", м(н в) б) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
