patternMajor
How does an admissible heuristic ensure an optimal solution?
Viewed 0 times
optimaladmissibleensureheuristicdoeshowsolution
Problem
When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves).
How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.
If you want you can explain using the Manhattan distance heuristic of the 8-puzzle.
How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.
If you want you can explain using the Manhattan distance heuristic of the 8-puzzle.
Solution
If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal.
Look at this simple example.
Let $A$ and $G$ be respectively the starting and goal nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X_{i})$ be the step cost function from node $N$ to its neighbour $X_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).
Let the heuristics be
-
$h(B) = 3$
-
$h(C) = 4$
This heuristics function $H$ is not admissible, because $$h(C) = 4 > c(C, G) = 2$$
If the $A^*$ algorithm starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there.
And the path will be $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$ with cost $3$. If the heuristic function was admissible this would not have happened.
Look at this simple example.
Let $A$ and $G$ be respectively the starting and goal nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X_{i})$ be the step cost function from node $N$ to its neighbour $X_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).
Let the heuristics be
-
$h(B) = 3$
-
$h(C) = 4$
This heuristics function $H$ is not admissible, because $$h(C) = 4 > c(C, G) = 2$$
If the $A^*$ algorithm starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there.
And the path will be $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$ with cost $3$. If the heuristic function was admissible this would not have happened.
Context
StackExchange Computer Science Q#16065, answer score: 20
Revisions (0)
No revisions yet.