Answers.Body: <p><strong>Update:</strong> A*, BFS and GFS are all <em>informed</em> search strategies meaning that they expand the nodes according to an <em>evaluation function</em>, <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$g(n)$</span> is the cost of the path from start node to current node <span class="math-container">$n$</span>, and <span class="math-container">$h(n)$</span> is a <em>heuristic</em> function, which provides an estimate of the cheapest path to from current node <span class="math-container">$n$</span> to the goal node.</p>
  <ul>
  <li>GFS expands the nodes using only the heuristic, so <span class="math-container">$f(n)=h(n)$</span>, so it tries to expand the nodes that the heuristic tells to be <em>closest to the goal</em>. As a consequence GFS is neither complete nor optimal.</li>
  </ul>
  <ul>
  <li>Considering BFS, if <span class="math-container">$f(n)=g(n)$</span> then the <em>uniform cost search</em> is recovered, which considers only the cost path <span class="math-container">$g$</span>.</li>
  <li>A* is an instantiation of BFS (thanks @nbro) which can achieve, under certain assumptions, completeness and optimality (if <span class="math-container">$g$</span> and <span class="math-container">$h$</span> are optimal, or at least <span class="math-container">$h$</span> is admissible never overestimating the cost.)</li>
  </ul>
  <hr />
  <p><s>A* is in general more efficient than BFS and GFS because it employs a <em>heuristic function</em> 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.</s></p>
  <p><s>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 <em>Manhattan distance</em> 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.</s></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-30T22:50:10.653Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-30T14:44:23.923Z
Answers.LastActivityDate: 2023-07-31T13:57:34.327Z
Answers.LastEditDate: 2023-07-31T13:57:34.327Z
Answers.UserDisplayName: Luca Anzalone
Body: <p>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.</p>
  <p>So, which one is the correct choice for this question, as all three are based on the heuristic function?</p>
  
Tags: <comparison><search><a-star><best-first-search>
Title: Which search algorithm expands nodes closest to the goal?
UserDisplayName: ndycuong
ThreadText: # Which search algorithm expands nodes closest to the goal?
  
  (Asked by: username_0 on 2023-07-29)
  
  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?
  
  **Tags:** comparison, search, a-star, best-first-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-07-30. Score: 0 | Accepted answer
  
  **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.~~
  
  > **Comments:**
  > **username_2**: 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.  
  
  ---
  
  