<script type="application/ld+json">
{
 "@context": "https://schema.org",
 "@type": "FAQPage",
 "mainEntity": [{
   "@type": "Question",
   "name": "What is an admissible heuristic?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "An admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions. They always find the cheapest path solution."
   }
 },{
   "@type": "Question",
   "name": "What is a non-admissible heuristic?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "Non-admissible heuristics may overestimate the cost of reaching the goal state. There is no guarantee that they will reach an optimal solution."
   }
 },{
   "@type": "Question",
   "name": "What happens when a heuristic is not admissible?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "When a non-admissible heuristic is used in an algorithm, it might or might not result in an optimal solution."
   }
 }]
}
</script>

Admissible heuristic

What is an admissible heuristic?

An admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions. They always find the cheapest path solution.

For a heuristic to be admissible to a search problem, needs to be lower than or equal to the actual cost of reaching the goal.

Here is an example:

In the A* search algorithm, the evaluation function (where {\displaystyle n}n is the current node) is:

f(n)=g(n)+h(n)

where

f(n) = evaluation function.

g(n) = cost from start node to current node

h(n) = estimated cost from current node to goal

Here, h(n) gets calculated with the use of the heuristic function. If a non-admissible heuristic was used, it is possible that the algorithm would not reach the optimal solution because of an overestimation in the evaluation function.

What is a non-admissible heuristic?

Non-admissible heuristics may overestimate the cost of reaching the goal state. There is no guarantee that they will reach an optimal solution.


What happens when a heuristic is not admissible?

When a non-admissible heuristic is used in an algorithm, it might or might not result in an optimal solution. 

But, sometimes non-admissible heuristics expand a smaller amount of nodes. As a result, it is possible that the total cost (search cost + path cost) could end up being lower than an optimal solution that would be found by using an admissible heuristic


What is the difference between admissible heuristics and consistent heuristics?

A heuristic is considered to be consistent if the estimated cost from one node to successor node, added to the estimated cost from the successor node to the goal is less than or equal to the estimated cost from the current node to the goal state.

In an admissible heuristic, the estimated cost from the current node to the goal state is never greater than the actual cost.

All consistent heuristics are admissible heuristics, however, all admissible heuristics are not necessarily consistent heuristics.

About Engati

Engati powers 45,000+ chatbot & live chat solutions in 50+ languages across the world.

We aim to empower you to create the best customer experiences you could imagine. 

So, are you ready to create unbelievably smooth experiences?

Check us out!

Admissible heuristic

October 14, 2020

Table of contents

Key takeawaysCollaboration platforms are essential to the new way of workingEmployees prefer engati over emailEmployees play a growing part in software purchasing decisionsThe future of work is collaborativeMethodology

What is an admissible heuristic?

An admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions. They always find the cheapest path solution.

For a heuristic to be admissible to a search problem, needs to be lower than or equal to the actual cost of reaching the goal.

Here is an example:

In the A* search algorithm, the evaluation function (where {\displaystyle n}n is the current node) is:

f(n)=g(n)+h(n)

where

f(n) = evaluation function.

g(n) = cost from start node to current node

h(n) = estimated cost from current node to goal

Here, h(n) gets calculated with the use of the heuristic function. If a non-admissible heuristic was used, it is possible that the algorithm would not reach the optimal solution because of an overestimation in the evaluation function.

What is a non-admissible heuristic?

Non-admissible heuristics may overestimate the cost of reaching the goal state. There is no guarantee that they will reach an optimal solution.


What happens when a heuristic is not admissible?

When a non-admissible heuristic is used in an algorithm, it might or might not result in an optimal solution. 

But, sometimes non-admissible heuristics expand a smaller amount of nodes. As a result, it is possible that the total cost (search cost + path cost) could end up being lower than an optimal solution that would be found by using an admissible heuristic


What is the difference between admissible heuristics and consistent heuristics?

A heuristic is considered to be consistent if the estimated cost from one node to successor node, added to the estimated cost from the successor node to the goal is less than or equal to the estimated cost from the current node to the goal state.

In an admissible heuristic, the estimated cost from the current node to the goal state is never greater than the actual cost.

All consistent heuristics are admissible heuristics, however, all admissible heuristics are not necessarily consistent heuristics.

Share

Continue Reading