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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is greedy best-first search.

Improve this answer
$\endgroup$
3
  • $\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, 2019 at 20:40
  • $\begingroup$ @Alexey I completely agree! $\endgroup$
    – David Richerby
    Mar 23, 2019 at 20:40
  • $\begingroup$ I would have called it something like impatient best-first. $\endgroup$
    – Alexey
    Mar 23, 2019 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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