Answers.Body: <p>According to the book <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a> (3rd edition), by Stuart Russel and Peter Norvig, specifically, section <strong>3.5.1 Greedy best-first search</strong> (p. 92)</p>
  
  <blockquote>
    <p>Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, <span class="math-container">$f(n) = h(n)$</span>.</p>
  </blockquote>
  
  <p>In this same section, the authors give an example that shows that greedy best-first search is neither optimal nor complete.</p>
  
  <p>In section <strong>3.5.2 A* search: Minimizing the total estimated solution cost</strong> of the same book (p. 93), it states</p>
  
  <blockquote>
    <p>A* search evaluates nodes by combining <span class="math-container">$g(n)$</span>, the cost to reach the node, and <span class="math-container">$h(n)$</span>, the cost to get from the node to the goal <span class="math-container">$$f(n) = g(n) + h(n).$$</span> </p>
    
    <p>Since <span class="math-container">$g(n)$</span> gives the path cost from the start node to node <span class="math-container">$n$</span>, and <span class="math-container">$h(n)$</span> is the estimated cost of the cheapest path from <span class="math-container">$n$</span> to the goal, we have <span class="math-container">$f(n)$</span> = estimated cost of the cheapest solution through <span class="math-container">$n$</span>.</p>
    
    <p>Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of <span class="math-container">$g(n) + h(n)$</span>. It turns out that this strategy is more than just reasonable: provided that the heuristic function <span class="math-container">$h(n)$</span> satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to uniform-cost search except that A* uses <span class="math-container">$g + h$</span> instead of <span class="math-container">$g$</span></p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-30T18:53:54.950Z
Answers.LastActivityDate: 2019-08-30T00:42:47.363Z
Answers.LastEditDate: 2019-08-30T00:42:47.363Z
Answers.UserDisplayName: kaleem231
Answers.Body: <p>What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching the goal. In that case, the A* algorithm is way better than the greedy search algorithm. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-31T09:22:12.170Z
Answers.Text: dear can you elaborate your answer. sorry to say but i did not get your point.
Answers.UserDisplayName: Iram Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-18T20:38:28.740Z
Answers.Text: @IramShah - TemmanRafk is talking about the proof that A* is both optimal and complete. To do so it is shown due to the triangle inequality that the heuristic that estimates the distance remaining to the goal is not an overestimate. To see a fuller explanation see https://en.wikipedia.org/wiki/Admissible_heuristic
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-31T00:03:08.087Z
Answers.LastActivityDate: 2019-08-30T00:23:29.313Z
Answers.LastEditDate: 2019-08-30T00:23:29.313Z
Answers.UserDisplayName: Rafik
Answers.Body: <p>Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that <em>can</em> use both the knowledge acquired so far while exploring the search space, denoted by <span class="math-container">$g(n)$</span>, and a heuristic function, denoted by <span class="math-container">$h(n)$</span>, which estimates the distance to the goal node, for each node <span class="math-container">$n$</span> in the search space (often represented as a graph). </p>
  
  <p>Each of these search algorithms defines an "evaluation function", for each node <span class="math-container">$n$</span> in the graph (or search space), denoted by <span class="math-container">$f(n)$</span>. This evaluation function is used to determine which node, while searching, is "expanded" first, that is, which node is first removed from the <a href="https://ai.stackexchange.com/q/5949/2444">"fringe" (or "frontier", or "border")</a>, so as to "visit" its children. In general, the difference between the algorithms in the "best-first" category is in the definition of the evaluation function <span class="math-container">$f(n)$</span>.</p>
  
  <p>In the case of <a href="https://en.wikipedia.org/wiki/Best-first_search#Greedy_BFS" rel="noreferrer"><em>the greedy BFS algorithm</em></a>, the evaluation function is <span class="math-container">$f(n) = h(n)$</span>, that is, the greedy BFS algorithm first expands the node whose estimated distance to the goal is the smallest. So, greedy BFS does not use the "past knowledge", i.e. <span class="math-container">$g(n)$</span>. Hence its connotation "greedy". In general, the greedy BST algorithm is <strong>not complete</strong>, that is, there is always the risk to take a path that does not bring to the goal. In the greedy BFS algorithm, all nodes on the <em>border</em> (or fringe or frontier) are kept in memory, and nodes that have already been expanded do not need to be stored in memory and can therefore be discarded. In general, the greedy BFS is also <strong>not optimal</strong>, that is, the path found may not be the optimal one. In general, the time complexity is <span class="math-container">$\mathcal{O}(b^m)$</span>, where <span class="math-container">$b$</span> is the (maximum) branching factor and <span class="math-container">$m$</span> is the maximum depth of the search tree. The space complexity is proportional to the number of nodes in the fringe and to the length of the found path.</p>
  
  <p>In the case of <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer"><em>the A* algorithm</em></a>, the evaluation function is <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$h$</span> is an <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="noreferrer">admissible heuristic function</a>. The "star", often denoted by an asterisk, <code>*</code>, refers to the fact that A* uses an admissible heuristic function, which essentially means that A* is <strong>optimal</strong>, that is, it always finds the optimal path between the starting node and the goal node. A* is also <strong>complete</strong> (unless there are infinitely many nodes to explore in the search space). The time complexity is <span class="math-container">$\mathcal{O}(b^m)$</span>. However, A* needs to keep all nodes in memory while searching, not just the ones in the fringe, because A*, essentially, performs an "exhaustive search" (which is "informed", in the sense that it uses a heuristic function).</p>
  
  <p>In summary, greedy BFS is not complete, not optimal, has a time complexity of <span class="math-container">$\mathcal{O}(b^m)$</span> and a space complexity which can be polynomial. A* is complete, optimal, and it has a time and space complexity of <span class="math-container">$\mathcal{O}(b^m)$</span>. So, in general, A* uses more memory than greedy BFS. A* becomes impractical when the search space is huge. However, A* also guarantees that the found path between the starting node and the goal node is the optimal one and that the algorithm eventually terminates. Greedy BFS, on the other hand, uses less memory, but does not provide the optimality and completeness guarantees of A*. So, which algorithm is the "best" depends on the context, but both are "best"-first searches. </p>
  
  <p>Note: in practice, you may not use any of these algorithms: you may e.g. use, instead, <a href="https://en.wikipedia.org/wiki/Iterative_deepening_A*" rel="noreferrer">IDA*</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-09T16:35:34.887Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/105362/discussion-on-answer-by-nbro-what-are-the-differences-between-a-and-greedy-best).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-25T13:59:45.653Z
Answers.Text: Both GBFS and A* can choose to store the already expanded nodes to avoid loops. There is no difference in this regard between them IMO.
Answers.UserDisplayName: HappyFace
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-25T14:01:56.140Z
Answers.Text: @HappyFace This is not about opinions, but facts. A* is a type of best-first search, which is different from greedy BFS.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-27T14:03:19.143Z
Answers.Text: Both are greedy too. (Any "best-first" is greedy by definition.)
Answers.UserDisplayName: Alexey
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-27T15:22:20.717Z
Answers.Text: @Alexey I can entertain your claim by saying that it really depends on your definition of greedy. If you define greedy as "best", then yes, but then there are different "best". There are the short-sighted ones, which are the real greedy (like greedy best-first search), and the ones that take into account future estimates (A*), which is not really greedy because it takes into account not what is the next best immediate move, but what is the best move based on what you've done so far and what is your knowledge of the future.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-10T13:32:37.873Z
Answers.LastActivityDate: 2018-11-10T13:49:14.970Z
Answers.LastEditDate: 2018-11-10T13:49:14.970Z
Answers.UserDisplayName: nbro
Body: <p>What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?</p>
  
Tags: <algorithm><search><comparison><a-star>
Title: What are the differences between A* and greedy best-first search?
UserDisplayName: Marosh Fatima
ThreadText: # What are the differences between A* and greedy best-first search?
  
  (Asked by: username_0 on 2018-11-10)
  
  What are the differences between the A\* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
  
  **Tags:** algorithm, search, comparison, a-star
  
  ---
  
  ## 3 answers
  
  ### Answer by username_5 on 2018-11-10. Score: 14 | Accepted answer
  
  Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that *can* use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and a heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$ in the search space (often represented as a graph).
  
  Each of these search algorithms defines an "evaluation function", for each node $n$ in the graph (or search space), denoted by $f(n)$. This evaluation function is used to determine which node, while searching, is "expanded" first, that is, which node is first removed from the ["fringe" (or "frontier", or "border")](https://ai.stackexchange.com/q/5949/2444), so as to "visit" its children. In general, the difference between the algorithms in the "best-first" category is in the definition of the evaluation function $f(n)$.
  
  In the case of [*the greedy BFS algorithm*](https://en.wikipedia.org/wiki/Best-first_search#Greedy_BFS), the evaluation function is $f(n) = h(n)$, that is, the greedy BFS algorithm first expands the node whose estimated distance to the goal is the smallest. So, greedy BFS does not use the "past knowledge", i.e. $g(n)$. Hence its connotation "greedy". In general, the greedy BST algorithm is **not complete**, that is, there is always the risk to take a path that does not bring to the goal. In the greedy BFS algorithm, all nodes on the *border* (or fringe or frontier) are kept in memory, and nodes that have already been expanded do not need to be stored in memory and can therefore be discarded. In general, the greedy BFS is also **not optimal**, that is, the path found may not be the optimal one. In general, the time complexity is $\mathcal{O}(b^m)$, where $b$ is the (maximum) branching factor and $m$ is the maximum depth of the search tree. The space complexity is proportional to the number of nodes in the fringe and to the length of the found path.
  
  In the case of [*the A\* algorithm*](https://en.wikipedia.org/wiki/A*_search_algorithm), the evaluation function is $f(n) = g(n) + h(n)$, where $h$ is an [admissible heuristic function](https://en.wikipedia.org/wiki/Admissible_heuristic). The "star", often denoted by an asterisk, `*`, refers to the fact that A\* uses an admissible heuristic function, which essentially means that A\* is **optimal**, that is, it always finds the optimal path between the starting node and the goal node. A\* is also **complete** (unless there are infinitely many nodes to explore in the search space). The time complexity is $\mathcal{O}(b^m)$. However, A\* needs to keep all nodes in memory while searching, not just the ones in the fringe, because A\*, essentially, performs an "exhaustive search" (which is "informed", in the sense that it uses a heuristic function).
  
  In summary, greedy BFS is not complete, not optimal, has a time complexity of $\mathcal{O}(b^m)$ and a space complexity which can be polynomial. A\* is complete, optimal, and it has a time and space complexity of $\mathcal{O}(b^m)$. So, in general, A\* uses more memory than greedy BFS. A\* becomes impractical when the search space is huge. However, A\* also guarantees that the found path between the starting node and the goal node is the optimal one and that the algorithm eventually terminates. Greedy BFS, on the other hand, uses less memory, but does not provide the optimality and completeness guarantees of A\*. So, which algorithm is the "best" depends on the context, but both are "best"-first searches.
  
  Note: in practice, you may not use any of these algorithms: you may e.g. use, instead, [IDA\*](https://en.wikipedia.org/wiki/Iterative_deepening_A*).
  
  > **Comments:**
  > **username_5**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/105362/discussion-on-answer-by-nbro-what-are-the-differences-between-a-and-greedy-best).  
  > **username_6**: Both GBFS and A* can choose to store the already expanded nodes to avoid loops. There is no difference in this regard between them IMO.  
  > **username_5**: @HappyFace This is not about opinions, but facts. A* is a type of best-first search, which is different from greedy BFS.  
  > **username_7**: Both are greedy too. (Any "best-first" is greedy by definition.)  
  > **username_5**: @Alexey I can entertain your claim by saying that it really depends on your definition of greedy. If you define greedy as "best", then yes, but then there are different "best". There are the short-sighted ones, which are the real greedy (like greedy best-first search), and the ones that take into account future estimates (A*), which is not really greedy because it takes into account not what is the next best immediate move, but what is the best move based on what you've done so far and what is your knowledge of the future.  
  
  ---
  
  ### Answer by username_1 on 2018-10-30. Score: 2
  
  According to the book [Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/) (3rd edition), by Stuart Russel and Peter Norvig, specifically, section **3.5.1 Greedy best-first search** (p. 92)
  
  > Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, $f(n) = h(n)$.
  
  In this same section, the authors give an example that shows that greedy best-first search is neither optimal nor complete.
  
  In section **3.5.2 A\* search: Minimizing the total estimated solution cost** of the same book (p. 93), it states
  
  > A\* search evaluates nodes by combining $g(n)$, the cost to reach the node, and $h(n)$, the cost to get from the node to the goal $$f(n) = g(n) + h(n).$$
  >
  > Since $g(n)$ gives the path cost from the start node to node $n$, and $h(n)$ is the estimated cost of the cheapest path from $n$ to the goal, we have $f(n)$ = estimated cost of the cheapest solution through $n$.
  >
  > Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of $g(n) + h(n)$. It turns out that this strategy is more than just reasonable: provided that the heuristic function $h(n)$ satisfies certain conditions, A\* search is both complete and optimal. The algorithm is identical to uniform-cost search except that A\* uses $g + h$ instead of $g$
  
  
  ---
  
  ### Answer by username_2 on 2018-10-31. Score: 1
  
  What you said isn't totally wrong, but the A\* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching the goal. In that case, the A\* algorithm is way better than the greedy search algorithm.
  
  > **Comments:**
  > **username_3**: dear can you elaborate your answer. sorry to say but i did not get your point.  
  > **username_4**: @IramShah - TemmanRafk is talking about the proof that A* is both optimal and complete. To do so it is shown due to the triangle inequality that the heuristic that estimates the distance remaining to the goal is not an overestimate. To see a fuller explanation see https://en.wikipedia.org/wiki/Admissible_heuristic  
  
  ---
  
  