Нам нужно 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)), а оттуда мы просто продолжим выбирать узлы на оптимальном пути.