启发函数的介绍
是一种函数用来估算当前state和 目标state之间的距离，用于路径决策。
也就是说，该函数的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)
2.consistency（确保该启发函数在最小cost的qing'kuai'xai能够找到最优解）
示例
如果，一个启发函数是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，不然会使计算复杂度以指数形式增长。
练习
有一只红鸟，要吃五只黄鸟。请设计不同的启发算法，使其成功完成任务。
def null_heuristic(pos, problem):
""" The null heuristic. It is fast but uninformative. It always returns 0.
(State, SearchProblem) -> int
"""
return 0
def manhattan_heuristic(pos, problem):
""" The Manhattan distance heuristic for a PositionSearchProblem.
((int, int), PositionSearchProblem) -> int
"""
return abs(pos[0] - problem.goal_pos[0]) + abs(pos[1] - problem.goal_pos[1])
def euclidean_heuristic(pos, problem):
""" The Euclidean distance heuristic for a PositionSearchProblem
((int, int), PositionSearchProblem) -> float
"""
return ((pos[0] - problem.goal_pos[0]) ** 2 + (pos[1] - problem.goal_pos[1]) ** 2) ** 0.5
#Abbreviations
null = null_heuristic
manhattan = manhattan_heuristic
euclidean = euclidean_heuristic
#-------------------------------------------------------------------------------
# You have to implement the following heuristics for Q4 of the assignment.
# It is used with a MultiplePositionSearchProblem
#-------------------------------------------------------------------------------
#You can make helper functions here, if you need them
def bird_counting_heuristic(state, problem) :
position, yellow_birds = state
heuristic_value = len(yellow_birds) - len(problem.heuristic_info) # the number of rest yellow birds
for index in range(0,len(yellow_birds)):
if position == yellow_birds[index]: # if find the yellow birds
if position in problem.heuristic_info: # if it has been found before
heuristic_value = len(yellow_birds) - len(problem.heuristic_info)
else :
problem.heuristic_info[position] = 1 # record the yellow birds' position caught by red birds
heuristic_value = len(yellow_birds) - len(problem.heuristic_info) # the number of rest yellow birds
return heuristic_value
bch = bird_counting_heuristic
def every_bird_heuristic(state, problem):
"""
(((int, int), ((int, int))), MultiplePositionSearchProblem) -> number
"""
position, yellow_birds = state
heuristic_value = 0
for index in (0, len(yellow_birds)): # go through all the yellow birds
if yellow_birds[index] in problem.heuristic_info: # if this yellow bird has been found before
continue
else:
# calculate the distance between the red bird and the closest yellow bird
heuristic_value_test = abs(yellow_birds[index][0] - position[0]) + abs(yellow_birds[index][1] - position)[1]
if heuristic_value > heuristic_value_test: # compare the distance and find the closest yellow bird
heuristic_value = heuristic_value_test
if heuristic_value == 0:
problem.heuristic_info[position] = 1 # add the yellow bird position visited into dic
return heuristic_value
every_bird = every_bird_heuristic
以上code中有完整的4种方法，一是计算欧几里得距离；二是计算曼哈顿距离；三是计算剩余的黄鸟数量；最后是计算该红鸟与最近黄鸟的距离，返回最小值。
网友评论