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

Теперь рассмотрим, как используется этот алгоритм при решении задачи поиска маршрута в Румынии на основе эвристической функции определения расстояния по прямой (Straight Line Distance — SLD), для которой принято обозначение. Если целью является Бухарест, то необходимо знать расстояния по прямой от каждого прочего города до Бухареста, которые приведены в табл. 4.1. Например, . Обратите внимание на то, что значения не могут быть вычислены на основании описания самой задачи. Кроме того, для использовании этой эвристической функции нужен определенный опыт, позволяющий узнать, каким образом значения связаны с действительными дорожными расстояниями, а это означает, что данная функция исходит из практики.

Таблица 4.1. Значения— расстояния по прямой до Бухареста

На рис. 4.1 показан процесс применения жадного поиска по первому наилучшему совпадению с использованием значенийдля определения пути от Арада до Бухареста. Первым узлом, подлежащим развертыванию из узла Arad, является узел Sibiu, поскольку город Сибиу находится ближе к Бухаресту, чем города Зеринд или Тимишоара. Следующим узлом, подлежащим развертыванию, является узел Fagaras, поскольку теперь ближайшим к Бухаресту является город Фэгэраш. Узел