Answers.Body: <p>It is often possible to construct a heuristic which is a provable lower bound on a cost.</p>
  <p>For instance, on any path search in a metric space (one with consistent measurements between items), you can calculate the direct distance between two points, and that would be an admissable heuristic for any path-finding search where not all paths are available. This is very easy in grid spaces (Manhatten distance) or Euclidean geometry, which are common settings for path-finding problems.</p>
  <p>In general, if your problem is to find a solution to a problem with constraints, you can simplify that problem by removing some or all of the constraints, and use an easy to calculate cost from the simplified problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-30T22:46:17.093Z
Answers.LastActivityDate: 2023-10-30T22:46:17.093Z
Answers.UserDisplayName: Neil Slater
Body: <p>An heuristic is admissible if never overestimates the real cost to reach the goal.</p>
  <p>In order to prove that an heuristic <span class="math-container">$h$</span> is admissible we need to prove that for every state <span class="math-container">$s$</span> in the state space we have <span class="math-container">$h(s)\le h^*(s)$</span>, where <span class="math-container">$h^*(s)$</span> is the perfect heuristic.</p>
  <p>To prove that a given heuristic is admissible we need to know the perfect heuristic, but if we know the perfect heuristic wouldn't it be useless to search an admissible heuristic?</p>
  <p>Are there other ways to prove that an heuristic is admissible?</p>
  
Tags: <heuristics><admissible-heuristic>
Title: How to determine that an heuristic is admissible
UserDisplayName: Jose Manuel
ThreadText: # How to determine that an heuristic is admissible
  
  (Asked by: username_0 on 2023-10-30)
  
  An heuristic is admissible if never overestimates the real cost to reach the goal.
  
  In order to prove that an heuristic $h$ is admissible we need to prove that for every state $s$ in the state space we have $h(s)\le h^\*(s)$, where $h^\*(s)$ is the perfect heuristic.
  
  To prove that a given heuristic is admissible we need to know the perfect heuristic, but if we know the perfect heuristic wouldn't it be useless to search an admissible heuristic?
  
  Are there other ways to prove that an heuristic is admissible?
  
  **Tags:** heuristics, admissible-heuristic
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-10-30. Score: 1
  
  It is often possible to construct a heuristic which is a provable lower bound on a cost.
  
  For instance, on any path search in a metric space (one with consistent measurements between items), you can calculate the direct distance between two points, and that would be an admissable heuristic for any path-finding search where not all paths are available. This is very easy in grid spaces (Manhatten distance) or Euclidean geometry, which are common settings for path-finding problems.
  
  In general, if your problem is to find a solution to a problem with constraints, you can simplify that problem by removing some or all of the constraints, and use an easy to calculate cost from the simplified problem.
  
  
  ---
  
  