开发者

what heuristic evaluation function or algorithm can be treated as inadmissible

I have learned several heuristic functions which开发者_开发问答 are admissible to deal with the classical 8 puzzle problem, and I know you can multiply a factor to a admissible function to make it inadmissible, however, I wonder is there any other inadmissible heuristic function for the 8 puzzle problem?


There are all sorts of inadmissible heuristics to this puzzle. An inadmissible heuristic just needs to overestimate the number of steps it will take to solve a given puzzle, and so one simple inadmissible heuristic would be

h(S) = infinity

Since any puzzle that's solvable can be solved in fewer than infinity steps, the heuristic is inadmissible.

A much trickier and more interesting question would be what good admissible heuristics are out there, since they require you to give the largest possible value you can that doesn't overestimate the distance. For that, I don't have a good answer. :-)


Heuristic evaluation function estimates the cost of an optimal path between a pair of states in a single-agent path-finding problem.

Read more on Heuristic evaluation function article.


Basically, any function that overestimates cost is inadmissible, which means that constructing inadmissible functions is easy.

Wikipedia has a good description

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜