Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 36
Текст из файла (страница 36)
Такой тип Ъ. чередования поиска и выполнения является также полезным при решении проблем исследования (см. раздел 4.5) и при ведении игр (см. главу 6). Часть!1. Решение проблем Резюме В настоягцей главе представлены методы, которые могут использоваться агентом для выбора действий в таких вариантах среды, которые являются детерминированными, наблюдаемыми, статическими и полностью известными.
В таких случаях агент может формировать последовательности из действий, позволяюших ему достичь своих целей; такой процесс называется поиском. ° Прежде чем агент сможет приступить к поиску решений, он должен сформулировать цель, а затем использовать эту цель для формулировки задачи. ° Задача состоит из четырех частей: начальное состояние, множество действий, функция проверки цели и функция стоимости пути. Среда задачи представлена пространством состояний, а путь через пространство состояний от начального состояния до целевого состояния представляет собой решение. ° Для решения любой задачи может использоваться единый, общий алгоритм тгее-яеагс)т; конкретные варианты этого алгоритма воплошают различные стратегии.
° Алгоритмы поиска оцениваются на основе полноты, оптимальности, временной и пространственной сложности. Сложность зависит от коэффициент ветвления в пространстве состояний, Ь, и глубины самого поверхностного решения, с3. ° При поиске в ширину для развертывания выбирается самый поверхностный неразвернутый узел в дереве поиска. Этот поиск является полным, оптимальным при единичных стоимостях этапов и характеризуется временной и пространственной сложностью 0( Ь~) . В связи с такой пространственной сложностью в большинстве случаев он становится практически не применимым. Поиск по критерию стоимости аналогичен поиску в ширину, но предусматривает развертывание узла с самой низкой стоимостью пути, д(п) .
Он является полным и оптимальным, если стоимость каждого шага превышает некоторое положительное предельное значение е. ° При поиске в глубину для развертывания выбирается самый глубокий неразвернутый узел в дереве поиска. Этот поиск не является ни полным, ни оптимальным, и характеризуется временной сложностью О()» ) и пространственной сложностью 0(Ьп), где гл — максимальная глубина любого пути в пространстве состояний. ° При поиске с ограничением глубины на поиск в глубину налагается установленный предел глубины.
° При поиске с итеративным углублением вызывается поиск с ограничением глубины и каждый раз устанавливаются увеличивающиеся пределы, до тех пор, пока цель не будет найдена. Этот поиск является полным и оптимальным при единичных стоимостях этапов и характеризуется временной сложностью 0 ( Ь') и пространственной сложностью 0()зс() . ° Двунаправленный поиск способен чрезвычайно уменьшить временную сложность, но он не всегда применим и может потребовать слишком много пространства. 145 Глава 3. Решение проблем посредством поиска ° Если пространство состояний представляет собой граф, а не дерево, то может оказаться целесообразной проверка повторяющихся состояний в дереве поиска. Алгоритм Сгар1з-беагс1з устраняет все дублирующие состояния. ° Если среда является частично наблюдаемой, то агент может применить алгоритмы поиска в пространстве доверительных состояний, или множестве возможных состояний, в которых может находиться агент.
В некоторых случаях может быть сформирована единственная последовательность решения; в других случаях агенту требуется план действий в непредвиденных ситуациях, чтобы иметь возможность справиться со всеми неизвестными обстоятельствами, которые могут возникнуть. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Большинство задач поиска в пространстве состояний, проанализированных в этой главе, имеют длинную историю, отраженную в литературе, и являются менее тривиальными, чем может показаться на первый взгляд. Задача с миссионерами и каннибалами, используемая в упр. 3.9, была подробно проанализирована Амарелем [24].
До него эту задачу ввели в проблематику искусственною интеллекта Саймон и Ньюэлл [1420], и в проблематику исследования операций — Беллман и Дрейфус [96]. Работы наподобие проведенных Ньюэллом и Саймоном наа программами Г.ой]с Т]зеог)зг [1127) и ОРБ [1129) привели к тому, что алгоритмы поиска считались основным оружием в арсенале исследователей искусственного интеллекта 1960-х годов, а сами процессы решения задач стали рассматриваться в качестве канонической проблемы искусственно~о интеллекта. К сожалению, в то время в области автоматизации этапа формулировки задачи было предпринято слишком мало усилий. Более современная трактовка подхода к представлению и абстрагированию задач, включая применение программ искусственного интеллекта, которые (отчасти) сами выполняют эти функции, изложена в книге Кноблока [807].
Задача игры в восемь — это "младшая сестра" задачи игры в пятнадцать, которая была изобретена знаменитым американским разработчиком игр Сэмом Ллойдом [955] в 1870-х годах. Игра в пятнадцать быстро приобрела в Соединенных Штатах огромную популярность, которую можно сравнить лишь с более современной сенсацией, вызванной изобретением кубика Рубика. Она также быстро привлекла внимание математиков [739], [1486). Редакторы Атее!сап эоигпа! оГМайетаг7сз заявили: "Игра в пятнадцать в последние несколько недель занимает все внимание американской публики, и можно с уверенностью сказать, что ею интересуются девять из десяти людей всех полов и возрастов и всех общественных положений.
Но не это побудило нас, редакторов, включить статьи, посвященные этой теме, в наш журнал Атепсап уоигпа! о7' МагйетагГш, а тот факт, что..." (далее следует краткое описание аспектов игры в пятнадцать, представляющих интерес с точки зрения математики).
Исчерпывающий анализ игры в восемь был проведен с помощью компьютера Шофилдом [1363]. Ратнер и Уормут [1268) показали, что общая версия игры (не в пятнадцать, а в пхп-1) принадлежит к классу 1ЧР-полных задач. Задача с восемью ферзями была впервые опубликована анонимно в немецком шахматном журнале осйасй в 1848 году; позднее ее создание приписали некоему 146 Часть П. Решение проблем Максу Беззелю.
Она была повторно опубликована в 1850 году и на этот раз привлекала внимание выдающегося математика Карла Фридриха Гаусса, который попытался перечислить все возможные решения, но нашел только 72. Наук (Хаос]г) опубликовал все 92 решения позднее, в том же 1850 году. Нетто [1121] обобщил эту задачу до п ферзей, а Абрамсон и Янг [2] нашли алгоритм с оценкой О (п). Каждая из реальных задач поиска, перечисленных в данной главе, была предметом значительных усилий исследователей. Методы выбора оптимальных расписаний авиаперелетов по большей части остаются недоступными для общего пользования (закрытыми), но Карл де Маркен (Саг! де Матс]геп) сообщил авторам (в личной беседе), что структуры формирования цен на авиабилеты и связанные с ними ограничения стали настолько сложными, что задача выбора оптимальною авиарейса является формально неразрешимой.
Задача коммивояжера (Тгаче]]п8 Ба1езрегзоп РгоЫегп — ТБР)— это стандартная комбинаторная проблема в теоретических компьютерных науках [898], [899]. Карп [772] доказал, что задача ТБР является ХР-трудной, но для нее были разработаны эффективные методы эвристической аппроксимации [933]. Арора [41] разработал полностью полиномиальную схему аппроксимации для евклидовых вариантов задачи ТБР. Обзор методов компоновки СБИС бьш сделан Шахукаром и Мазумдером [1390], а в журналах по сверхбольшим интегральным микросхемам (СБИС) появилось много статей, посвященных оптимизации компоновки. Задачи робототехнической навигации и сборки обсуждаются в главе 25. Алгоритмы неинформированного поиска для решения задач являются центральной темой классических компьютерных наук [680] и исследования операций [417]; более современные результаты исследований приведены в книгах Део и Панга [390], а также Галло и Паллоттино [5! 6].
Метод поиска в ширину применительно к решению задач с лабиринтами бьш сформулирован Муром [1078]. Метод динамического программирования [96], в котором предусматривается систематическая регистрация решений для всех подзадач с возрастающей длиной, может рассматриваться как форма поиска в ширину в графах.
Алгоритм определения кратчайшего пути между двумя точками, предложенный Дейкстрой [399], является предшественником алгоритма поиска по критерию стоимости. Одна из версий алгоритма поиска с итеративным углублением, предназначенная для эффективного ведения игры в шахматы с контролем времени, была впервые применена Слейтом и Аткином [1429] в программе ведения шахматной игры С]тезз 4.5, но ее применению для поиска кратчайшего пути в графе мы обязаны Корфу [835]. В некоторых случаях может также оказаться очень эффективным двунаправленный поиск, который был предложен Полом [1219], [122Ц.
Частично наблюдаемые и недетерминированные варианты среды не были достаточно глубоко исследованы в этом подходе к решению задач. Некоторые проблемы эффективности при поиске в пространстве доверительных состояний рассматривались Генезеретом и Нурбакшем [538]. Кениг и Симмонс [819] изучали навигацию робота из неизвестной начальной позиции, а Эрдман и Мэйсон [439] исследовали проблему робототехнического манипулирования без датчиков, используя непрерывную форму поиска в пространстве доверительных состояний.
Поиск в условиях непредвиденных ситуаций изучался в этой подобласти планирования (см. главу 12). По большей части в подходе к изучению планирования и осуществления действий с неопределенной информацией используются инструментальные средства теории вероятностей и теории решений (см. главу 17). 147 Глава 3. Решение проблем посредством поиска Книги Нильссона [114! [, [1!42[ являются хорошим общим источником информации о классических алгоритмах поиска.
Исчерпывающий и более современный обзор можно найти в [838[. Статьи о новых алгоритмах поиска (которые, как это ни удивительно, продолжают изобретаться) публикуются в таких журналах, какАгв?)с(а! Йге(1~8елсе. УПРАЖНЕНИЯ 3.!. Самостоятельно сформулируйте определения следующих понятий: состояние, пространство состояний, дерево поиска, поисковый узел, цель, действие, функция определения преемника и коэффициент ветвления. 3.2. Объясните, почему составление формулировки задачи должно осуществляться вслед за составлением формулировки цели. 3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
