Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There's not even much about admissibility (which is not always used in game settings). I don't have a good sense for consistency/monotonicity. Do you have an example of an inconsistent admissible heuristic?


I'll do my best to provide an example. It is hard to come up with a general idea, but I can demonstrate using a graph: http://i.imgur.com/AwpTeRt.png

The numbers in the nodes represent heuristic values at each node and the numbers on edges represent edge weights; we're looking to get from S to T.

Our heuristic is admissible because it never overestimates the distance to the target.

Consistency dictates that the heuristic value at any node may at most be the weight of any out-edge added to the heuristic value of the node that the edge connects to. So in our example, the heuristic at A is 3, but at B it is 0, but 3 > 1 + 0, so our heuristic is inconsistent.

The reason this causes issues is because our algorithm assumes that any visited path is the shortest path to the end vertex of that path. So when we traverse this graph, we will visit B first, because the sum of its heuristic value and the respective edge weight is less than that of A.


Thanks!


Take a look at this paper:

http://web.cs.du.edu/~sturtevant/papers/incnew.pdf

Specifically, look at the Martelli G family example.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: