Зачем алгоритму A-star нужен g(n)?

Question

Алгоритм Дейкстры f(n) = g(n)
и А * является f(n) = g(n) + h(n),

g (n) - стоимость пути от начального узла до n.
h (n) - эвристическая функция, которая оценивает стоимость самого дешевого пути от n до цели.

Нужен ли g (n)? Разве он не может найти кратчайший путь без g (n)?

Зачем A* нужен g (n)?

Answer 1

Нам нужно g(n)

Рассмотрим случай, когда h(n) является 0 для всех узлов на некотором заданном пути к цели (который является совершенно допустимым, то есть допустимым, эвристическим) и ненулевым для всех других узлов.

Если мы пока игнорируем стоимость (g(n)), очевидно, мы выберем узлы на этом пути независимо от того, какова фактическая стоимость, поэтому путь, который мы в итоге получим, может иметь гораздо большую стоимость, чем какой-либо другой путь.

               start
       g(n)=0    O --
               5 |   \ 1
h(n)=0,g(n)=5    O    O h(n)=1,g(n)=1
               5 |   / 1
h(n)=0,g(n)=10   O --
               goal

В приведенном выше примере мы выберем узел слева, а затем цель, так как h(n) = 0 для обоих (что больше, чем h(n) = 1 для узла справа). Это даст нам путь со стоимостью 10где самый дешевый путь включает в себя выбор узла справа, за 2,

Это, пожалуй, крайний пример, но та же идея применима и во многих других случаях. Например, вы могли бы также добавить 10 ко всем значениям в моем примере, и это было бы частью большего графика, и это все равно могло бы привести к неправильному выбору левой части над правой.

Более общий вывод заключается в том, что вы можете выбирать между 2 узлами. n1 а также n2 где h(n1) < h(n2)Таким образом, мы выберем n1, но n2 находится на самом дешевом пути, не n1,

Мы также можем выбрать неправильный узел, если мы включим g(n), Но, в этом случае, для некоторого узла n на пути в том числе n1, f(n) будет больше, чем самый дешевый путь (в худшем случае n будет целью и f(n) будет истинная стоимость, чтобы достичь его через n1, что явно дороже, чем фактический самый дешевый путь), и, следовательно, также больше, чем f(n2) (поскольку эвристика должна недооценивать стоимость), поэтому мы рассмотрим n2 до достижения цели.

Если h(n) были истинная стоимость (а не оценка)

Тогда нам действительно не нужно g(n),

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