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

1. 实验目的

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

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

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

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

1. 实验问题

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

径。有如下条件及要求：

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

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

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

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

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

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

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