Answers.Body: <p>Let's see their definition first:</p>
  
  <ol>
  <li><p><a href="https://en.wikipedia.org/wiki/Best-first_search" rel="nofollow noreferrer">Best First Search</a> (BFS):
  ‌ </p>
  
  <blockquote>
    <p>Best-first search is a search algorithm that explores a graph by expanding the most promising node chosen according to a specified rule.</p>
    
    <p>estimating the promise of node n by a "heuristic evaluation function <span class="math-container">${\displaystyle f(n)}$</span> which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain."</p>
  </blockquote></li>
  <li><p><a href="https://en.wikipedia.org/wiki/Hill_climbing" rel="nofollow noreferrer">Hill Climbing</a> (HC):</p>
  
  <blockquote>
    <p>In numerical analysis, hill climbing is a mathematical optimization technique that belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.</p>
  </blockquote></li>
  </ol>
  
  <p>Base on the definition, we can find the following differences:</p>
  
  <ul>
  <li>The aim of BFS is reaching to a specified goal by using a heuristic function (it might be greedy) vs. HC is a local search algorithm </li>
  <li>BFS is mostly used in the graph search (in a wide state space) to find a path. vs. HC is using for the optimization task. </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-25T00:04:44.477Z
Answers.Text: It's not true that BFS algorithms don't look at history. A* is a BFS algorithm and it looks at the history (in fact, its evaluation function is $f(n) = g(n) + h(n)$, where $h$ is an admissible heuristic and $g$ is the history (i.e. cost of the path from the start node to $n$), but it also looks at the estimates to the goal. That's the idea.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-25T00:09:42.933Z
Answers.Text: @nbro Many thanks for the comment. You're right. I wanted to explain about the locality of HC as I've explained in the first difference! So, I've removed that statement. Do you suggest any more differences?
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-25T00:10:52.127Z
Answers.Text: Yes, actually, I think you should explain how BFS algorithms (e.g. A*) choose to "move" (i.e. just explain a little bit about the evaluation function I talked about in my comment above) and how HC also "moves" in order to solve the optimization problem.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-25T00:12:40.060Z
Answers.Text: Also, note that the OP was specifically asking about "greedy" BFS. I think it's important to distinguish a greedy from a non-greedy BFS. A* is non-greedy. (At least, in the title). But I guess he was also confused ;)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-24T23:11:36.790Z
Answers.LastActivityDate: 2020-04-25T00:07:04.280Z
Answers.LastEditDate: 2020-04-25T00:07:04.280Z
Answers.UserDisplayName: OmG
Body: <p>While watching MIT's lectures about search, <a href="https://www.youtube.com/watch?v=j1H3jAAGlEA&amp;list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi&amp;index=4" rel="nofollow noreferrer">4. Search: Depth-First, Hill Climbing, Beam</a>, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around the 35 mins mark, the professor enqueues the paths in a way similar to greedy best-first search in which they are sorted, and the closer nodes expanded first. </p>
  
  <p>However, I have read elsewhere that hill climbing is different from the best first search. What's the difference between the two then?</p>
  
Tags: <comparison><search><hill-climbing><best-first-search>
Title: What is the difference between hill-climbing and greedy best-first search algorithms?
UserDisplayName: calveeen
ThreadText: # What is the difference between hill-climbing and greedy best-first search algorithms?
  
  (Asked by: username_0 on 2020-04-24)
  
  While watching MIT's lectures about search, [4. Search: Depth-First, Hill Climbing, Beam](https://www.youtube.com/watch?v=j1H3jAAGlEA&list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi&index=4), the professor explains the hill-climbing search in a way that is similar to the best-first search. At around the 35 mins mark, the professor enqueues the paths in a way similar to greedy best-first search in which they are sorted, and the closer nodes expanded first.
  
  However, I have read elsewhere that hill climbing is different from the best first search. What's the difference between the two then?
  
  **Tags:** comparison, search, hill-climbing, best-first-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-24. Score: 3 | Accepted answer
  
  Let's see their definition first:
  
  1. [Best First Search](https://en.wikipedia.org/wiki/Best-first_search) (BFS):
     ‌
  
     > Best-first search is a search algorithm that explores a graph by expanding the most promising node chosen according to a specified rule.
     >
     > estimating the promise of node n by a "heuristic evaluation function ${\displaystyle f(n)}$ which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain."
  2. [Hill Climbing](https://en.wikipedia.org/wiki/Hill_climbing) (HC):
  
     > In numerical analysis, hill climbing is a mathematical optimization technique that belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.
  
  Base on the definition, we can find the following differences:
  
  * The aim of BFS is reaching to a specified goal by using a heuristic function (it might be greedy) vs. HC is a local search algorithm
  * BFS is mostly used in the graph search (in a wide state space) to find a path. vs. HC is using for the optimization task.
  
  > **Comments:**
  > **username_2**: It's not true that BFS algorithms don't look at history. A* is a BFS algorithm and it looks at the history (in fact, its evaluation function is $f(n) = g(n) + h(n)$, where $h$ is an admissible heuristic and $g$ is the history (i.e. cost of the path from the start node to $n$), but it also looks at the estimates to the goal. That's the idea.  
  > **username_1**: @nbro Many thanks for the comment. You're right. I wanted to explain about the locality of HC as I've explained in the first difference! So, I've removed that statement. Do you suggest any more differences?  
  > **username_2**: Yes, actually, I think you should explain how BFS algorithms (e.g. A*) choose to "move" (i.e. just explain a little bit about the evaluation function I talked about in my comment above) and how HC also "moves" in order to solve the optimization problem.  
  > **username_2**: Also, note that the OP was specifically asking about "greedy" BFS. I think it's important to distinguish a greedy from a non-greedy BFS. A* is non-greedy. (At least, in the title). But I guess he was also confused ;)  
  
  ---
  
  