《启发式搜索实验》由会员分享，可在线阅读，更多相关《启发式搜索实验（13页珍藏版）》请在金锄头文库上搜索。
1、(2)2 - ( 2 -费aIIEIu 1 -将窖)三(一) BHmsssss. fflmiais 一1(2) Sun0 fasHsisi swTJ解。: fsNgs+hmhs f SOJS器田dtMhnslnD冒s市岑gm) 画丑番带霞n费3将染令hs)星 nslnn茹爵更霞lsitfsss (ms)蛰警m案sHalhm)薯BBZ3AN 初善赛-F 雷夺汕fl n iLil即距离估计h(n)等于最短距离，那么搜素将严格沿着最短路径进行， 此时的搜索效率是最高的。然后我们通过图文结合的形式来解释下，如下图:Start障碍end12345中有这么几个要点先需要了解:1,类似迷宫，分W始节点(st
2、art)B碍物束节点(end)，我们需要从start节点探寻一条到end节点的路线2.对于探寻的每一步，都会以当前节点为基点，扫描其相邻的八个节点3计算当前节点与start节点及到end的距离4计算出最短路径如果明白了上面的场景描述，下面就可以进行分析了。在A*算法中，核心思想是一个公式，上面已经提到过:f(n)=g(n)+h(n)源程序清单：package com.itxxz.ui.suanfa.astar;import java.util.Iterator;import java.util.LinkedList;import java.util.Queue;import com.itxxz
3、.ui.suanfa.astar.Point;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,
4、 0, 0, 0, 0 , 1, 1, 1, 1, 0 , 1, 0, 0, 0, 0 , 3, 0, 1, 1, 1 ;/迷宫坐标对象private Point mazePoint = null;/开启队列，用于存放待处理的节点Queue openQueue = null;/关闭队列，用于存放已经处理过的节点Queue closedQueue = null;/起始节点到某个节点的距离int FList = null;/某个节点到目的节点的距离int GList = null;/起始节点经过某个节点到目的节点的距离 int HList = null;/*构造函数* param maze* 迷宫
5、图* param startPoint* 起始节点* param endPoint* 结束节点*/public ItxxzAstar(Point mazePoint, Point startPoint, Point endPoint) ( this.mazePoint = mazePoint;this.startPoint = startPoint;this.endPoint = endPoint;openQueue = new LinkedList();openQueue.offer(startPoint);closedQueue = new LinkedList();FList = new
6、 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+) ( FListij = Integer.MAX_VALUE; GListij = Integer.MAX_VALUE; HListij = Integer.MAX_
7、VALUE;/起始节点到当前节点的距离GListstartPoint.getX()startPoint.getY() = 0;/当前节点到目的节点的距离HListstartPoint.getX()startPoint.getY() = getPointDistance( startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY();/ f(x) = g(x) + h(x)FListstartPoint.getX()startPoint.getY() = GListstartPoint.getX()startPoin
8、t .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 - end_x) + Math.abs(current_y - end_y);/*数组迷宫地图* 0、可通行1、障碍2、开始节点3、结束节点*/public static void main(
9、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 Point(i, j, mazeArrayij);Point start = mazePoint12;Point end = mazePoint60;ItxxzAstar star = new ItxxzAstar(mazePoin
10、t, start, end);star.start();System.out.println(mazeArray.length + , + mazeArray0.length);star.printPath();/*开始迷宫搜索*/public void start() (while (currentPoint = findShortestFPoint() != null) (if (currentPoint.getX() = endPoint.getX()& currentPoint.getY() = endPoint.getY()return;updateNeighborPoints(cu
11、rrentPoint);/*获取距离最短的坐标点*/public Point findShortestFPoint() (currentPoint = null;shortestFPoint = null;int shortestFValue = Integer.MAX_WLUE;Iterator it = openQueue.iterator();while (it.hasNext() (currentPoint = it.next();if (FListcurrentPoint.getX()currentPoint.getY() = shortestFValue) ( shortestFP
12、oint = currentPoint;shortestFValue = FListcurrentPoint.getX()currentPoint.getY();if (shortestFValue != Integer.MAX_AALUE) (System.out.println(【移除节点】:+ shortestFPoint.getValue() + + shortestFPoint.getX() + ,+ shortestFPoint.getY() + );openQueue.remove(shortestFPoint);closedQueue.offer(shortestFPoint)
13、;return shortestFPoint;/*更新临近节点*/private void updateNeighborPoints(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(mazePointcurrent_xcurrent_y, mazePointcurrent_x - 1current_y);/下if (checkPosValid(current_x + 1, current_y) (System.out.print(下)；updatePoint(mazePointcurrent_xcurrent_y,mazePointcurrent_x + 1current_y);
