Per the wikipedia pageВ алгоритме поиска A *, почему мы добавляем g (n)?
... F (п) = г (п) + Л (п)
где п последний узел на пути, г (п) является стоимость пути от начального узла до n, а h (n) - эвристика, которая оценивает стоимость самого дешевого пути от n до цели.
Почему мы рассматриваем стоимость пути от начального узла до того, где мы находимся сейчас? Я играю с реализацией этого алгоритма для проблемы и использовал очередь приоритетов, и когда я делаю g (n) + h (n), это занимает больше времени, чем просто используя строго h (n). Разве не имеет смысла использовать h (n), поскольку гипотетически, если эвристика точна, вы заботитесь только о том, насколько вы близки к своей цели?
EDIT: На самом деле я только что обнаружил, что моя функция g (n) неправильно вычисляет, но я по-прежнему логически не понимаю, почему g (n) + h (n) будет лучше, чем просто h (n).
В противном случае вы можете получить неправильные результаты. Возьмем, к примеру, совершенно правильную эвристику h (n) = 0. – Henry
Ну, общая стоимость от начала до цели - это стоимость от начала -> n + стоимость от n -> цели. То есть, S -> G = S -> n + n -> G = g (n) + h (n) '. – Kevin
Возможно, вы захотите удалить тег [java], так как это агностик языка. –