启发式搜索实验.doc

实验三搜索推理技术
启发式搜索算法—A*算法

(1)了解搜索推理的相关技术;
(2)掌握启发式搜索算法或者基于规则推理的分析方法。
(2个实验内容可以选择1个实现)
(1)启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程,并求解博弈问题,理解求解流程和搜索顺序;
(2)产生式系统实验。熟悉和掌握产生式系统的运行机制,掌握基于规则推理的基本方法。

(1)简述实验原理及方法,并请给出程序设计流程图。
(A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
公式表示为: f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数,
g(n) 是在状态空间中从初始节点到n节点的实际代价,
h(n) 是从n到目标节点最佳路径的估计代价。
保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:
估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行, 此时的搜索效率是最高的。
然后我们通过图文结合的形式来解释下,如下图:
图中有这么几个要点先需要了解:
1、类似迷宫图,分开始节点(start)、障碍物、结束节点(end),我们需要从start节点探寻一条到end节点的路线
2、对于探寻的每一步,都会以当前节点为基点,扫描其相邻的八个节点
3、计算当前节点与start节点及到end的距离
4、计算出最短路径
如果明白了上面的场景描述,下面就可以进行分析了。
在A*算法中,核心思想是一个公式,上面已经提到过:f(n)=g(n)+h(n)
(2)源程序清单:
.;

import ;
import ;
import ;

.;

public class ItxxzAstar {
// 开始节点
private Point startPoint = null;
// 当前节点
private Point endPoint = null;
// 结束节点
private Point currentPoint = null;
// 最短距离坐标节点
private Point shortestFPoint = null;

// 迷宫数组地图
private static final int[][] mazeArray = {
{ 1, 0, 0, 0, 0 },
{ 1, 0, 2, 0, 0 },
{ 1, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 3, 0, 1, 1, 1 } };

// 迷宫坐标对象
private Point[][] mazePoint = null;

// 开启队列,用于存放待处理的节点
Queue<Point> openQueue = null;
// 关闭队列,用于存放已经处理过的节点
Queue<Point> closedQueue = null;

// 起始节点到某个节点的距离
int[][] FList = null;
// 某个节点到目的节点的距离
int[][] GList = null;
// 起始节点经过某个节点到目的节点的距离
int[][] HList = null;

/**
* 构造函数
*
* ***@param maze
* 迷宫图
* ***@param startPoint
* 起始节点
* ***@param endPoint
* 结束节点
*/
public ItxxzAstar(Point[][] mazePoint, Point startPoint, Point endPoint) {
= mazePoint;
= startPoint;
= endPoint;

openQueue = new LinkedLi