0
$\begingroup$

I want to know which search algorithm among A* and Best-First Search and Greedy First Search expands nodes closest to the goal. I have three opinions about A* and Best-First Search and Greedy First Search. As far as I know, Best-First Search is a category of search algorithms that includes A* and Greedy First Search as special cases.

So, which one is the correct choice for this question, as all three are based on the heuristic function?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Update: A*, BFS and GFS are all informed search strategies meaning that they expand the nodes according to an evaluation function, $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from start node to current node $n$, and $h(n)$ is a heuristic function, which provides an estimate of the cheapest path to from current node $n$ to the goal node.

  • GFS expands the nodes using only the heuristic, so $f(n)=h(n)$, so it tries to expand the nodes that the heuristic tells to be closest to the goal. As a consequence GFS is neither complete nor optimal.
  • Considering BFS, if $f(n)=g(n)$ then the uniform cost search is recovered, which considers only the cost path $g$.
  • A* is an instantiation of BFS (thanks @nbro) which can achieve, under certain assumptions, completeness and optimality (if $g$ and $h$ are optimal, or at least $h$ is admissible never overestimating the cost.)

A* is in general more efficient than BFS and GFS because it employs a heuristic function that basically provides the remaining distance between the actual node and the goal node (indeed, it depends on how you implement it.) So, in this way, A* tends to explore less nodes in general because it focuses more on the most important (nearest to the goal) ones.

For example, say you perform A* on a grid in which you can explore following 4 directions (up, down, left, and right). The heuristics would be the Manhattan distance telling the remaining distance from the actual position to the goal. So when this information is combined with the cost of the edge (or weight) it enables A* to be more efficient when exploring nodes.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ A* is a BFS algorithm (note that this is not breadth-first search), so I don't think that "A* is in general more efficient than BFS" makes a lot of sense. Moreover, the heuristic function does not provide the remaining distance between the "actual node" (which should have been the "current node") and the goal node. It merely provides an estimate of this distance. Note also that the heuristic function is not really fixed. You can have many heuristic functions. If these heuristic functions satisfy certain conditions, then A* is optimal. $\endgroup$
    – nbro
    Commented Jul 30, 2023 at 22:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .