3.启发函数（heuristic）的设计
启发函数的介绍
是⼀种函数⽤来估算当前state和 ⽬标state之间的距离，⽤于路径决策。
value函数什么意思也就是说，该函数的IQ直接决定了寻路径的快慢和准确度（accuracy）
在A*算法⾥：
Evaluation function： f(n) = g(n) + h(n)
h(n)就是启发函数，如果我们将该算法⽤于电脑在游戏中的⾓⾊，那么该函数将直接决定游戏地难度，当我们在调整游戏难度的时候，其实就是在重新选择⼀个更完美或者的启发函数。
相关性质
1.admissibility(决定了启发函数得到最佳solution)
⼀个启发函数是admissible，那么当
a是⾮最佳goal，b是最佳goal，c 是起始点，n 是⼀个中间点。
通过该启发函数，最后得到的应该是b，⽽不是a。
c-->a: f(a) = g(a) + h(a) =g(a)-----since a is a goal node, hence, h(a) = 0
c-->b: f(b) = g(b) + h(b) = g(b)
即：f(a)>=f(b)>=f(n)
since h is admissible, f(n) does not overestimate g(b)
⽰例
如果，⼀个启发函数是consistent，那么
h(n) ≤ c(n, a, n′) + h(n′)
也就是说，⼀旦⼀个node 的state被expended，那么，这个cost （ h(node) ）就是最⼩的cost。
所以，⼀个启发函数是consistent，它也是admissible。反之，不可。
3.Dominance（⽤于表现不同启发函数的关系）
two admissible heuristics ha, hb：如果对于所有n, ha(n) >hb(n)，那么，我们可以说 ha dominates hb，对于这个search问题，我们最好使⽤ha作为启发函数。
⼀些想法
1.很多问题都不会像tree的结构那么简单，graph更适合表⽰现实问题。
2.环形结构可以避免不必要的termination。
3.在探测node时，要避免对同⼀个node的重复test，不然会使计算复杂度以指数形式增长。
练习
有⼀只红鸟，要吃五只黄鸟。请设计不同的启发算法，使其成功完成任务。
以上code中有完整的4种⽅法，⼀是计算欧⼏⾥得距离；⼆是计算曼哈顿距离；三是计算剩余的黄鸟数量；最后是计算该红鸟与最近黄鸟的距离，返回最⼩值。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。