实验一 启发式搜索

启发式搜索实验讲解实验三搜索推理技术启发式搜索算法—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 = newint[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）实验结果及分析。

启发式搜索启发式搜索1. 相关概念在宽度优先和深度优先搜索⾥⾯，我们都是根据搜索的顺序依次进⾏搜索，可以称为盲⽬搜索，搜索效率⾮常低。

⽽启发式搜索则⼤⼤提⾼了搜索效率，由这两张图可以看出它们的差别：什么是启发式搜索（heuristic search）⽤当前与问题有关的信息作为启发式信息，这些信息是能够提升查找效率以及减少查找次数的。

我们定义了⼀个估价函数h(x)。

h(x)是对当前状态x的⼀个估计，表⽰x状态到⽬标状态的距离。

1. h(x) >= 0；2. h(x)越⼩表⽰x越接近⽬标状态；3. 如果h(x) ==0，说明达到⽬标状态。

有了启发式信息还不⾏，还需要起始状态到x状态所花的代价，我们称为g(x)。

g(x)就是我们实际要求解的问题。

⽐如在⾛迷宫问题、⼋数码问题，我们的g(x)就是从起点到 x位置花的步数，h(x)就是与⽬标状态的曼哈顿距离或者相差的数⽬；在最短路径中，我们的g(x)就是起点到x点的最短距离，h(x)就是x点到⽬标结点的最短路或直线距离。

令F(x)=g(x)+h(x)，作为我们的搜索依据。

当F(x) = g(x)的时候就是⼀个等代价搜索，完全是按照花了多少代价去搜索。

⽐如bfs，我们每次都是从离得近的层开始搜索，⼀层⼀层搜；以及dijkstra算法，也是依据每条边的代价开始选择搜索⽅向。

当F(x) = h(x)的时候就相当于⼀个贪婪优先搜索。

每次都是向最靠近⽬标的状态靠近。

⼈们发现，等代价搜索虽然具有完备性，能找到最优解，但是效率太低。

贪婪优先搜索不具有完备性，不⼀定能找到解，最坏的情况下类似于dfs。

这时候，有⼈提出了A算法。

令F(x) = g(x) + h(x)。

（这⾥的h(x)没有限制）。

虽然提⾼了算法效率，但是不能保证找到最优解，不适合的h(x)定义会导致算法找不到解。

不具有完备性和最优性。

⼏年后有⼈提出了A*算法。

该算法仅仅对A算法进⾏了⼩⼩的修改。

并证明了当估价函数满⾜⼀定条件，算法⼀定能找到最优解。

启发式搜索算法心得体会启发式搜索算法是一种通过推测来指导搜索方向的方法，它根据问题的特点和先前的知识进行启发式的搜索，以找到问题的最优解。

在实际应用中，启发式搜索算法被广泛应用于解决各种问题，如求解迷宫、规划路径等。

通过学习和理解启发式搜索算法，我获得了以下几点体会。

首先，启发式搜索算法的核心是启发函数的设计。

启发函数用于评估搜索节点的优劣，以决定搜索的方向。

好的启发函数能够明确指导搜索过程，减少不必要的搜索节点，提高搜索的效率。

在设计启发函数时，我们需要考虑问题的特点和约束条件，合理选择启发函数的评估指标，并通过启发函数的计算方法来优化搜索过程。

其次，启发式搜索算法在问题求解中的表现受到启发函数的影响。

不同的启发函数会导致不同的搜索策略和结果。

因此，在实际应用中，我们需要根据问题的不同特点和求解要求，设计适合的启发函数。

例如，在解决迷宫问题时，可以根据迷宫的布局和目标位置，设计一种启发函数来估计当前节点到目标的距离，以此指导搜索前进的方向。

再次，启发式搜索算法是一种权衡准确性和效率的方法。

通常情况下，启发式搜索算法能够在较短的时间内找到较优解，但并不能保证找到问题的最优解。

这是因为启发式搜索算法通过启发函数进行估计，存在一定的不确定性。

因此，在实际应用中，我们需要根据问题的实际需求，平衡准确性和效率的关系，选择适合的搜索算法和启发函数。

最后，启发式搜索算法是一个不断迭代的过程。

通过不断优化启发函数和搜索策略，我们可以不断改进算法的性能和效果。

在实际应用中，我们可以通过实验和反馈来不断改进启发函数和搜索策略，以逐步提高算法的性能和效果。

此外，启发式搜索算法也可以与其他算法结合使用，形成更加强大和高效的问题求解方法。

总之，通过学习和理解启发式搜索算法，我认识到它在问题求解中的重要性和广泛应用。

通过合理设计启发函数，我们能够明确指导搜索过程，提高搜索效率。

然而，启发式搜索算法也存在一定的局限性，需要在准确性和效率之间进行权衡。

实验报告课程名称人工智能应用技术实验项目启发式搜索程序设计实验仪器Windows/VisualStudio学院信息管理学院专业信息安全班级/学号信安1401/学生姓名Cony实验日期2016-5-17成绩指导教师赵刚北京信息科技大学信息管理学院（课程上机）实验报告5.实验过程：#include<stdio.h>#include<malloc.h>#include<assert.h>//#include "rand.h"#include<stdlib.h>#include<time.h>#define RANDINIT() srand(time(NULL))#define RANDOM() ((float)rand() / (float)RAND_MAX)#define RANDMAX(x) (int)((float)(x)*rand()/(RAND_MAX+1.0))#define MAX_BOARD9#define ALPHA(double)1.0 /* Depth Bias */#define BETA(double)2.0 /* Misplaced Tile Bias */#define MAX_DEPTH26struct board_s;typedef struct board_s {struct board_s *pred;double f;double g;double h;char array[MAX_BOARD];char blank;char depth;} board_t;/* Node Functions */board_t *nodeAlloc( void ){board_t *board_p;board_p = (board_t *)malloc( sizeof(board_t) );assert(board_p);board_p->pred = NULL;board_p->f = board_p->g = board_p->h = (double)0.0;return board_p;}void nodeFree( board_t *board_p ){assert(board_p);free(board_p);return;}/* List Functions */#define MAX_LIST_ELEMENTS100000typedef struct {int numElements;board_t *elements[MAX_LIST_ELEMENTS];} list_t;#define listCount(x) ((x)->numElements)list_t openList_p;list_t closedList_p;void initList( list_t *list_p ){int i;assert(list_p);list_p->numElements = 0;for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) { list_p->elements[i] = (board_t *)0;}return;}int onList( list_t *list_p, char *board_p, int *pos ) {int i, j;assert(list_p); assert(board_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] != (board_t *)0) {for (j = 0 ; j < MAX_BOARD ; j++) {if (list_p->elements[i]->array[j] != board_p[j]) break; }if (j == MAX_BOARD) {if (pos) *pos = i;return 1;}}}return 0;}board_t *getListBest( list_t *list_p ){int i, first=1;int best=-1;double best_f;board_t *board_p;for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i]) {if (first) {best = i;best_f = list_p->elements[best]->f;first = 0;} else {if (list_p->elements[i]->f < best_f) {best = i;best_f = list_p->elements[best]->f;}}}}assert( best != -1 );board_p = list_p->elements[best];list_p->elements[best] = (board_t *)0;list_p->numElements--;return board_p;}board_t *getList( list_t *list_p, char *board_p ) {int pos, ret;board_t *retboard_p = (board_t *)0;assert(list_p); assert(board_p);ret = onList( list_p, board_p, &pos );if (ret) {retboard_p = list_p->elements[pos];list_p->elements[pos] = (board_t *)0;list_p->numElements--;}return retboard_p;}void putList( list_t *list_p, board_t *board_p ) {int i;assert(list_p); assert(board_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] == (board_t *)0) {list_p->elements[i] = board_p;list_p->numElements++;return;}}assert(0);}void cleanupList( list_t *list_p ){int i;assert(list_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] != (board_t *)0) {nodeFree(list_p->elements[i]);list_p->numElements--;}}return;}double evaluateBoard( board_t *board_p ){int i;const int test[MAX_BOARD-1]={1, 2, 3, 4, 5, 6, 7, 8 };int score=0;for (i = 0 ; i < MAX_BOARD-1 ; i++) {score += (board_p->array[i] != test[i]); }return (double)score;}int countInversions( char *array ){int i, j, inversions = 0;for (j = 0 ; j < MAX_BOARD-1 ; j++) {for (i = j+1 ; i < MAX_BOARD ; i++) {if (array[j] > array[i]) inversions++;}}return inversions;}board_t *initPuzzle( void ){int i, inversions;board_t *board_p;board_p = nodeAlloc();for (i = 0 ; i < MAX_BOARD-1 ; i++) {board_p->array[i] = i+1;}board_p->array[i] = 0;do {/* Randomize the board */for (i = 0 ; i < MAX_BOARD ; i++) {int x = RANDMAX(MAX_BOARD);int y = RANDMAX(MAX_BOARD);int temp = board_p->array[x];board_p->array[x] = board_p->array[y];board_p->array[y] = temp;}inversions = countInversions( board_p->array ); } while (inversions & 1);/* Find the blank space (we need to track it) */for (i = 0 ; i < MAX_BOARD ; i++) {if (board_p->array[i] == 0) {board_p->blank = i;break;}}board_p->f = board_p->h = evaluateBoard( board_p );/* Depth is zero -- top of the tree */board_p->depth = 0;return board_p;}void emitPuzzleBoard( board_t *board ){int i;assert(board);for (i = 0 ; i < MAX_BOARD ; i++) {if ((i%3) == 0) printf("\n");if (board->array[i] == 0) printf(" ");else printf("%c", 'A'+board->array[i]-1);}printf("\n");return;}#define MAX_VECTOR 4typedef struct {unsigned int len;unsigned int vector[MAX_VECTOR];} move_t;const move_t moves[MAX_BOARD] = {/* 0 */ { 2, {1, 3} },/* 1 */ { 3, {0, 2, 4} },/* 2 */ { 2, {1, 5} },/* 3 */ { 3, {0, 4, 6} },/* 4 */ { 4, {1, 3, 5, 7} },/* 5 */ { 3, {2, 4, 8} },/* 6 */ { 2, {3, 7} },/* 7 */ { 3, {4, 6, 8} },/* 8 */ { 2, {5, 7} } };board_t *getChildBoard( board_t *board_p, int index ){board_t *child_p = (board_t *)0;int blankSpot;int i;blankSpot = board_p->blank;if (index < moves[blankSpot].len) {int moveFrom;child_p = nodeAlloc();/* Copy board from parent to child */for (i = 0 ; i < MAX_BOARD ; i++) {child_p->array[i] = board_p->array[i];}child_p->blank = board_p->blank;moveFrom = moves[blankSpot].vector[index];child_p->array[ (int)child_p->blank ] = child_p->array[ moveFrom ];child_p->array[ moveFrom ] = 0;child_p->blank = moveFrom;}return child_p;}void showSolution( board_t *goal ){board_t *revList[MAX_LIST_ELEMENTS];int i = 0, j;printf("Solution:\n");while (goal) {revList[i++] = goal;goal = goal->pred;}for (j = i-1 ; j >= 0 ; j--) {emitPuzzleBoard( revList[j] );printf("\n");}return;}void astar( void ){board_t *cur_board_p, *child_p, *temp;int i;/* While items are on the open list */while ( listCount(&openList_p) ) {/* Get the current best board on the open list */ cur_board_p = getListBest( &openList_p );putList( &closedList_p, cur_board_p );/* Do we have a solution? */if (cur_board_p->h == (double)0.0) {showSolution( cur_board_p );return;} else {/* Heuristic - average number of steps is 22 for a 3x3, so don't go * too deep.*/if (cur_board_p->depth > MAX_DEPTH) continue;/* Enumerate adjacent states */for (i = 0 ; i < 4 ; i++) {child_p = getChildBoard( cur_board_p, i );if (child_p != (board_t *)0) {if ( onList(&closedList_p, child_p->array, NULL) ) {nodeFree( child_p );continue;}child_p->depth = cur_board_p->depth + 1;child_p->h = evaluateBoard( child_p );child_p->g = (double)child_p->depth;child_p->f = (child_p->g * ALPHA) + (child_p->h * BETA);/* New child board on the open list? */if ( onList(&openList_p, child_p->array, NULL) ) {assert( !onList(&closedList_p, child_p->array, NULL) );temp = getList(&openList_p, child_p->array);if (temp->g < child_p->g) {nodeFree(child_p);putList(&openList_p, temp);continue;}nodeFree( temp );} else {/* Child board either doesn't exist, or is better than a * previous board. Hook it to the parent and place on the * open list.*/child_p->pred = cur_board_p;putList( &openList_p, child_p );}}}}}return;}int main(){board_t *initial_p;RANDINIT();initList( &openList_p );initList( &closedList_p );initial_p = initPuzzle();putList( &openList_p, initial_p );astar();1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模版供学生使用；2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。

实验一：搜索策略实验一、实验目的1、熟悉和掌握启发式搜索的定义、估价函数和算法过程。

2、利用A*算法求解N数码难题，理解求解流程和搜索顺序。

二、实验内容以八数码为例实现A或A*算法。

1、分析算法中的OPEN表CLOSE表的生成过程。

2、分析估价函数对搜索算法的影响。

3、分析启发式搜索算法的特点。

起始棋局目标棋局启发式函数选取为：f*(n)=g*(n)+h*(n)其中：g*(n)是搜索树中节点n的深度；h*(n)用来计算对应于节点n的数据中错放的棋子个数。

三、实验设计与结果八数码问题是个典型的状态图搜索问题。

搜索方式有两种基本的方式，即树式搜索和线式搜索。

搜索策略大体有盲目搜索和启发式搜索两大类。

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。

所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。

即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

由此解决八数码问题就是在初始状态和目标状态两个状态之间寻找一系列可过渡状态。

利用A*算法实现寻找中间状态，从而得到目标状态。

根据启发式搜索算法A*算法的具体步骤，结合八数码问题的要求，从而得出相应的流程图为：其中：OPEN表：算法已搜索但尚未扩展的节点集合。

CLOSED表：算法已扩展的节点集合。

实验输出结果：运行程序，输入起始棋局与目标棋局：结果输出为：四、程序1、设定启发式函数：八数码问题的目标是要搜索到目标节点，所以为了尽快的向目标节点进行靠近，可以把启发式函数设定为当前节点与目标节点中状态的差异，即与目标节点中数码的位置不同的个数作为启发函数的返回值，然后根据启发函数值找出启发值最小的状态节点进行扩展。

2、OPEN表和CLOSE表的生成过程：OPEN表是用来存放经过扩展得到的待考察的状态节点，CLOSE表是用来存放考察过的状态节点，并且标记上当前节点的编号和父节点的编号，然后可以根据编号便可以形成一个搜索树，即可以找到一个解路径。

人工智能基础实验报告实验名称：八数码问题姓名：张俊学号：2220092333指导老师：邓安生启发式搜索算法1. 实验内容：使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题A *算法，采用估价函数()()()()w n f n d n p n ⎧⎪=+⎨⎪⎩， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的熟练掌握启发式搜索A *算法及其可采纳性。

3. 实验原理八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

4.源代码#include <iomanip>#include <stdlib.h>#include <time.h>#include <iostream>#include <stdio.h>#include <conio.h>#include <math.h>//以上为C++源文件using namespace std;static int space=0;int target[9];class EightNum//定义一个EightNum 类{public:int num[9];int f;//初始状态与目标状态相比，棋子错放个数int deap;//深度int evalfun;//状态的估价值EightNum *parent;//以下为类内成员函数的声明EightNum(int nnum[9]);int get_evalfun();int get_deapfun();void eval_func(int id);int Canspread(int n);void Spreadchild(int n);void getnum(int num1[9]);void setnum(int num1[9]);void show(void);int operator ==(EightNum& NewEightN);int operator ==(int num2[9]);int Shownum();};//-----------------------以下为EightNum类成员函数定义-----------------// class Stack{private:EightNum * eightnum;public:Stack * next;EightNum * Minf();EightNum * Belong(EightNum * suc);void Putinto(EightNum * suc);};EightNum::EightNum(int nnum[9]){//此函数功能为：初始化num[]；for(int i=0;i<9;i++)num[i]=nnum[i];f=0;deap=0;parent=NULL;}int EightNum::get_evalfun(){return evalfun;}int EightNum::get_deapfun(){return deap;}void EightNum::eval_func(int id){//此函数为估价函数int i,qifa;qifa=0;switch(id){case 1:{for(i=0;i<9;i++){if(num[i]!=target[i])qifa++;}break;}case 2:{int j, h1,h2;for(i=0;i<9;i++){for(j=0;j<9;j++){if(num[j]==i)h1=j;if(target[j]==i)h2=j;}qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3)));}break;}case 3:{int j, h1,h2;for(i=0;i<9;i++){for(j=0;j<9;j++){if(num[j]==i)h1=j;if(target[j]==i)h2=j;}qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3)));}qifa=3*qifa;break;}default :break;}f=qifa;if(this->parent==NULL) deap=0;else deap=this->parent->deap+1;evalfun=deap+f;}int EightNum::Canspread(int n){//判断空格"0"可否移动int i,flag = 0;for(i = 0;i < 9;i++)if(this->num[i] == 0)break;switch(n){case 1:if(i/3 != 0)flag = 1;break;case 2:if(i/3 != 2)flag = 1;break;case 3:if(i%3 != 0)flag = 1;break;case 4:if(i%3 != 2)flag = 1;break;default:break;}return flag ;}void EightNum::Spreadchild(int n){//扩展child节点的子节点int i,loc,qifa;for(i = 0;i < 9;i++)this->num[i] = this->parent->num[i];for(i = 0;i < 9;i++)if(this->num[i] == 0)break;if(n==0)loc = i%3+(i/3 - 1)*3;else if(n==1)loc = i%3+(i/3 + 1)*3;else if(n==2)loc = i%3-1+(i/3)*3;elseloc = i%3+1+(i/3)*3;qifa = this->num[loc];this->num[i] = qifa;this->num[loc] = 0;}void EightNum::getnum(int num1[9]){ for(int i=0;i<9;i++)num1[i]=num[i];}void EightNum::setnum(int num1[9]){ for(int i=0;i<9;i++)num[i]=num1[i];}void EightNum::show(){//输出函数for(int i=0;i<9;i++){cout<<num[i]<<" ";if((i+1)%3==0)cout<<"\n";}cout<<"--------------------";}int EightNum::Shownum(){if(this == NULL)return 0;else{int n = this->parent->Shownum();this->show();cout<<endl;return n+1;}}int EightNum::operator ==(EightNum& NewEightN){int compere=1;for(int i=0;i<9;i++)if(num[i]!=NewEightN.num[i]){compere=0;break;}if(compere==0) return 0;else return 1;}//-----------------------以下为分函数的定义---------------------////判断是否有解的函数int solve(int num[9],int target[9]){int i,j;int num_con=0,tar_con=0;for(i=0;i<9;i++)for(j=0;j<i;j++){if(num[j]<num[i] && num[j]!=0)num_con++;if(target[j]<target[i] && target[j]!=0)tar_con++;}num_con=num_con%2;tar_con=tar_con%2;if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1))return 1;elsereturn 0;}EightNum * Stack::Minf(){Stack * qifa =this->next;Stack * min = this->next;Stack * minp = this;EightNum * minx;while(qifa->next != NULL){if((qifa->next->eightnum->get_evalfun()) < (min->eightnum->get_evalfun())){min = qifa->next;minp = qifa;}qifa = qifa->next;}minx = min->eightnum;qifa = minp->next;minp->next = minp->next->next;free(qifa);return minx;}//判断节点是否属于OPEN表或CLOSED表EightNum * Stack::Belong(EightNum * suc){Stack * qifa = this-> next ;if(qifa == NULL)return NULL;while(qifa != NULL){if(suc==qifa->eightnum)return qifa ->eightnum;qifa = qifa->next;}return NULL;}//把节点存入OPEN 或CLOSED 表中void Stack::Putinto(EightNum * suc){Stack * qifa;qifa =(Stack *) malloc(sizeof(Stack));qifa->eightnum = suc;qifa->next = this->next;this->next = qifa;}int BelongProgram(EightNum * suc ,Stack *Open ,Stack *Closed ,EightNum goal,int m ){EightNum * qifa = NULL;int flag = 0;if((Open->Belong(suc) != NULL) || (Closed->Belong(suc) != NULL)){if(Open->Belong(suc) != NULL) qifa = Open->Belong(suc);else qifa = Closed->Belong(suc);flag=1;}else{Open->Putinto(suc);suc->eval_func(m);}return flag;}//扩展后继节点总函数void Spread(EightNum * suc, Stack * Open, Stack * Closed, EightNum goal,int m){int i;EightNum * child;for(i = 0; i < 4; i++){if(suc->Canspread(i+1)){space++;child = (EightNum *) malloc(sizeof(EightNum));child->parent = suc;child->Spreadchild(i);child->eval_func(m);if(BelongProgram(child, Open, Closed, goal,m)) //判断子节点是否属于OPEN或CLOSED表free(child);}}}//执行函数EightNum * Process(EightNum * org, EightNum goal, Stack * Open, Stack * Closed,int m){while(1){if(Open->next == NULL)return NULL;EightNum * minf =Open->Minf();Closed->Putinto(minf);if((*minf)==goal)return minf;Spread(minf, Open, Closed, goal,m);}}//------------------------A*算法搜索函数----------------------//void A(int id,EightNum start,EightNum Target){EightNum * result;space=0;float time;Stack *Open = (Stack *) malloc(sizeof(Stack));Open->next = NULL;Stack *Closed = (Stack *) malloc(sizeof(Stack));Closed->next = NULL;clock_t startt,finisht;startt=clock();//开始时间start.eval_func(id);Open->Putinto(&start);result = Process(&start, Target, Open, Closed,id); //进行剩余的操作cout<<"\n搜索过程:\n"<<result->Shownum()<<endl;finisht=clock();time=(float)(finisht-startt);cout<<endl<<id<<"算法处理结果：所耗时间:";cout<<time;cout<<"ms, ";cout<<"所耗空间:";cout<<space;cout<<"块, "<<endl<<endl;}//-----------------------------主函数-----------------------------//int main(void)//主函数{int i,j;int flag;int num[9];int error;do{error=0;cout<<"请输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开):"<<endl;for(i=0;i<9;i++){flag=0;cin>>num[i];for(j=0;j<i;j++)if(num[j]==num[i])flag=1;if(num[i]<0||num[i]>8||flag==1){error++;}}if(error!=0)cout<<"输入数据错误!请重新输入!"<<endl;}while(error!=0);//输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开）；int error1;do{error1=0;cout<<"请输入新的目标状态(用0代表空格,“棋子”间用空格隔开):"<<endl;for(i=0;i<9;i++){flag=0;cin>>target[i];for(j=0;j<i;j++)if(target[j]==target[i])flag=1;if(target[i]<0||target[i]>9||flag==1){error1++;}}if(error1!=0)cout<<"输入数据错误!请重新输入!"<<endl;}while(error1!=0);//输入八数码问题的目标状态(用0代表空格,中间用空格隔开）；EightNum start(num),Target(target);int m=solve(num,target);//判断初始状态到目标状态是否有解，有解返回1，误解返回0；if(m==0){cout<<"此状态无解!"<<endl;return 0;}int id=0;while(id!=3){cout<<"1. 错放的棋子个数为;\n2.每个棋子与目标位置之间的距离总和为;"<<endl;cout<<"3.结束，退出程序！"<<endl;cout<<"\n请选择功能,分别输入“1”“2”“3”进行选择："<<endl;cin>>id;switch(id){case 1:{cout<<"错放的棋子个数结果为:\n(以下逐一展示搜索过程：)"<<endl;A(1,start,Target);break;}case 2:{cout<<"每个棋子与其目标位置之间的距离总和为:\n(以下逐一展示搜索过程：)"<<endl;A(2,start,Target);break;}default: break;}}cout<<"啊啊….程序结束!!";}实验截图实验中遇到的问题1：开始程序只能运行一种方式即按照错位个数搜索，后经过查找相关资料，修改后可程序可进行选择，两种方法结合在一起根据选择运行。