Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 30
Текст из файла (страница 30)
Качество решения измеряется с помощью функции стоимости пути, а Ъ.оптимальным решением является такое решение, которое имеет наименьшую стоимость пути среди всех прочих решений. Формулировка задачи В предыдущем разделе была предложена формулировка задачи переезда в Бухарест в терминах начального состояния, функции определения преемника, проверки цели и стоимости пути. Зта формулировка кажется приемлемой, но в ней все же не учитываются слишком многие аспекты реального мира. Сравним простое выбранное нами описание состояния, Дп (Лгас(), с действительным путешествием по стране, в котором состояние мира должно учитывать так много факторов: попутчиков, текущие радиопередачи, вид из окна, наличие поблизости представителей сил правопорядка, расстояние до ближайшей остановки на отдых, состояние дороги, погоду и т.д.
Все эти соображения исключены из наших описаний состояния, поскольку они не имеют отношения к задаче поиска маршрута поездки в Бухарест. Процесс удаления деталей из представления называется ъ. абстрагированием. Кроме абстрагирования описаний состояний, необходимо абстрагировать сами действия.
Любое действие по вождению влечет за собой много следствий. Такие действия не только изменяют местонахождение автомобиля и его пассажиров, но и занимают время, приводят к потреблению топлива, влекут за собой загрязнение окружающей среды и влияют на самого агента (как говорится, путешествия расширяют кругозор). В нашей формулировке учитывается только изменение местонахождения. Кроме того, существует много действий, которые мы вообтце не рассматриваем: включение ралиоприемника, осмотр окрестностей из окна, замедление движения по требованию дорожной полиции и т.д. К тому же, безусловно, действия здесь не задаются на уровне "'поворота рулевого колеса влево на три градуса". Можно ли достичь большей точности определения приемлемого уровня абстракции? Будем считать, что выбранные нами абстрактные состояния и действия соответствуют большим множествам более подробных описаний состояния мира, а также более детализированным последовательностям действий.
Теперь рассмотрим решение абстрактной задачи, например поиска пути от Арада до Бухареста через города Сибиу, Рымнику-Выпча и Питешти. Зто абстрактное решение соответствует 4 Псслеяствия, связанные с применением отрицательных стоимостей, рвссматриввязтся в упр. 3.17. Часть П. Решение проблем 116 большому количеству более подробных инструкций по преодолению пути. Например, можно вести автомобиль между городами Сибиу и Рымнику-Вылча с включенным радиоприемником, а затем выключить его на всю оставшуюся часть путешествия. Абстракция является действительной, если мы можем преобразовать любое абстрактное решение в такое решение, которое подходит для более детально описанного мира; достаточным условием является то, что для любого детализированного состояния, которое представляет собой "пребывание в городе Арад", существует детализированный путь в некоторое состояние, соответствующее "пребыванию в городе Сибиу", и т.д.
Абстракция является полезной, если осуществление каждого из действий, предусмотренных в решении, становится проще цо сравнению с первоначальной задачей; в этом случае действия являются достаточно простыми для того, чтобы они могли быть выполнены без дальнейшего поиска или планирования со стороны обычного агента, занимающегося вождением автомобиля. Поэтому выбор хорошей абстракции сводится к исключению максимально возможного количества подробностей и вместе с тем к сохранению способности оставаться действительной и обеспечению того, чтобы абстрактные действия были легко осуществимыми.
Если бы не было возможности создавать полезные абстракции, то интеллектуальные агенты не могли бы успешно действовать в реальном мире. 3.2. ПРИМЕРЫ ЗАДАЧ Описанный подход к решению задач был применен в очень многих вариантах экспериментальной среды. В этом разделе перечислены некоторые из наиболее известных примеров решения задач, которые подразделяются на два типа — упрощенные и реальные задачи. 'ж Упрощенная задача предназначена для иллюстрации или проверки различных методов решения задач. Ей может быть дано краткое, точное описание. Это означает, что такая задача может легко использоваться разными исследователями для сравнения производительности алгоритмов. Ж Реальной задачей называется такая задача, решение которой действительно требуется людям.
Как правило, такие задачи не имеют единого приемлемого для всех описания, но мы попытаемся показать, как обычно выглядят их формулировки. Упрощенные задачи В качестве первого примера рассмотрим мир пылесоса, впервые представленный в главе 2 (см. рис. 2.2). Деятельность в этом мире можно сформулировать в качестве задачи, как описано ниже. ° Состояния. Агент находится в одном из двух местонахождений, в каждом из которых может присутствовать или не присутствовать мусор.
Поэтому существует 2х2а=8 возможных состояний мира. ° Начальное состояние. В качестве начального состояния может быть назначено любое состояние. ° Функция определения преемника. Эта функция вырабатывает допустимые состояния, которые являются следствием попыток выполнения трех действий (лег с, лй ггпу с и Яыс)г). полное пространство состояний показано на рис.
3.2. 117 Глава 3. Решение проблем посредством поиска Рис.3.2. Пространство состояний длл мира пылесоса. Дуги обозначают действа»: ь=ье к=аддис, Б=яисх ° Проверка цели. Эта проверка сводится к определению того, являются ли чис- тыми все квадраты. ° Стоимость пути. Стоимость каждого этапа равна 1, поэтому стоимость пути представляет собой количество этапов в этом пути. По сравнению с задачей реального мира эта упрошенная задача характеризуется различимыми местонахождениями, возможностью определять наличие мусора, надежной очисткой, а также сохранением достигнутого состояния после очистки.
(В разделе 3.6 некоторые из этих допущений будут исключены.) Необходимо учитывать, что состояние определяется и местонахождением агента, и наличием мусора. В более крупной среде с и местонахождениями имеется п 2" состояний. Ъ. Задача игры в восемь, экземпляр которой показан на рис. 3.3, состоит из доски Зхз с восемью пронумерованными фишками и с одним пустым участком.
Фишка, смежная с пустым участком, может быть передвинута на этот участок. Требуется достичь указанного целевого состояния, подобного тому, которое показано в правой части рисунка. Стандартная формулировка этой задачи приведена ниже. ° Состояния. Описание состояния определяет местонахождение каждой из этих восьми фишек и пустого участка на одном из девяти квадратов. ° Начальное состояние. В качестве начального может быть определено любое состояние. Необходимо отметить, что любая заданная цель может быть достигнута точно из половины возможных начальных состояний (см.
упр. 3.4). ° Функция определения преемника. Эта функция формирует допустимые состояния, которые являются результатом попыток осуществления указанных четырех действий (теоретически возможных ходов ьеГС, дзоте, Ггр или Роьзз). ° Проверка цели. Она позволяет определить, соответствует ли данное состояние целевой конфигурации, показанной на рис. 3.3. (Возможны также другие це- левые конфигурации.) 120 Часть П. Решение проблем мые в данной главе. В главе 4 описана формулировка полного состояния, а в главе 5 приведен простой алгоритм, который позволяет легко решить задачу даже с миллионом ферзей. Реальные задачи Выше уже было показано, как можно определить Ъ.
задачу поиска маршрута в терминах заданных местонахождений и переходов по связям между ними. Алгоритмы поиска маршрута используются в самых разных приложениях, таких как системы маршрутизации в компьютерных сетях, системы планирования военных операций и авиапугешествнй. Обычно процесс определения таких задач является трудоемким. Рассмотрим упрощенный пример задачи планирования авиапутешествий, который задан следующим образом. ° Состояния.
Каждое состояние представлено местонахождением (например, аэропортом) и текущим временем. ° Начальное состояние. Оно задается в условии задачи. ° Функция определения преемника. Эта функция возвращает состояния, которые следуют из выполнения любого полета, указанного в расписании (возможно, с дополнительным указанием класса и места), отправления позже по сравнению с текущим временем с учетом продолжительности переезда внутри самого аэропорта, а также из одного аэропорта в другой.
° Проверка цели. Находимся лн мы в месте назначения к некоторому заранее заданному времени? ° Стоимость пути. Зависит от стоимости билета, времени ожидания, продолжительности полета, таможенных и иммиграционных процедур, комфортности места, времени суток, типа самолета, скидок для постоянных пассажиров и т.д. В коммерческих консультационных системах планирования путешествий используется формулировка задачи такого типа со многими дополнительными усложнениями, которые требуются для учета чрезвычайно запуганных структур определения платы за проезд, применяемых в авиакомпаниях.
Но любой опытный путешественник знает, что не все авиапутешествня проходят согласно плану. Действительно качественная система должна предусматривать планы действий в непредвиденных ситуациях (такие как страховочное резервирование билетов на альтернативные рейсы) в такой степени, которая соответствует стоимости и вероятности нарушения первоначального плана. Ж Задачи планирования обхода тесно связаны с задачами поиска маршрута, но с одним важным исключением. Рассмотрим, например, задачу: "Посетить каждый город, показанный на рис.
3.1, по меньшей мере один раз, начав и окончив путешествие в Бухаресте". Как и при поиске маршрута, действия соответствуют поездкам из одного смежного города в другой. Но пространство состояний является совершенно другим. Каждое состояние должно включать не только текущее местонахождение, но также и множество городов, которые посетил агент. Поэтому первоначальным состоянием должно быть "В Бухаресте; посещен (Бухарест)", а типичным промежуточным состоянием — "В Васлуй; цосещены (Бухарест, Урзичени, Васлуй)", тогда как проверка цели должна предусматривать определение того, находится ли агент в Бухаресте и посетил ли он все 20 городов.
Глава 3. Решение проблем посредством поиска 12! Одной из задач планирования обхода является 'в. задача коммивояжера (Тгаче))пя За!езрегзоп РгоЫет — ТВР), по условию которой каждый город должен быть посещен только один раз. Назначение ее состоит в том, чтобы найти самый короткий путь обхода. Как известно, эта задача является МР-трудной, но на улучшение возможностей алгоритмов ТВР были затрачены колоссальные усилия. Кроме планирования поездок коммивояжеров, эти алгоритмы использовались для решения таких задач, как планирование перемещений автоматических сверл при отработке печатных плат и организация работы средств снабжения в производственных цехах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
