Жадный поиск по первому наилучшему совпадению

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

Рассмотрим, как используется этот алгоритм при решении задачи поиска маршрута из Венеции в Рим (рис.1). В качестве эвристической функции будем использовать расстояние по прямой из любого города до Рима (табл.1). Эта задача сводится к задаче поиска в пространстве состояний. На рис.2 представлено пространство состояний этой задачи в виде графа. Вес дуг определяет длину дороги между городами (не по прямой).

Рис.1. Задача поиска маршрута из Венеции в Рим

Таблица 1

Дата добавления: 2015-07-26; просмотров: 347; Нарушение авторских прав

Мы поможем в написании ваших работ!