Skip to main content
Artificial Intelligence

Return to Answer

added 928 characters in body
Source Link
Luca Anzalone
Luca Anzalone
  • 3.2k
  • 3
  • 14

Update: A* is in general more efficient than, BFS and GFS because it employs aare all heuristic functioninformed search strategies meaning that basically provides the remaining distance between the actual node andthey expand the goal nodenodes according to an (indeed, it depends on how you implement it.) Soevaluation function, in this way$f(n) = g(n) + h(n)$, A* tends to explore less nodes in general because it focuses more on the most importantwhere (nearest to$g(n)$ is the goal) ones.

For example, say you perform A* on a grid in which you can explore following 4 directionscost of the path from start node to current node (up, down, left$n$, and right). The heuristics would be the$h(n)$ is a Manhattan distanceheuristic tellingfunction, which provides an estimate of the remaining distancecheapest path to from the actual positioncurrent node $n$ 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 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.

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.

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.

Source Link
Luca Anzalone
Luca Anzalone
  • 3.2k
  • 3
  • 14

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.