Главная arrow Поиск arrow Жадный поиск
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Жадный поиск Печать
При жадном поиске по первому наилучшему совпадению предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции: f(n) = h(n).

Теперь рассмотрим, как используется этот алгоритм при решении задачи поиска маршрута в Румынии на основе эвристической функции определения расстояния по прямой (Straight Line Distance — SLD), для которой принято обозначение hSLD.

Если целью является Бухарест, то необходимо знать расстояния по прямой от каждого прочего города до Бухареста, которые приведены в таблице. Например, hSLD( In {Arad) ) =3 66. Обратите внимание на то, что значения hSLD не могут быть вычислены на основании описания самой задачи. Кроме того, для использовании этой эвристической функции нужен определенный опыт, позволяющий узнать, каким образом значения hSLD связаны с действительными дорожными расстояниями, а это означает, что данная функция исходит из практики.

Обозначение узла
Название города
Расстояние попрямой до Бухареста
Обозначение узла
Название города
Расстояние по прямой до Бухареста
Arad
Арад
366
Mehadia
Мехадия
241
Bucharest
Бухарест
 0Neamt
Нямц
234
Craiova
Крайова
 160OradeaОрадя
380
Drobeta
Дробета
 242Pitesti
Питешти
 100
Eforie
Эфорие
 161RimnicuVilcea
Рымнику-Вылча
 193
Fagaras
Фэгэраш
 176Si biuСибиу
 253
Giurgiи
Джурджу 77Timisoara
Тимишоара
 329
Hirsova
Хыршова
 151Urziceni
Урзичени
 80
Iasi
Яссы
 226VasluiВаслуй
 199
Lugoj
Лугож 244ZerindЗеринд
 374

 

 

 

 

 

 

 

 

 

 

На рисунке показан процесс применения жадного поиска по первому наилучшему совпадению с использованием значений hSLD для определения пути от Арада до Бухареста. Первым узлом, подлежащим развертыванию из узла Arad, является узел Sibiu, поскольку город Сибиу находится ближе к Бухаресту, чем города Зеринд или Тимишоара. Следующим узлом, подлежащим развертыванию, является узел Fagaras, поскольку теперь ближайшим к Бухаресту является город Фэгэраш. Узел Fagaras, в свою очередь, обеспечивает формирование узла Bucharest, который является целевым. Применение в процессе решения данной конкретной задачи алгоритма жадного поиска по первому наилучшему совпадению с использованием функции hSLD позволяет найти решение без развертывания какого-либо узла, не находящегося в пути решения; это означает, что стоимость такого поиска является минимальной. Но само найденное решение не оптимально: путь до Бухареста через города Сибиу и Фэгэраш на 32 километра длиннее, чем путь через города Рымнику-Вылча и Питешти. Это замечание показывает, почему данный алгоритм называется «жадным»: на каждом этапе он пытается подойти к цели как можно ближе (фигурально выражаясь, «захватить как можно больше»).


Этапы жадного поиска пути до Бухареста по первому наилучшему совпадению с использованием эвристической функции hSLD, определяющей расстояние по прямой. Узлы обозначены с помощью их h-значений

Процедура минимизации h(n) восприимчива к фальстартам (при ее использовании иногда приходится отменять начальные этапы). Рассмотрим задачу поиска пути от города Яссы до города Фэгэраш. Эта эвристическая функция подсказывает, что в первую очередь должен быть развернут узел города Нямц, Neamt, поскольку он является ближайшим к узлу Fagaras, но этот путь становится тупиковым.

Решение состоит в том, чтобы отправиться вначале в город Васлуй (а этот этап, согласно данной эвристической функции, фактически уводит дальше от цели), а затем продолжать движение через Урзичени, Бухарест и, наконец, в Фэгэраш. Поэтому в данном случае применение указанной эвристической функции вызывает развертывание ненужных узлов. Более того, если не будет предусмотрено обнаружение повторяющихся состояний, то решение так никогда не будет найдено — процедура поиска станет совершать возвратно-поступательные движения между узлами Neamt и lasi.

Жадный поиск по первому наилучшему совпадению напоминает поиск в глубину в том отношении, что этот алгоритм предпочитает на пути к цели постоянно следовать по единственному пути, но возвращается к предыдущим узлам после попадания в тупик. Данный алгоритм страдает от тех же недостатков, что и алгоритм поиска в глубину: он не является оптимальным, к тому же он — не полный (поскольку способен отправиться по бесконечному пути, да так и не вернуться, чтобы опробовать другие возможности). При этом в наихудшем случае оценки временной и пространственной сложности составляют О (if), где т — максимальная глубина пространства поиска. Однако хорошая эвристическая функция позволяет существенно сократить такую сложность. Величина этого сокращения зависит от конкретной задачи и откачества эвристической функции.