当前位置：文档库 › 启发式搜索实验

启发式搜索实验

实验三搜索推理技术

启发式搜索算法—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_V ALUE;

GList[i][j] = Integer.MAX_V ALUE;

HList[i][j] = Integer.MAX_V ALUE;

}

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

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 + "," + mazeArray[0].length);

star.printPath();

}

/**

* 开始迷宫搜索

public void start() {

while ((currentPoint = 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_V ALUE;

Iterator it = openQueue.iterator();

while (it.hasNext()) {

currentPoint = it.next();

if (FList[currentPoint.getX()][currentPoint.getY()] <= shortestFValue) { shortestFPoint = currentPoint;

shortestFValue = FList[currentPoint.getX()][currentPoint.getY()];

}

if (shortestFValue != Integer.MAX_V ALUE) {

System.out

.println("【移除节点】:" + shortestFPoint.getValue() + "["

+ shortestFPoint.getX() + ","

+ shortestFPoint.getY() + "]");

openQueue.remove(shortestFPoint);

closedQueue.offer(shortestFPoint);

}

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(mazePoint[current_x][current_y],

mazePoint[current_x - 1][current_y]);

}

// 下

if (checkPosValid(current_x + 1, current_y)) {

System.out.print("下");

updatePoint(mazePoint[current_x][current_y],

mazePoint[current_x + 1][current_y]);

}

// 左

if (checkPosValid(current_x, current_y - 1)) {

System.out.print("左");

updatePoint(mazePoint[current_x][current_y],

mazePoint[current_x][current_y - 1]);

}

// 右

if (checkPosValid(current_x, current_y + 1)) {

System.out.print("右");

updatePoint(mazePoint[current_x][current_y],

mazePoint[current_x][current_y + 1]);

}

System.out.println("---------------");

}

/**

* 检查该节点是否有效

private boolean checkPosValid(int x, int y) {

// 检查x,y是否越界，并且当前节点不是墙

if ((x >= 0 && x < mazePoint.length)

&& (y >= 0 && y < mazePoint[0].length)

&& (mazePoint[x][y].getValue() != 1)) {

// 检查当前节点是否已在关闭队列中，若存在，则返回"false"

Iterator it = closedQueue.iterator();

Point point = 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_x = currentPoint.getX();

int current_y = currentPoint.getY();

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

int temp_g = GList[last_x][last_y] + 1;

// 当前节点到目的位置的距离

System.out.print(" [" + current_x + "," + current_y + "]"

+ mazePoint[current_x][current_y].getValue());

int temp_h = getPointDistance(current_x, current_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) 起始节点到当前节点距离

// 2) 当前节点到目的节点的距离

// 3) 起始节点到目的节点距离

if (!openQueue.contains(currentPoint)) {

openQueue.offer(currentPoint);

currentPoint.setFather(lastPoint);

System.out.println("添加到开启列表:" + currentPoint.getValue() + "["

+ currentPoint.getX() + "," + currentPoint.getY() + "]");

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

GList[current_x][current_y] = temp_g;

// 当前节点到目的节点的距离

HList[current_x][current_y] = temp_h;

// f(x) = g(x) + h(x)

FList[current_x][current_y] = temp_f;

} else {

// 如果当前节点在开启列表中存在，并且，

// 从起始节点、经过上一节点到当前节点、至目的地的距离< 上一次记录的从起始节点、到当前节点、至目的地的距离，

// 则：“更新”

// 1) 起始节点到当前节点距离

// 2) 当前节点到目的节点的距离

// 3) 起始节点到目的节点距离

if (temp_f < FList[current_x][current_y]) {

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

GList[current_x][current_y] = temp_g;

// 当前节点到目的位置的距离

HList[current_x][current_y] = temp_h;

// f(x) = g(x) + h(x)

FList[current_x][current_y] = temp_f;

// 更新当前节点的父节点

currentPoint.setFather(lastPoint);

}

System.out.println("currentPoint:" + currentPoint.getValue() + "["

+ currentPoint.getX() + "," + currentPoint.getY() + "]");

System.out.println("currentPoint.father:"

+ currentPoint.getFather().getValue() + "["

+ currentPoint.getFather().getX() + ","

+ currentPoint.getFather().getY() + "]");

}

/**

* 打印行走路径

public void printPath() {

System.out.println("================ 开始打印行走路径【用8 表示】================");

Point father_point = null;

int[][] result = new int[mazeArray.length][mazeArray[0].length];

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

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

result[i][j] = 0;

}

int step = 0;

father_point = mazePoint[endPoint.getX()][endPoint.getY()];

while (father_point != null) {

System.out.println("【father_point】" + father_point.getValue() + "["

+ father_point.getX() + "," + father_point.getY() + "]");

if (father_point.equals(startPoint))

result[father_point.getX()][father_point.getY()] = 2;

else if (father_point.equals(endPoint)) {

result[father_point.getX()][father_point.getY()] = 3;

step++;

} else {

result[father_point.getX()][father_point.getY()] = 8;

step++;

}

father_point = father_point.getFather();

}

// 打印行走步数

System.out.println("step is : " + step);

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

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

System.out.print(result[i][j] + " ");

}

System.out.println();

}

（3）实验结果及分析。

实验结果：

很好的完成了实验目的，并且成功给出了最短路径！！A*算法作为解决最优路径的一种高效算法，自从1968年诞生以来，得到了广泛的应用，而其的多种改进算法也在许多领域发挥着作用。可以预见，在更优的算法发现以前，A*算法将会得到更广泛的应用，并会由于图论、

人工智能、机器人技术、自动控制等多学科的融合而得到更大的发展。

《人工智能基础》实验报告-实验名称：启发式搜索算法

实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求（复述问题）使用启发式算法求解8数码问题（1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n）其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。（2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路八数码问题的求解算法（1）盲目搜索宽度优先搜索算法、深度优先搜索算法（2）启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)

搜索引擎-第二次实验报告

实验二：实验一、实验目的：根据网络爬虫的基本原理，实现一个简易网络爬虫，需要达到以下指标： 1、种子URL为https://www.wendangku.net/doc/9d5291282.html,； 2、至少抓取10000个页面； 3、至少完成3轮抓取，每轮给出更新的URL及其数量； 4、实现ＵＲＬ判重，列出每轮爬去时重复的URL数量； 5、数据存放到数据库中，能抽取出网页中的标题、页面生成日期（http协议中的时间），至少包含标题、时间、url、抓取时间、网页正文这几个字段。二、实验方案： 1.爬虫分析与设计我们组应用的是java来写爬虫，我们应用SSM框架将数据库和应用程序连接起来，可以在程序中更简单的进行数据库插入、查询等操作。在对url处理的时候我们用的是Java的URL类，通过这个类可以获得请求头的一些信息，例如编码方式。如何获取url，我们一开始遇到了一些问题，直接解析网页中的ref 标签的时候得到的不全是网页链接，所以转换思路，我们先得到页面中的标签，然后再得到标签里边href中的url，然后再对url进行处理。在处理url的时候，因为网页中的url并不是全部以http开头的，所以在url获取部分，对url的格式进行判断，如果通常格式就进行修改，例如，有的链接是”#”，我们就把开始搜索的url加到它的前边，形成一个正确的url。

图1：应用URL类获取网页内容图2：利用url请求头获取编码信息图3：获取a标签

图4-1：获取url 图4-2：获取url

图5：url判重 2.数据库分析与设计我们设计了两个表，一个是未爬取url表，两一个是已经爬取url表。未爬取的表中村的是搜索判重之后，还没有爬取的url，已爬取的存储爬取到的信息。图6：判重后需要爬取的url表图7：爬取后url信息存储表