https://stackoverflow.com/questions/20745371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianAdmissible
How much we think it will cost to get to the goal isn't more than it will actually cost.
Why do we need admissibility?
If any expected cost is less than the actual cost, it means the optimal path will always have an expected cost less than or equal to its true cost, which will be less than the true cost of some non-optimal path. Since we always explore the node with the lowest expected total cost first and when we reach the goal we'd only look at the true cost, we can never reach the goal through a non-optimal path.
If we think it will cost more than it will actually cost, we could actually end up taking a more expensive path. The expected cost of path A could be more than the expected cost of path B, yet path A can have a lower actual cost. This would mean we'd explore the non-optimal path B first.
If a heuristic is not admissible, we might theoretically never even get to the goal (or at least we'd explore the entire possible space before getting there). While this is unlikely with a reasonable heuristic, it is possible to create a heuristic where we think it will cost less to get to the goal the further away we are, and the expected remaining cost decreases faster than the actual cost when moving away from the goal. As a simple (finite) example: heuristic = 100000000 - 2 * actual.
Consistent
No move we make should decrease the expected total cost. Put in another way: any move made should decrease the heuristic by no more than the cost of that move.
The expected total cost (f(n)) is the expected remaining cost (h(n)) plus the cost so far (g(n)). As an example, we may think the total time to get to the goal would be 10 minutes. After travelling 5 minutes, it's fine if we think the total time (including the 5 minutes travelled) will be 11 minutes, but we shouldn't think the total time is 9 minutes.
Note: for the remaining cost, we only consider how long we think it will take. How long it actually takes may be different.
In addition to the above, consistent heuristics also need to have an expected remaining cost of 0 when we're already at the goal.
A consistent heuristic is also admissible (but not necessarily the other way around). This follows from the above.
Why do we need consistency?
If we keep making moves (towards or away from the goal), we want the cost to increase. Otherwise we could end up moving away from the goal and exploring a whole bunch of unpromising paths before we finally find the optimal one.
Note: if a heuristic is admissible but not consistent, we won't find a non-optimal path to the goal, but finding the optimal path may take a while.
Examples
h(n) = heuristic, i.e. expected (remaining) cost from n to goal
g(n) = cost (so far) from the start to n
t(n) = true (remaining) cost from n to goal
h(n) = 10 (except h(goal) = 0): Not admissible if moves cost less than 10, since there would be some n where the t(n) < 10. Not consistent since moving to the goal would involve decreasing the heuristic from 10 to 0, yet the move to do so would cost less than 10. However, if every move costs at least 10, this would be both admissible and consistent.
h(n) = 0: Admissible since (for positive costs) it can't cost less than 0 to get to the goal. Consistent since the heuristic will never decrease. Not particularly useful though. This would be equivalent to Dijkstra's algorithm.
h(n) = t(n) / 2: Admissible since the expected cost is lower than the true cost. Consistent since the cost of a move will always be at least double the expected cost of that move (it will also increase h(n) if moving away from the goal), thus any move will increase the total expected cost.
