启发式搜索实验

1、实验三 搜索推理技术启发式搜索算法A*算法1实验目的（1）了解搜索推理的相关技术；（2）掌握启发式搜索算法或者基于规则推理的分析方法。2实验内容（2个实验内容可以选择1个实现）（1）启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程，并求解博弈问题，理解求解流程和搜索顺序；（2）产生式系统实验。熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。3实验报告要求（1）简述实验原理及方法，并请给出程序设计流程图。（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，

2、g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。然后我们通过图文结合的形式来解释下，如下图：图中有这么几个要点先需要了解：1、类似迷宫图，分开始节点(start)、障碍物、结束节点(end)，我们需要从start节点探寻一条到end节点的路线2、对于

3、探寻的每一步，都会以当前节点为基点，扫描其相邻的八个节点 3、计算当前节点与start节点及到end的距离4、计算出最短路径如果明白了上面的场景描述，下面就可以进行分析了。在A*算法中，核心思想是一个公式，上面已经提到过：f(n)=g(n)+h(n)（2）源程序清单：package com.itxxz.ui.suanfa.astar; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import com.itxxz.ui.suanfa.astar.Point; public clas

4、s 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,

5、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; /

6、* * 构造函数 * * param maze * 迷宫图 * param startPoint * 起始节点 * param endPoint * 结束节点 */ public ItxxzAstar(Point mazePoint, Point startPoint, Point endPoint) this.mazePoint = mazePoint; this.startPoint = startPoint; this.endPoint = endPoint; openQueue = new LinkedList<Point>(); openQueue.offer(start

7、Point); closedQueue = new LinkedList<Point>(); FList = new intmazePoint.lengthmazePoint0.length; GList = new intmazePoint.lengthmazePoint0.length; HList = new intmazePoint.lengthmazePoint0.length; for (int i = 0; i < mazePoint.length; i+) for (int j = 0; j < mazePoint0.length; j+) FListi

8、j = Integer.MAX_VALUE; GListij = Integer.MAX_VALUE; HListij = Integer.MAX_VALUE; / 起始节点到当前节点的距离 GListstartPoint.getX()startPoint.getY() = 0; / 当前节点到目的节点的距离 HListstartPoint.getX()startPoint.getY() = getPointDistance( startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY(); / f(x) = g(x

9、) + h(x) FListstartPoint.getX()startPoint.getY() = GListstartPoint.getX()startPoint .getY() + HListstartPoint.getX()startPoint.getY(); /* * 计算当前坐标与结束坐标之间的距离 * * 计算方法为每向相信坐标移动一次算作一个距离单位 * */ private int getPointDistance(int current_x, int current_y, int end_x, int end_y) return Math.abs(current_x - e

10、nd_x) + Math.abs(current_y - end_y); /* * 数组迷宫地图 * * 0、可通行 1、障碍 2、开始节点 3、结束节点 * */ public static void main(String args) / 创建节点迷宫图 Point mazePoint = new PointmazeArray.lengthmazeArray0.length; for (int i = 0; i < mazePoint.length; i+) for (int j = 0; j < mazePoint0.length; j+) mazePointij = new

11、 Point(i, j, mazeArrayij); Point start = mazePoint12; Point end = mazePoint60; ItxxzAstar star = new ItxxzAstar(mazePoint, start, end); star.start(); System.out.println(mazeArray.length + "," + mazeArray0.length); star.printPath(); /* * 开始迷宫搜索 * */ public void start() while (currentPoint =

12、 findShortestFPoint() != null) if (currentPoint.getX() = endPoint.getX() && currentPoint.getY() = endPoint.getY() return; updateNeighborPoints(currentPoint); /* * 获取距离最短的坐标点 * */ public Point findShortestFPoint() currentPoint = null; shortestFPoint = null; int shortestFValue = Integer.MAX_VA

13、LUE; Iterator<Point> it = openQueue.iterator(); while (it.hasNext() currentPoint = it.next(); if (FListcurrentPoint.getX()currentPoint.getY() <= shortestFValue) shortestFPoint = currentPoint; shortestFValue = FListcurrentPoint.getX()currentPoint.getY(); if (shortestFValue != Integer.MAX_VAL

14、UE) System.out .println("【移除节点】:" + shortestFPoint.getValue() + "" + shortestFPoint.getX() + "," + shortestFPoint.getY() + ""); openQueue.remove(shortestFPoint); closedQueue.offer(shortestFPoint); return shortestFPoint; /* * 更新临近节点 */ private void updateNeighb

15、orPoints(Point currentPoint) int current_x = currentPoint.getX(); int current_y = currentPoint.getY(); System.out.println("当前节点：" + current_x + "," + current_y + ""); / 上 if (checkPosValid(current_x - 1, current_y) System.out.print("上"); updatePoint(mazePointc

16、urrent_xcurrent_y, mazePointcurrent_x - 1current_y); / 下 if (checkPosValid(current_x + 1, current_y) System.out.print("下"); updatePoint(mazePointcurrent_xcurrent_y, mazePointcurrent_x + 1current_y); / 左 if (checkPosValid(current_x, current_y - 1) System.out.print("左"); updatePoin

17、t(mazePointcurrent_xcurrent_y, mazePointcurrent_xcurrent_y - 1); / 右 if (checkPosValid(current_x, current_y + 1) System.out.print("右"); updatePoint(mazePointcurrent_xcurrent_y, mazePointcurrent_xcurrent_y + 1); System.out.println("-"); /* * 检查该节点是否有效 * */ private boolean checkPos

18、Valid(int x, int y) / 检查x,y是否越界， 并且当前节点不是墙 if (x >= 0 && x < mazePoint.length) && (y >= 0 && y < mazePoint0.length) && (mazePointxy.getValue() != 1) / 检查当前节点是否已在关闭队列中，若存在，则返回 "false" Iterator<Point> it = closedQueue.iterator(); Point point

19、= null; while (it.hasNext() if (point = it.next() != null) if (point.getX() = x && point.getY() = y) return false; return true; return false; /* * 更新当前节点 */ private void updatePoint(Point lastPoint, Point currentPoint) int last_x = lastPoint.getX(); int last_y = lastPoint.getY(); int current

20、_x = currentPoint.getX(); int current_y = currentPoint.getY(); / 起始节点到当前节点的距离 int temp_g = GListlast_xlast_y + 1; / 当前节点到目的位置的距离 System.out.print(" " + current_x + "," + current_y + "" + mazePointcurrent_xcurrent_y.getValue(); int temp_h = getPointDistance(current_x, cu

21、rrent_y, endPoint.getX(), endPoint.getY(); System.out.println("到目的位置的距离 :" + temp_h); / f(x) = g(x) + h(x) int temp_f = temp_g + temp_h; System.out.println("f(x) = g(x) + h(x) :" + temp_f + "=" + temp_g + "+" + temp_h); / 如果当前节点在开启列表中不存在，则：置入开启列表，并且“设置” / 1) 起

22、始节点到当前节点距离 / 2) 当前节点到目的节点的距离 / 3) 起始节点到目的节点距离 if (!openQueue.contains(currentPoint) openQueue.offer(currentPoint); currentPoint.setFather(lastPoint); System.out.println("添加到开启列表:" + currentPoint.getValue() + "" + currentPoint.getX() + "," + currentPoint.getY() + "&

23、quot;); / 起始节点到当前节点的距离 GListcurrent_xcurrent_y = temp_g; / 当前节点到目的节点的距离 HListcurrent_xcurrent_y = temp_h; / f(x) = g(x) + h(x) FListcurrent_xcurrent_y = temp_f; else / 如果当前节点在开启列表中存在，并且， / 从起始节点、经过上一节点到当前节点、至目的地的距离 < 上一次记录的从起始节点、到当前节点、至目的地的距离， / 则：“更新” / 1) 起始节点到当前节点距离 / 2) 当前节点到目的节点的距离 / 3) 起始节点

24、到目的节点距离 if (temp_f < FListcurrent_xcurrent_y) / 起始节点到当前节点的距离 GListcurrent_xcurrent_y = temp_g; / 当前节点到目的位置的距离 HListcurrent_xcurrent_y = temp_h; / f(x) = g(x) + h(x) FListcurrent_xcurrent_y = temp_f; / 更新当前节点的父节点 currentPoint.setFather(lastPoint); System.out.println("currentPoint:" + cur

25、rentPoint.getValue() + "" + currentPoint.getX() + "," + currentPoint.getY() + ""); System.out.println("currentPoint.father:" + currentPoint.getFather().getValue() + "" + currentPoint.getFather().getX() + "," + currentPoint.getFather().getY(

26、) + ""); /* * 打印行走路径 * */ public void printPath() System.out.println("= 开始打印行走路径【用 8 表示】 ="); Point father_point = null; int result = new intmazeArray.lengthmazeArray0.length; for (int i = 0; i < mazeArray.length; i+) for (int j = 0; j < mazeArray0.length; j+) resultij = 0; int step = 0; father_point = mazePointendPoint.getX()endPoint.