snippetMinor
How do you prove a heuristic is admissible?
Viewed 0 times
youadmissibleproveheuristichow
Problem
How does one prove that a suggested heuristic is admissible? Is this even possible?
For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell
How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?
For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell
How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?
Solution
Proving a heuristic is admissible usually means proving two things:
-
it follows the triangular inequality principle
-
given the same preconditions, the heuristic never overestimates the actual solution
-
it follows the triangular inequality principle
-
given the same preconditions, the heuristic never overestimates the actual solution
Context
StackExchange Computer Science Q#110708, answer score: 2
Revisions (0)
No revisions yet.