python实现A*和双向A*(启发式搜索)

【实例简介】

1. 实验目的 

1） 掌握搜索算法的基本设计思想与方法，  

2） 掌握A*算法的设计思想与方法，  

3） 熟练使用高级编程语言实现搜索算法，  

4） 利用实验测试给出的搜索算法的正确性。  

1. 实验问题 

寻路问题。以图1为例，输入一个方格表示的地图，要求用A*算法找到并输出从起点（在方格中标示字母S）到终点（在方格中标示字母T）的代价最小的路

径。有如下条件及要求：  

1） 每一步都落在方格中，而不是横竖线的交叉点。

2） 灰色格子表示障碍，无法通行。

3） 在每个格子处，若无障碍，下一步可以达到八个相邻的格子，并且只可以到达无障碍的相邻格子。其中，向上、下、左、右四个方向移动的代价为1，向四

个斜角方向移动的代价为 √2。

4） 在一些特殊格子上行走要花费额外的地形代价。比如，黄色格子代表沙

漠，经过它的代价为4；蓝色格子代表溪流，经过它的代价为2；白色格子为普通地形，经过它的代价为0。

5） 经过一条路径总的代价为移动代价 地形代价。其中移动代价是路径上所做的所有移动的代价的总和；地形代价为路径上除起点外所有格子的地形代价的总和。

【实例截图】

【核心代码】

def a_star_single(start, end, area_map):
    open = []
    close = []
    open.append(start) # open表首先加入起点，因为while循环条件，len>0  # 答案的节点  res = None # 还没找到终点   while len(open) > 0: # 选择可选点中F最小的  node = least_f(open)
        open.remove(node)
        close.append(node) # 获取周围的没在close里的又符合area_map范围的点  surrounds = get_surrounds(node, area_map, close)
        ret = False  for surround in surrounds: # 155行判断不在close里，但是不一定不在open里  if is_in_list(surround, open) is None: # 若不在open表里，要把它加进去  surround.parent = node # 则设置周围点的父节点是当前点   calc_g(node, surround, area_map) # 计算g  calc_h(surround, close, area_map) #计算h  # calc_h(surround, end)  # 计算h  surround.F = calc_f(surround) # g f  open.append(surround) # 把此节点加入open表  else: # 若此周围点已经在open表里  temp_f = calc_f(node) if temp_f < surround.F: # 如果新算的f值比原来已经存储的低  surround.parent = node # 则更新，把当前点作为此早已在Open表里的周围点的父节点  surround.F = calc_f(surround)
            res = is_in_list(end, open) # 查看终点是否在Open表里，因为此时，当前步的周围点都在open表里了  if res is not None: # 有则达到终点  ret = True   if ret: # 就跳出循环  break   path = [] while res is not None: # 起点的父节点是None    #res到这里刚开始必定为终点，如果上面已经找到了终点的话  path.append(res)
        res = res.parent # res赋值为当前点的父节点   return path