Жадный поиск по первому наилучшему совпадению
При жадном поиске по первому наилучшему совпадению3 предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции: f(n)=h(n).
Теперь рассмотрим, как используется этот алгоритм при решении задачи поиска маршрута в Румынии на основе эвристической функции определения расстояния по прямой (Straight Line Distance — SLD), для которой принято обозначение hSLD. Если целью является Бухарест, то необходимо знать расстояния по прямой от каждого прочего города до Бухареста, которые приведены в табл. 4.1. Например, hSLD(In(Arad) ) =3 66. Обратите внимание на то, что значения hSLD не могут быть вычислены на основании описания самой задачи. Кроме того, для использовании этой эвристической функции нужен определенный опыт, позволяющий узнать, каким образом значения hSLD связаны с действительными дорожными расстояниями, а это означает, что данная функция исходит из практики.
На рис. 4.1 показан процесс применения жадного поиска по первому наилучшему совпадению с использованием значений hSLD для определения пути от Арада до Бухареста. Первым узлом, подлежащим развертыванию из узла Arad, является узел Sibiu, поскольку город Сибиу находится ближе к Бухаресту, чем города Зеринд или Тимишоара. Следующим узлом, подлежащим развертыванию, является узел Fagaras, поскольку теперь ближайшим к Бухаресту является город Фэгэраш. Узел Fagaras, в свою очередь, обеспечивает формирование узла Bucharest, который является целевым. Применение в процессе решения данной конкретной задачи алгоритма жадного поиска по первому наилучшему совпадению с использованием функции hSLD позволяет найти решение без развертывания какого-либо узла, не находящегося в пути решения; это означает, что стоимость такого поиска является минимальной. Но само найденное решение не оптимально: путь до Бухареста через города Сибиу и Фэгэраш на 32 километра длиннее, чем путь через города Рымнику-Вылча и Питешти. Это замечание показывает, почему данный алгоритм называется "жадным": на каждом этапе он пытается подойти к цели как можно ближе (фигурально выражаясь, "захватить как можно больше").
Процедура минимизации h{n) восприимчива к фальстартам (при ее использовании иногда приходится отменять начальные этапы). Рассмотрим задачу поиска пути от города Яссы до города Фэгэраш. Эта эвристическая функция подсказывает, что в первую очередь должен быть развернут узел города Нямц, Neamt, поскольку он является ближайшим к узлу Fagaras, но этот путь становится тупиковым. Решение состоит в том, чтобы отправиться вначале в город Васлуй (а этот этап, согласно данной эвристической функции, фактически уводит дальше от цели), а затем продолжать движение через Урзичени, Бухарест и, наконец, в Фэгэраш. Поэтому в данном случае применение указанной эвристической функции вызывает развертывание ненужных узлов. Более того, если не будет предусмотрено обнаружение повторяющихся состояний, то решение так никогда не будет найдено — процедура поиска станет совершать возвратно-поступательные движения между узлами Neamt и Iasi.
Жадный поиск по первому наилучшему совпадению напоминает поиск в глубину в том отношении, что этот алгоритм предпочитает на пути к цели постоянно следовать по единственному пути, но возвращается к предыдущим узлам после попадания в тупик. Данный алгоритм страдает от тех же недостатков, что и алгоритм поиска в глубину: он не является оптимальным, к тому же он — не полный (поскольку способен отправиться по бесконечному пути, да так и не вернуться, чтобы опробовать другие возможности). При этом в наихудшем случае оценки временной и пространственной сложности составляют О (, где т — максимальная глубина пространства поиска. Однако хорошая эвристическая функция позволяет существенно сократить такую сложность. Величина этого сокращения зависит от конкретной задачи и от качества эвристической функции.