Menu
In this figure:
let's assume that h(C)=1
If f(A)=g(A)+h(A)=0+4=4, and f(C)=g(C)+h(C)=1+1=2
Then f(C) is NOT greater than or equal to f(A)
Therefore this example is consistent and admissible, but can someone give me an example of admissible heuristic that is not consistent? please
667
No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency.
A heuristic h is admissible (optimistic) if: 0 ≤ h(n) ≤ h∗(n) where h∗(n) is the true cost to a nearest goal Note: Coming up with admissible heuristics is most of what's involved in using A* in practice. Examples: Optimize: number of flips.
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.
A known problem with inconsistent heuristics is that they may cause algorithms like A∗ to find shorter paths to nodes that were previously expanded and inserted into the closed list. If this happens, then these nodes must be moved back to the open list, where they might be chosen for expansion again.
if you want your heuristics to be admissible then you should have that h(n) <=h*(n) for every node n where h* is the real cost to the goal. In your case you want:
h(A) <= 4
h(C) <= 3
h(G) <= 0
Consistency
If you want your heuristics to be consistent then you should have that h(G) = 0 and h(n) <= cost(n, c) + h(c) where the node c is a child of node c. So in your case
h(A) <= 1 + h(C)
h(C) <= 3 + h(G) = 3
If you want inconsistency and since h(C) <= 3 for the admissibility condition then you should have that h(A) > 1 + h(C). So any heristics that satisfies:
h(A) > 1 + h(C)
h(C) <= 3
h(G) = 0
is admissible and not consistent. You gave
h(A) = 4
h(C) = 1
h(G) = 0
which is a valid candidate.
152
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
