Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 39
Текст из файла (страница 39)
В остав- ' В уир. 4.3 предложено показать, что зто семейство включает несколько знакомых читателю неинформированныхалгоритмов. ~ Эвристическая функция Ь (ц) принимает в качестве входного параметра некоторый узел, но зависит только от состояния данного узла. Глава 4. Информированный поиск и исследование пространства состояний 155 шейся части настояшего раздела рассматриваются два способа использования эври- стической информации для управления поиском.
Жадный поиск по первому наилучшему совпадению При Ъ. жадном поиске по первому наилучшему совпадению' предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции; Р(п) =2з(п). Теперь рассмотрим, как используется этот алгоритм при решении задачи поиска маршрута в Румынии на основе эвристической функции определения 'в.
расстояния по прямой (Бтга!8)г( !Зле О!Малое — Я.Г)), для которой принято обозначение 77„,. Если целью является Бухарест, то необходимо знать расстояния по прямой от каждого прочего города до Бухареста, которые приведены в табл. 4.1. Например, 7ззсс(1п(лгал)) ) =366. Обратите внимание на то, что значения )ззсс не могут быть вычислены на основании описания самой задачи.
Кроме того, для использовании этой эвристической функции нужен определенный опыт, позволяюший узнать, каким образом значения )зз„с связаны с действительными дорожными расстояниями, а это означает, что данная функция исходит из практики. Таблипа 4.1. Значения Ьз с — расстояния по пряной до Бухареста Обозначение Название ю- Рассюянне ло Обозначение узла Название города узла рода прямой до Бу- хареста Расстояние по пря- ной до Бухареста 241 234 380 100 Мехадия Нямц Орадя Питешти Рымнику-Выпча 193 Сибиу 253 Тимишоара 329 Урзичеии 80 Васлуй !99 Зеринл 374 Лугож На рис. 4.1 показан процесс применения жадного поиска по первому наилучшему совпадению с использованием значений )ззсо для определения пути от Арада до Бухареста.
Первым узлом, подлежащим развертыванию из узла Атас), является узел БЗЬз и, поскольку город Сибиу находится ближе к Бухаресту, чем города Зеринд или Тимишоара. Следующим узлом, подлежащим развертыванию, является узел Радагаэ, поскольку теперь ближайшим к Бухаресту является город Фэгэраш. Узел ' В первом издании данной книги этот алгоритм поиска именовался просто жадным поиском; в книгах других авторов для него применяется название поиск по первому наилучшему совпадению.
Авторы настоящей книги используют последний термин в более общем смысле, в соответствии с трактовкой Перла !1188!. Лзас1 Вислагеле ссазст а ПссЬееа Етссте Радах ае Озигдзи Нзгаоиа таят ьидсз Арад Бухарест Крайова Дробета Эфорие Фзгзраш Джурлжу Хыршова Яссы 366 0 160 242 161 176 77 151 226 244 Мелос)за в(енес Огаиеа Рзееаез'. Лзюизси(гззсеа ЛзЬзи Тзтзасаса цгезсепз иаезиз гесзпг( Глава 4. Информированный поиск и исследование пространства состояний 157 от города Яссы до города Фэгэраш.
Эта эвристическая функция подсказывает, что в первую очередь должен быть развернут узел города Нямц, дгеатс, поскольку он является ближайшим к узлу радагаз, но этот путь становится тупиковым. Решение состоит в том, чтобы отправиться вначале в город Васлуй (а этот этап, согласно данной эвристической функции, фактически уводит дальше от цели), а затем продолжать движение через Урзичени, Бухарест и, наконец, в Фэгэраш. Поэтому в данном случае применение указанной эвристической функции вызывает развертывание ненужных узлов.
Более того, если не будет предусмотрено обнаружение повторяющихся состояний, то решение так никогда не будет найдено — процедура поиска станет совершать возвратно-поступательные движения между узлами)уеале и 1азз. Жадный поиск по первому наилучшему совпадению напоминает поиск в глубину в том отношении, что этот алгоритм предпочитает на пути к цели постоянно следовать по единственному пути, но возвращается к предыдугдим узлам после попадания в тупик. Данный алгоритм страдает от тех же недостатков, что и алгоритм поиска в глубину: он не является оптимальным, к тому же он — не полный (поскольку способен отправиться по бесконечному пути, да так и не вернуться, чтобы опробовать другие возможности).
При этом в наихудшем случае оценки временной и пространственной сложности составляют о()о ), где в — максимальная глубина пространства поиска. Однако хорошая эвристическая функция позволяет существенно сократить такую сложность. Величина этого сокращения зависит от конкретной задачи и от качества эвристической функции. Поиск А*: минимизация суммарной оценки стоимости решения Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется ~в. поиском А* (читается как "А звездочка").
В нем применяется оценка узлов, объединяющая в себе д(п), стоимость достижения данного узла, и )з (и), стоимость прохождения от данного узла до цели: г(п) = д(п) + п(п) Поскольку функция д(п) позволяет определить стоимость пути от начального узла до узла и, а функция )з (и) определяет оценку стоимости наименее дорогостоящего пути от узла и до цели, то справедлива следующая формула: г"(и) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел и Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением д (п) т)з (п) . Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция )з (и) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.
Анализ оптимальности поиска А' является несложным, если этот метод используется в сочетании с алгоритмом тгее-оеагс)ь В таком случае поиск А' является оптимальным, при условии, что )з (и) представляет собой )ж допустимую эвристическую функцию, т е. при условии, что Л(п) никогда не переоценивает стоимость достижения цели. Допустимые эвристические функции являются по своей сути оптимистическими функциями, поскольку возвращают значения стоимости решения за- 158 Часть П.
Решение проблем дачи, меньшие по сравнению с фактическими значениями стоимости. А поскольку д (и) — точная стоимость достижения узла п, из этого непосредственно следует, что функция Е(п) никогда не переоценивает истинную стоимость достижения решения через узел гс Очевидным примером допустимой эвристической функции является функция определения расстояния по прямой Л,„„которая уже использовалась в данной главе для поиска пути в Бухарест. Расстояние по прямой является допустимым, поскольку кратчайший путь между любыми двумя точками лежит на прямой; это означает, что длина прямого пути по определению не может представлять собой переоценку длины пути. На рис. 4.2 показан процесс поиска А' пути в Бухарест с помощью дерева.
Значения д вычисляются на основании стоимостей этапов, показанных на рис. 3.1, а значения Л,„, приведены в табл. 4.!. Следует, в частности, отметить, что узел цисЛагеаг впервые появляется в периферии на этапе, показанном на рис. 4.2, д, но не выбирается для развертывания, поскольку его Г-стоимость (450) выше, чем стоимость узла равеас5 (417). Иными словами эту ситуацию можно описать так, что может существовать решение, при котором путь проходит через город Питешти со стоимостью, достигающей 417, поэтому алгоритм не останавливается на решении со стоимостью 450. Данный пример может служить общим свидетельством того, что о»- поиск А» с использованием алгоритма ггее-ЯеагсЛ является оптимальным, если функция Л (п) допустима. Предположим, что на периферии поиска появился неоптимальный целевой узел С,, а стоимость оптимального решения равна С*.
В таком случае, поскольку узел С, неоптимален, а Л ( С,) =0 (это выражение справедливо лля любого целевого узла), можно вывести следующую формулу: Е(Е») = д(Е2)» Л(д») = д(О2) > С* Теперь рассмотрим периферийный узел п, который находится в оптимальном пути решения, например узел р5 Сеаг5 в примере, приведенном в предыдущем абзаце. (Если решение существует, то всегда должен быть такой узел.) Если функция Л(п) не переоценивает стоимость завершения этого пути решения, то справедлива следующая формула: Е(п) = д(п)» Л(п) < С* Таким образом, доказано, что Е(п) <С*<Е(С,), поэтому узел С, не развертывается и поиск А* должен вернуть оптимальное решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
