Answers.Body: <p>Yes, UCS is a special case of A*. </p>
  
  <p>UCS uses the evaluation function <span class="math-container">$f(n) = g(n)$</span>, where <span class="math-container">$g(n)$</span> is the length of the path from the starting node to <span class="math-container">$n$</span>, whereas A* uses the evaluation function <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$g(n)$</span> means the same thing as in UCS and <span class="math-container">$h(n)$</span>, called the "heuristic" function, is an estimate of the distance from <span class="math-container">$n$</span> to the goal node. In the A* algorithm, <span class="math-container">$h(n)$</span> must be <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="noreferrer">admissible</a>. </p>
  
  <p>UCS is a special case of A* which corresponds to having <span class="math-container">$h(n) = 0, \forall n$</span>. A heuristic function <span class="math-container">$h$</span> which has <span class="math-container">$h(n) = 0$</span>, <span class="math-container">$\forall n$</span>, is clearly admissible, because it always "underestimates" the distance to the goal, which cannot be smaller than <span class="math-container">$0$</span>, unless you have negative edges (but I assume that all edges are non-negative). So, indeed, UCS is a special case of A*, and its heuristic function is even admissible!</p>
  
  <p>To see this with an example, just draw a simple graph, and apply the A* algorithm using <span class="math-container">$h(n) = 0$</span>, for all <span class="math-container">$n$</span>, and then apply UCS to the same graph. You will obtain the same results.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-26T15:13:05.710Z
Answers.LastActivityDate: 2018-11-26T15:19:27.280Z
Answers.LastEditDate: 2018-11-26T15:19:27.280Z
Answers.UserDisplayName: nbro
Body: <p>How do I show that uniform-cost search is a special case of A*? How do I prove this?</p>
  
Tags: <comparison><search><proofs><a-star><uniform-cost-search>
Title: How do I show that uniform-cost search is a special case of A*?
UserDisplayName: dua fatima
ThreadText: # How do I show that uniform-cost search is a special case of A*?
  
  (Asked by: username_0 on 2018-11-26)
  
  How do I show that uniform-cost search is a special case of A\*? How do I prove this?
  
  **Tags:** comparison, search, proofs, a-star, uniform-cost-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-26. Score: 7 | Accepted answer
  
  Yes, UCS is a special case of A\*.
  
  UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A\* uses the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal node. In the A\* algorithm, $h(n)$ must be [admissible](https://en.wikipedia.org/wiki/Admissible_heuristic).
  
  UCS is a special case of A\* which corresponds to having $h(n) = 0, \forall n$. A heuristic function $h$ which has $h(n) = 0$, $\forall n$, is clearly admissible, because it always "underestimates" the distance to the goal, which cannot be smaller than $0$, unless you have negative edges (but I assume that all edges are non-negative). So, indeed, UCS is a special case of A\*, and its heuristic function is even admissible!
  
  To see this with an example, just draw a simple graph, and apply the A\* algorithm using $h(n) = 0$, for all $n$, and then apply UCS to the same graph. You will obtain the same results.
  
  
  ---
  
  