Значения эвристической функции

1.2. Поиск А*

В 1968 году П. Хартом, Н. Нильсоном и Б. Рафаэлем был предложен поиск по наилучшему совпадению — алгоритм А. Впоследствии оказалось, что если эвристическая функция в этом алгоритме обладает некоторыми свойствами, то такой поиск является оптимальным и полным, т.е. позволяет найти кратчайший путь до цели за минимальное число развернутых узлов. Из-за этих хороших качеств этот алгоритм был позже переименован в алгоритм поиска А* (А-звездочка).

В данной стратегии применяется оценка узлов, объединяющая в себе g(n) — точная стоимость достижения узла n и h(n) — эвристическую функцию, т.е. f(n)=g(n)+h(n).

Поскольку функция g(n) позволяет определить стоимость пути от начального узла до узла n, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла n до цели, то справедливо следующее утверждение: f(n) — оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n.

Как оказалось, если h(x) является допустимой эвристической функцией, то алгоритм А* является оптимальным и полным. Функция h(x) называется допустимой эвристической функцией, если она никогда не переоценивает стоимость достижения цели. Допустимая эвристическая функция является оптимистической, поскольку возвращает значение стоимости пути всегда меньшее, либо равное фактическому. Так, кратчайшее расстояние до города по прямой является допустимой эвристической функцией, поскольку никогда не переоценивает реальную (по дороге) стоимость пути до цели. Действительно, расстояние по прямой всегда меньше, чем реальное расстояние по дороге.

На рис.4. приведен процесс применения алгоритма А* для поиска пути из Венеции в Рим.

Первым узлом, подлежащим развертыванию после узла Венеция, является Падуя. Рассчитаем оценку для этого узла: f(n)=g(n)+h(n)=51+387=438 км. В данном случае g(n) — фактическое расстояние между городами Венеция и Падуя = 51 км (см. рис.2), а h(n) — расстояние по прямой между Падуей и Римом = 387 км. Поскольку это единственный соседний город, выбираем его. Теперь развертываем узел Падуя. В этом случае имеется два пути — в Болонью и в Верону (узел Венеция не рассматриваем, так как он уже разворачивался). Поскольку оценка для Болоньи = 424, что меньше 495, то разворачиваем узел Болонья. На следующем шаге получаем три пути — в Римини (оценка 348 км), Модену (371 км) и Флоренцию (340 км). Из этих узлов выбираем узел с наименьшей оценкой, т.е. Флоренция (340 км). Выбираем узел с минимальной оценкой, т.е. Флоренцию. После развертывания узла Флоренция приходим к цели. Таким образом, получили следующий путь: Венеция-Падуя-Болонья-Флоренция-Рим длиной 51+88+119+122+285=665 км. Этот путь также является кратчайшим, поскольку эвристическая функция является оптимальной.

Рис.4. Применение алгоритма А*

Помимо рассмотренных стратегий информированного поиска, существуют более сложные стратегии: рекурсивный поиск по первому наилучшему совпадению (RFBS), поиск А* с ограничением объема памяти (MA*), упрощенный поиск МА* (SMA*). Производительность (т.е. количество развернутых узлов) всех алгоритмов поиска зависит от точности выбранной эвристической функции.

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

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