0
$\begingroup$

I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance from the source.

In best-first search algorithms, the node to expand next is the most promising one according to some evaluation function (which may take into account the current global knowledge). In the normal A* algorithm, the evaluation function is the sum of the length of the currently know shortest path from the source and the heuristic estimate of the distance to the goal. Is there a standard term for a similar strategy where the evaluation function is just the heuristic distance to the goal?

I was thinking about greedy and hill-climbing, but greedy in this context seems to be just a synonym of best-first, and in what is commonly referred to as hill-climbing, there seems to be either no backtracking, or just one-step backtracking, that is, old unexpanded nodes are discarded at each step.

$\endgroup$
1
$\begingroup$

This is greedy best-first search.

$\endgroup$
  • $\begingroup$ Indeed, it is so called in Artificial Intelligence: A Modern Approach by Russell and Norvig, though this does not look appropriate. (Any "best-first" is greedy by definition, i think.) $\endgroup$ – Alexey Mar 23 at 20:40
  • $\begingroup$ @Alexey I completely agree! $\endgroup$ – David Richerby Mar 23 at 20:40
  • $\begingroup$ I would have called it something like impatient best-first. $\endgroup$ – Alexey Mar 23 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.