Answers.Body: <p>A* is an <strong>informed</strong> search algorithm. A* <em>informed</em> because it is based on the use of a <em>heuristic function</em>, which estimates the distance of each node to the goal, that is, the heuristic function provides <em>information</em> about the distance from any node to the goal node. The heuristic function can e.g. be the Euclidean distance (in the case this can be defined).</p>
  
  <p>More precisely, at each step, A* needs to select the next node to explore. It chooses the node <span class="math-container">$n$</span> with the smallest value of <span class="math-container">$$f(n) = g(n) + h(n),$$</span> where <span class="math-container">$g(n)$</span> is the actual distance from the starting node to node <span class="math-container">$n$</span> and <span class="math-container">$h(n)$</span> is the heuristic function that estimates the distance from node <span class="math-container">$n$</span> to the goal node.</p>
  
  <p>For example, suppose that we want to find the shortest path from Paris to Madrid. If you are already in Madrid, then you can estimate that the distance from Madrid to Madrid is zero, so <span class="math-container">$h(\text{Madrid}) = 0$</span>. However, if you're still in Paris, what is the estimate of the distance from Paris to Madrid? We can e.g. pick up a map of the world and choose <span class="math-container">$h(\text{Paris})$</span> to be the length of the straight segment that goes from Paris to Madrid. Similarly, we can do this for other intermediate cities. There are other ways of estimating this distance, but this is an understandable one, given that people are usually familiar with the Euclidean distance. (This example is a little bit misleading because the Earth is not flat and so the Euclidean geometry does not really apply, but, for simplicity, you can ignore this). </p>
  
  <p>For info regarding the completeness and optimality of A*, have a look at <a href="https://ai.stackexchange.com/a/8907/2444">https://ai.stackexchange.com/a/8907/2444</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-21T16:17:27.343Z
Answers.LastActivityDate: 2019-06-21T20:25:45.000Z
Answers.LastEditDate: 2019-06-21T20:25:45.000Z
Answers.UserDisplayName: nbro
Body: <p>What kind of search method is A*? Explain to me with an example.</p>
  
Tags: <algorithm><search><definitions><a-star>
Title: What kind of search method is A*?
UserDisplayName: Maira Khan
ThreadText: # What kind of search method is A*?
  
  (Asked by: username_0 on 2018-12-12)
  
  What kind of search method is A\*? Explain to me with an example.
  
  **Tags:** algorithm, search, definitions, a-star
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-21. Score: 1
  
  A\* is an **informed** search algorithm. A\* *informed* because it is based on the use of a *heuristic function*, which estimates the distance of each node to the goal, that is, the heuristic function provides *information* about the distance from any node to the goal node. The heuristic function can e.g. be the Euclidean distance (in the case this can be defined).
  
  More precisely, at each step, A\* needs to select the next node to explore. It chooses the node $n$ with the smallest value of $$f(n) = g(n) + h(n),$$ where $g(n)$ is the actual distance from the starting node to node $n$ and $h(n)$ is the heuristic function that estimates the distance from node $n$ to the goal node.
  
  For example, suppose that we want to find the shortest path from Paris to Madrid. If you are already in Madrid, then you can estimate that the distance from Madrid to Madrid is zero, so $h(\text{Madrid}) = 0$. However, if you're still in Paris, what is the estimate of the distance from Paris to Madrid? We can e.g. pick up a map of the world and choose $h(\text{Paris})$ to be the length of the straight segment that goes from Paris to Madrid. Similarly, we can do this for other intermediate cities. There are other ways of estimating this distance, but this is an understandable one, given that people are usually familiar with the Euclidean distance. (This example is a little bit misleading because the Earth is not flat and so the Euclidean geometry does not really apply, but, for simplicity, you can ignore this).
  
  For info regarding the completeness and optimality of A\*, have a look at <https://ai.stackexchange.com/a/8907/2444>.
  
  
  ---
  
  