Вот пример графика, на котором мы получаем неправильный ответ из-за непоследовательной эвристики. Здесь эвристика показана в скобках рядом с каждым узлом, а стоимость ребра указана рядом с ребрами:
(8)
A
/ \
+1 / \ +3
/ \
B ----- C ----- D
(7) +1 (0) +6 (0)
Здесь оптимальный путь из A в D — это A — B — C — D с общей стоимостью 8. Но давайте посмотрим, что сделает A*:
Начиная с A, есть варианты: перейти от A к B с затратами плюс эвристика 8 или перейти от A к C с затратами плюс эвристика 3. Итак, мы выбираем A – C.
Теперь у нас есть варианты: расширить A-B для стоимости плюс эвристика 8 или расширить C-D для стоимости плюс эвристика 9. Итак, мы выбираем A-B.
Мы уже закрыли C предыдущим путем, поэтому мы не рассматриваем ребро B — C. Вместо этого мы выбираем C — D по цене 9.
В общем, мы нашли путь A - C - D. Упс.
Следующий вопрос заключается в том, как вы могли бы найти пример, подобный этому, и для этого точка зрения, которая, как мне кажется, весьма полезна для размышлений о том, как работает A*, заключается в следующем:
Запуск A* на графе, ребра которого имеют стоимость c(u, v), с использованием эвристической функции h(v) эквивалентен запуску алгоритма Дейкстры на графе, где стоимость ребра (u, v) равна c(u , v) + h(v) - h(u).
Другими словами, вы можете думать о том, что делает A*, как если бы вы запускали алгоритм Дейкстры, настраивая стоимость каждого ребра, добавляя изменение эвристического значения для каждого ребра.
Причина, по которой это полезно, заключается в том, что алгоритм Дейкстры, как известно, будет давать неправильный ответ в тех случаях, когда в графе есть отрицательные ребра. Таким образом, мы можем спросить: когда мы изменим стоимость ребра на c(u, v) + h(v) - h(u), сможем ли мы когда-нибудь получить отрицательную стоимость? Другими словами, что должно произойти, чтобы
c(u, v) + h(v) - h(u) ≥ 0?
При быстрой перестановке можно заметить, что это происходит именно в том случае, если
c(u, v) + h(v) ≥ h(u)
или, что то же самое, uf
h(u) ≤ c(u, v) + h(v).
И эй! Это определение последовательной эвристики.
Это означает, что что-то может пойти не так, если использовать A* с непоследовательной эвристикой точно так же, как что-то может пойти не так с алгоритмом Дейкстры, использующим отрицательные веса ребер. Вы (скорее всего) столкнетесь с проблемой, когда найдете неоптимальный путь к какому-то промежуточному узлу на пути к цели и оттуда получите неверный ответ.
Я закончил тем, что построил приведенный выше график, где A * терпит неудачу, начав с этого графика, где Дейкстра получает неправильный ответ, а затем реконструировал эвристику, которая сделала все затраты на преимущество положительными:
A
+0 / \ -5
/ \
B --- C --- D
-6 +6
Здесь путь, который Дейкстра нашел бы от A до D, — это путь A — C — D со стоимостью 1, а не путь A — B — C — D со стоимостью 0. Это тот же неправильный путь, что и в Пример A* наверху.
person
templatetypedef
schedule
04.08.2018
