1. 实验目的
1） 掌握搜索算法的基本设计思想与方法，
2） 掌握A*算法的设计思想与方法，
3） 熟练使用高级编程语言实现搜索算法，
4） 利用实验测试给出的搜索算法的正确性。
1. 实验问题
寻路问题。以图1为例，输入一个方格表示的地图，要求用A*算法找到并输出从起点（在方格中标示字母S）到终点（在方格中标示字母T）的代价最小的路
径。有如下条件及要求：
1） 每一步都落在方格中，而不是横竖线的交叉点。
2） 灰色格子表示障碍，无法通行。
3） 在每个格子处，若无障碍，下一步可以达到八个相邻的格子，并且只可以到达无障碍的相邻格子。其中，向上、下、左、右四个方向移动的代价为1，向四
个斜角方向移动的代价为 √2。
4） 在一些特殊格子上行走要花费额外的地形代价。比如，黄色格子代表沙
漠，经过它的代价为4；蓝色格子代表溪流，经过它的代价为2；白色格子为普通地形，经过它的代价为0。
5） 经过一条路径总的代价为移动代价 地形代价。其中移动代价是路径上所做的所有移动的代价的总和；地形代价为路径上除起点外所有格子的地形代价的总和。
暂无评论