Answers.Body: <h2>Best-first search</h2>
  <p>BFS is a search approach and not just a single algorithm, so there are many best-first (BFS) algorithms, such as greedy BFS, A* and B*. BFS algorithms are <strong>informed</strong> search algorithms, as opposed to uninformed search algorithms (such as breadth-first search, depth-first search, etc.), i.e. BFS algorithms make use of domain knowledge that can be encoded into a so-called <strong>heuristic function</strong> (that's why they are informed!).</p>
  <p>Every BFS algorithm defines a so-called <strong>evaluation function</strong> <span class="math-container">$f$</span> of the following form</p>
  <p><span class="math-container">$$f(n) = g(n) + h(n)$$</span></p>
  <p>for all nodes <span class="math-container">$n \in V$</span> (where <span class="math-container">$V$</span> is the set of nodes or states of the search space), where</p>
  <ul>
  <li><p><span class="math-container">$g(n)$</span> is the cost from the start node (of the search) to the node <span class="math-container">$n$</span>, and</p>
  </li>
  <li><p><span class="math-container">$h(n)$</span> (the so-called heuristic, which is the way of including domain knowledge to solve the search problem) is an estimate of the cost of the cheapest path from <span class="math-container">$n$</span> to the goal node.</p>
  </li>
  </ul>
  <p>Depending on how you define <span class="math-container">$f$</span> and, in particular, the heuristic function <span class="math-container">$h$</span>, you get different BFS algorithms. For instance, A* is a BFS algorithm where <span class="math-container">$h$</span> is an <em>admissible heuristic</em> (i.e. it never overestimates the cost to the goal node). Because of this admissibility property, A* is guaranteed to find the globally optimal solution (i.e. the cheapest path from a start node to the goal node among all paths), but you can ignore this detail.</p>
  <p>To apply a BFS algorithm, you need to define the evaluation function and the <strong>search space</strong>, i.e. the states (or nodes) and their connections. For example, if you want to find the cheapest path from Paris to Madrid, you need to define that Paris is the start node, Madrid the goal node and then you need to define all intermediate nodes between Paris and Madrid, but you also need to define <span class="math-container">$g$</span> and <span class="math-container">$h$</span>.</p>
  <h2>Hill climbing</h2>
  <p>Hill climbing (HC) is a <em>general</em> search strategy (so it's also not just an algorithm!). HC algorithms are <strong>greedy local search</strong> algorithms, i.e. they typically only find local optima (as opposed to global optima) and they do that greedily (i.e. they do not look ahead). The idea behind HC algorithms is that of moving (or climbing) in the direction of increasing value. HC algorithms can be used to solve optimization problems and not just well-defined search problems, i.e. you start from some solution and you move to the best neighboring solution, and then loop.</p>
  <h2>Best-first search vs hill climbing</h2>
  <ul>
  <li>BFS algorithms are informed search algorithms (as opposed to uninformed)</li>
  <li>BFS algorithms need to define the search space and the evaluation function</li>
  <li>Some BFS algorithms (such as A*) are guaranteed to find the best global solution</li>
  <li>HC algorithms are general (i.e. widely applicable) but local and greedy search and optimization algorithms; consequently, they are not generally guaranteed to find the global optimum (but, in practice, they may work well, depending also on the problem).</li>
  <li>HC algorithms do not need to define the search space explicitly (i.e. you do not need to define the start and goal nodes, and so on), but you just need a way of determining the best neighboring solution</li>
  </ul>
  <h2>Further reading</h2>
  <p>The book <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a> by Stuart Russell and Peter Norvig provides more details about these two search approaches. (You can find free copies of this book online).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-04T21:16:56.117Z
Answers.LastActivityDate: 2021-10-13T12:32:38.767Z
Answers.LastEditDate: 2021-10-13T12:32:38.767Z
Answers.UserDisplayName: nbro
Body: <p>How does <em>best-first search</em> differ from <em>hill-climbing</em>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-04T06:48:48.510Z
Comments.Text: See also [this](https://stackoverflow.com/a/16652181/129889) post.
Comments.UserDisplayName: alltom
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-13T12:31:06.117Z
Comments.Text: [You should accept the answer below, if it answers your question](https://ai.stackexchange.com/help/someone-answers), which I think it does.
Comments.UserDisplayName: nbro
Tags: <comparison><search><hill-climbing><best-first-search>
Title: How does best-first search differ from hill-climbing?
UserDisplayName: Ayesha Sajjad
ThreadText: # How does best-first search differ from hill-climbing?
  
  (Asked by: username_0 on 2020-07-04)
  
  How does *best-first search* differ from *hill-climbing*?
  
  **Tags:** comparison, search, hill-climbing, best-first-search
  > **Comments:**
  > **username_1**: See also [this](https://stackoverflow.com/a/16652181/129889) post.  
  > **username_2**: [You should accept the answer below, if it answers your question](https://ai.stackexchange.com/help/someone-answers), which I think it does.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-07-04. Score: 2
  
  ## Best-first search
  
  BFS is a search approach and not just a single algorithm, so there are many best-first (BFS) algorithms, such as greedy BFS, A\* and B\*. BFS algorithms are **informed** search algorithms, as opposed to uninformed search algorithms (such as breadth-first search, depth-first search, etc.), i.e. BFS algorithms make use of domain knowledge that can be encoded into a so-called **heuristic function** (that's why they are informed!).
  
  Every BFS algorithm defines a so-called **evaluation function** $f$ of the following form
  
  $$f(n) = g(n) + h(n)$$
  
  for all nodes $n \in V$ (where $V$ is the set of nodes or states of the search space), where
  
  * $g(n)$ is the cost from the start node (of the search) to the node $n$, and
  * $h(n)$ (the so-called heuristic, which is the way of including domain knowledge to solve the search problem) is an estimate of the cost of the cheapest path from $n$ to the goal node.
  
  Depending on how you define $f$ and, in particular, the heuristic function $h$, you get different BFS algorithms. For instance, A\* is a BFS algorithm where $h$ is an *admissible heuristic* (i.e. it never overestimates the cost to the goal node). Because of this admissibility property, A\* is guaranteed to find the globally optimal solution (i.e. the cheapest path from a start node to the goal node among all paths), but you can ignore this detail.
  
  To apply a BFS algorithm, you need to define the evaluation function and the **search space**, i.e. the states (or nodes) and their connections. For example, if you want to find the cheapest path from Paris to Madrid, you need to define that Paris is the start node, Madrid the goal node and then you need to define all intermediate nodes between Paris and Madrid, but you also need to define $g$ and $h$.
  
  ## Hill climbing
  
  Hill climbing (HC) is a *general* search strategy (so it's also not just an algorithm!). HC algorithms are **greedy local search** algorithms, i.e. they typically only find local optima (as opposed to global optima) and they do that greedily (i.e. they do not look ahead). The idea behind HC algorithms is that of moving (or climbing) in the direction of increasing value. HC algorithms can be used to solve optimization problems and not just well-defined search problems, i.e. you start from some solution and you move to the best neighboring solution, and then loop.
  
  ## Best-first search vs hill climbing
  
  * BFS algorithms are informed search algorithms (as opposed to uninformed)
  * BFS algorithms need to define the search space and the evaluation function
  * Some BFS algorithms (such as A\*) are guaranteed to find the best global solution
  * HC algorithms are general (i.e. widely applicable) but local and greedy search and optimization algorithms; consequently, they are not generally guaranteed to find the global optimum (but, in practice, they may work well, depending also on the problem).
  * HC algorithms do not need to define the search space explicitly (i.e. you do not need to define the start and goal nodes, and so on), but you just need a way of determining the best neighboring solution
  
  ## Further reading
  
  The book [Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/) by Stuart Russell and Peter Norvig provides more details about these two search approaches. (You can find free copies of this book online).
  
  
  ---
  
  