启发式搜索实验

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

1．实验目的

（1）了解搜索推理的相关技术；

（2）掌握启发式搜索算法或者基于规则推理的分析方法。 2．实验内容（2个实验内容可以选择1个实现）

（1）启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程，并求解博弈问题，理解求解流程和搜索顺序；

（2）产生式系统实验。熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。 3．实验报告要求

（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）源程序清单：

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 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 openQueue = null;

// 关闭队列，用于存放已经处理过的节点 Queue 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) { this.mazePoint = mazePoint; this.startPoint = startPoint; this.endPoint = endPoint;

openQueue = new LinkedList(); openQueue.offer(startPoint);

closedQueue = new LinkedList();

FList = new int[mazePoint.length][mazePoint[0].length]; GList = new int[mazePoint.length][mazePoint[0].length]; HList = new int[mazePoint.length][mazePoint[0].length];

for (int i = 0; i < mazePoint.length; i++) {

for (int j = 0; j < mazePoint[0].length; j++) { FList[i][j] = Integer.MAX_VALUE; GList[i][j] = Integer.MAX_VALUE; HList[i][j] = Integer.MAX_VALUE; } }

// 起始节点到当前节点的距离

GList[startPoint.getX()][startPoint.getY()] = 0; // 当前节点到目的节点的距离

HList[startPoint.getX()][startPoint.getY()] = getPointDistance( startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()); // f(x) = g(x) + h(x)

FList[startPoint.getX()][startPoint.getY()] = GList[startPoint.getX()][startPoint .getY()] + HList[startPoint.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(String[] args) {

// 创建节点迷宫图

Point[][] mazePoint = new Point[mazeArray.length][mazeArray[0].length]; for (int i = 0; i < mazePoint.length; i++) {

for (int j = 0; j < mazePoint[0].length; j++) {

mazePoint[i][j] = new Point(i, j, mazeArray[i][j]); } }

Point start = mazePoint[1][2]; Point end = mazePoint[6][0];

ItxxzAstar star = new ItxxzAstar(mazePoint, start, end); star.start();

System.out.println(mazeArray.length + \

star.printPath();

}

/**

本文来源：https://www.bwwdw.com/article/7g3t.html