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