人工智能实验 旅行商问题 启发式搜索

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

智能优化实验报告基于遗传算法的TSP问题求解研究一、问题描述1、TSP问题的概述旅行商问题 (Traveling Salesman Problem，简称 TSP) 是一个经典的组合化问题。

它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城出发需要经过所有城市后回到出发地，应如何选择行进路线以使总行程短。

从图论的角度看，该问题实质是在一个带权完全无向图中找一个权值最的小回路。

在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。

旅行商问题也是经典的组合数学的问题，生活中随处可见这类组合数学问题。

例如，计算下列赛制下的总的比赛次数:n个球队比赛，每队只和其他队比赛一次。

在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，一笔画出网络图。

一个邮递员从邮局出发，要走完他所管辖的街道，他应该选择什么样的路径，这就是著名的“中国邮递员问题”。

一个通调网络怎样布局最节省?美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。

库房和运输的管理也是典型的组合数学问题，怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取。

上述的这些例子中，其中一部分就和旅行商问题有关系。

2、TSP问题研究意义解决旅行商问题有着极其重要的理论和现实意义。

从理论层面来讲，解TSP不仅为其他算法提供了思想方法平台，使这些算法广泛地应用于各种组合优化问题；而且经常被用来测试算法的优劣，如模拟退火算法、禁忌搜索、神经网络、进化算法等，都可用旅行商问题来测试。

从实际应用层面来讲，旅行商问题作为一个理想化的问题，尽管多数的研究成果不是为了直接的应用，但却被广泛地转化为许多组合优化问题，最直接的就是其在交通、物流和大规模生产中的应用。

3、TSP问题的解决TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。

人工智能概论大作业学院：电子工程学院专业：智能科学与技术题目一：搜索算法编程及实验报告一．算法题目八数码难题的求解。

二．实验目的从盲目搜索和启发式搜索方法中分别选择一种解决八数码难题，给出搜索树和从起始节点到目标节点的路径。

三．实验设备及软件环境Win7的笔记本电脑，VS2013（使用c语言编程）。

四．实验方法1.盲目搜索——宽度优先搜索。

（1）.算法描述如果搜索是以接近其实节点的程度来依次扩展节点，那么这中搜索就叫宽度优先搜索。

这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

(1）把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。

（2）如果OPEN是个空表，则没有解，失败退出；否则继续。

（3）把第一个节点（节点 n）从OPEN表移出，并把它放入CLOSED扩展节点表中。

（4）扩展节点n。

如果没有后继节点，则转向上述第（2）步。

（5）把n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。

（6）如果n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（2）步。

（2）.算法流程图（3）.程序代码#include "stdio.h"#include "conio.h"#include "string.h" struct pic{char data[10];char imoperate;int father;char extend; };char end[10] = "1238 4765";int result[100];int n;int m;pic base[100];char *w;int find(int x){for (int i = 0; i < 10; i++)if (base[x].data[i] != end[i])return 0;return 1;}void showline(int x){int i = 0;while (base[x].father != -1){result[i] = x;x = base[x].father;i++;}result[i] = 0;result[i + 1] = '\0';m = i;printf("\n搜索路径");for (i = m; i >= 0; i--){printf("\n\n\n");printf("%c\t%c\t%c\n", base[result[i]].data[0], base[result[i]].data[1], base[result[i]].data[2]);printf("%c\t%c\t%c\n", base[result[i]].data[3], base[result[i]].data[4], base[result[i]].data[5]);printf("%c\t%c\t%c", base[result[i]].data[6], base[result[i]].data[7], base[result[i]].data[8]);}}int left(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 3 || i == 6)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i] = base[x].data[i - 1];base[n].father = x;base[n].imoperate = 'R';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int right(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 2 || i == 5 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 1] = base[x].data[i];base[n].father = x;base[n].imoperate = 'L';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int up(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 1 || i == 2)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i - 3] = base[x].data[i];base[n].data[i] = base[x].data[i - 3];base[n].father = x;base[n].imoperate = 'D';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int down(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] ==' ')break;if (i == 6 || i == 7 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 3] = base[x].data[i];base[n].data[i] = base[x].data[i + 3];base[n].father = x;base[n].imoperate = 'U';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}void main(){void showtree(int x);n = 1;int i;strcpy_s(base[0].data, "2831 4765");base[0].imoperate = 'N';base[0].father = -1;base[0].extend = 'Y';for ( i = 0; i < 100; i++){if (base[i].extend == 'Y'){if (base[i].imoperate == 'L'){if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'R') {if (left(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'U') {if (left(i) == 1)break;if (right(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'D') {if (right(i) == 1)break;if (up(i) == 1)break;if (left(i) == 1)break;continue;}if (base[i].imoperate == 'N') {if (left(i) == 1)break;if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}}}printf("搜索结束\n");showline(n - 1);showtree(n - 1);getchar();}void showtree(int x){printf("\n\n\n搜索树\n\n\n");int i;for (i = 0; i <= x; i++){if (i == 0){printf("\t\t\t %c%c%c\n", base[i].data[0], base[i].data[1], base[i].data[2]);printf("\t\t\t %c%c%c\n", base[i].data[3], base[i].data[4], base[i].data[5]);base[i].data[7], base[i].data[8]);printf("\t\t\t |\n");printf(" ");for (int j = 0; j < 49; j++)printf("-");printf("\n");printf(" |");printf(" |");printf(" |");printf(" |\n");continue;}if (i>0 && i <= 4){printf(" %c%c%c", base[i].data[0],base[i].data[1], base[i].data[2]);printf("\t %c%c%c", base[i+1].data[0], base[i+1].data[1], base[i+1].data[2]);printf("\t %c%c%c", base[i+2].data[0], base[i+2].data[1], base[i+2].data[2]);printf("\t %c%c%c\n", base[i+3].data[0], base[i+3].data[1], base[i+3].data[2]);printf(" %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);base[i+1].data[4], base[i+1].data[5]);printf("\t %c%c%c", base[i+2].data[3], base[i+2].data[4], base[i+2].data[5]);printf("\t %c%c%c\n", base[i+3].data[3], base[i+3].data[4], base[i+3].data[5]);printf(" %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);printf("\t %c%c%c", base[i+1].data[6], base[i+1].data[7], base[i+1].data[8]);printf("\t %c%c%c", base[i+2].data[6], base[i+2].data[7], base[i+2].data[8]);printf("\t %c%c%c\n", base[i+3].data[6], base[i+3].data[7], base[i+3].data[8]);printf(" |");printf(" |");printf(" |");printf(" |\n");printf(" ---------");printf(" ---------");printf(" ---------");printf(" ---------\n");printf(" | |");printf(" | |");printf(" | |");printf(" | |\n");i = 4;continue;}if (i > 4 && i <= 12){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i+j].data[0],base[i+j].data[1], base[i+j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");i = 12;continue;}if (i > 12 && i <= 20){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");printf(" -----");for (int j = 0; j < 7;j++)printf(" -----");printf("\n | |");for (int j = 0; j < 7; j++)printf(" | |");i = 20;continue;}if (i>20 && i <= 36){printf("\n%c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n%c%c%c", base[i].data[3], base[i].data[4], base[i].data[5]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n%c%c%c", base[i].data[6], base[i].data[7], base[i].data[8]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);i = 36;continue;}}}2.启发式搜索——有序搜索（1）算法描述有序搜索又称最好优先搜索，他总是选择最有希望的节点作为下一个要扩展的节点。

第五章搜索策略习题参考解答5.1 练习题5.1 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？5.2 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优解？最优解唯一吗？5.3 请写出状态空间图的一般搜索过程。

在搜索过程中OPEN表和CLOSE表的作用分别是什么？有何区别？5.4 什么是盲目搜索？主要有几种盲目搜索策略？5.5 宽度优先搜索与深度优先搜索有何不同？在何种情况下，宽度优先搜索优于深度优先搜索？在何种情况下，深度优先搜索优于宽度优先搜索？5.6 用深度优先搜索和宽度优先搜索分别求图5.10所示的迷宫出路。

图5.10 习题5.6的图5.7 修道士和野人问题。

设有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到河的右岸去。

但该船每次只能装载两个人，在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会被野人吃掉。

假设野人服从任何一种过河安排，请使用状态空间搜索法，规划一使全部6人安全过河的方案。

（提示：应用状态空间表示和搜索方法时，可用(N m,N c)来表示状态描述，其中N m和N c分别为传教士和野人的人数。

初始状态为(3,3)，而可能的中间状态为(0,1),(0,2),(0,3), (1,1),(2,1),(2,2),(3,0),(3,1),(3,2)等。

）5.8 用状态空间搜索法求解农夫、狐狸、鸡、小米问题。

农夫、狐狸、鸡、小米都在一条河的左岸，现在要把它们全部送到右岸去。

农夫有一条船，过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样。

狐狸要吃鸡，鸡要吃小米，除非农夫在那里。

试规划出一个确保全部安全的过河计划。

（提示：a.用四元组(农夫，狐狸，鸡，米)表示状态，其中每个元素都可为0或1，0表示在左岸，1表示在右岸；b.把每次过河的一种安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。

）5.9 设有三个大小不等的圆盘A 、B 、C 套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态S 0和目标状态S g 如图5.11所示，用宽度优先搜索法和深度优先搜索法求从S 0到S g 的路径。

启发式搜索名词解释,每个小标题不低于500字《启发式搜索名词解释》一、定义启发式搜索（Heuristics Search）是一种在计算机科学中广泛使用的搜索算法，它允许计算机使用启发式（如得分函数、近似值或盲目的）信息，以优化给定的搜索空间。

它是有用的在离散搜索空间，如游戏，环境下，因为有效的方法来解决搜索空间。

许多计算机科学领域都使用启发式搜索，例如，机器人控制，分布式搜索，推荐系统和自动计算机解析。

启发式搜索的设计是以当前最佳的情况和最全面的视角结合。

它既可以用于解决困难的问题也可以用于找到最优化的解决方案。

在某些情况下，决策者可能不想等待精确解决方案，只需要有一个基本准确，能够接受的解决方案即可，此时启发式搜索就可以发挥作用。

二、启发式搜索算法启发式搜索算法是搜索过程中一解决问题的有效策略，需要考虑不同路径及其代价，以便在算法运行的过程中不断优化。

他使用的是启发式的提示，即使用一种外部的知识来完成任务，而不是系统地搜索认知空间。

例如搜索过程的启发式准则可以是最小代价原则，即树的深度少的路径比深的优先；最大价值原则，即从树深度里估计到达最终目标容易程度；优先发现原则，即对已知状态下可行解空间里最可靠的解进行搜索；以及回溯法，即回溯，把搜索树搜索过程中当前最优状态保存，以便在最后可以得到最量化的最优解。

三、应用启发式搜索在多个研究领域中有着广泛的应用，从规划和自然语言理解到视觉，启发式搜索已经是一种解决问题的标准技术。

例如，在人工智能领域，启发式搜索可以帮助人类更好地理解其自身有限的能力，并能够有效地利用现有的信息来为给定解决方案找到更佳的解决方案。

此外，启发式搜索也被用于物流优化、交通系统调整、医疗领域的数据分析、推荐系统等，是大数据背后运行的一种数据分析和优化技术。

总之，启发式搜索是一种非常有用的算法，其主要目的是通过搜索问题的空间以找到最优的解决方案，它被广泛用于搜索优化，数据分析，推荐系统等多个领域，不仅有助于在计算上更好地求解问题，也有助于提高最终解决方案的准确率。

91、实验题目人工智能实验报告——旅行商问题旅行商问题：从某个城市出发，每个城市只允许访问一次，最后又回到原来的城市， 寻找一条最短距离的路径。

请定义两个h 函数（非零），讨论这两个函数是否都在h*的下界范围，是否满足单调限制？你认为哪个会产生比较有效的搜索？2、实验目的及要求旅行商问题是图论中的一个重要的经典问题，本次实验要求学生要求自行定义两个h 函数（非零），独立编写程序解决旅行者问题，语言不限，工具不限，独立完成实验报告。

通过本次实验，使学生加深对图搜索策略的理解和认识，对启发式搜索、估价函数有更深入的理解认识，并学会灵活掌握及解决实际问题。

3、实验设备装有Office 软件的微机一台，本次实验使用Visual studio 6.0开发环境4、实验内容本实验首先对旅行商问题进行了学习了解，之后结合人工智能课堂内容，设计了两个h 函数，使用C 语言编写实现。

具体说明及步骤如下。

4.1、旅行商问题旅行商问题是图论中的一个重要的经典问题: 任给一个城市与城市间的道路图, 求一个旅行商访问每个城市并回到出发点的最短路程。

如本实验中, 城市间均有道路的五个城市的地图可以表示成下面的图1:B7 A7 10 10 6 13 10 CE56D图1 城市间均有道路的五个城市的地图在旅行商的地图中, 五个城市用节点表示, 两城市间的距离用弧线上的数字表示。

设旅行商从A 城市出发, 到B、C、D、E 等城市去推销商品, 要寻找一条从A 出发, 包括B、C、D、E, 且仅包含一次, 最后回到A 的一条最短路径。

4.2、A*算法A* 算法是N.Nillson于1971年提出的一种有序搜索算法, 该算法被认为是求解人工智能问题的最成功的技术理论之一。

Nillson指出对于某一已到达的现行状态, 如已到达图中的n节点, 它是否可能成为最佳路径上的一点的估价, 应由估价函数f(n)值来决定。

假设g*(n)函数值表示从起始节点s 到任意一个节点n 的一条最佳路径上的实际耗散值。

实验报告姓名：***学号：**********班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：2015.11.09实验环境：Visual C++实验目的以及内容：1、实验内容：使用启发式搜索算法求解八数码问题。

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

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

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

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

代码：#include"stdio.h"#define num 3void show(int begin[num][num]){for(int i = 0; i < num; i++){for(int j = 0; j < num; j++)printf("%d ", begin[i][j]);printf("\n");}printf("\n");}void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two){int temp;temp = begin[row_two][column_two] ;begin[row_two][column_two] = begin[row_one][column_one];begin[row_one][column_one] = temp;}int judge(int begin[num][num], int end[num][num]){int count=0;for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){if(begin[i][j] == end[i][j] && end[i][j] != 0)count++;}return count;}int yidong(int begin[num][num], int end[num][num], int right, int jishu, int ji_shu[50][3][3], int biaoji, int row, int column){int temp_zhi;show(begin);if(jishu >= 20)return 0;int node;int temp;for(int q=0; q<jishu; q++){node = 1;for(int w=0; w<num && node; w++)for(int r=0; r<num && node; r++)if(ji_shu[q][w][r] != begin[w][r])node = 0;if(node == 1){return 0;}}for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)ji_shu[jishu][i][j] = begin[i][j];if(right == num * num - 1)return 1;if(row > 0 && biaoji != 0){exchange(begin, row - 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row - 1, column, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column);if( temp_zhi == 1)return 1;exchange(begin, row - 1, column, row , column);}}if(column > 0 && biaoji != 1){exchange(begin, row, column - 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column - 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column -1);if(temp_zhi == 1)return 1;exchange(begin, row, column - 1, row , column);}}if(row < num-1 && biaoji != 2){exchange(begin, row + 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row + 1, column, row , column);else if(temp >= right){temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column);if(temp_zhi == 1)return 1;exchange(begin, row + 1, column, row , column);}}if(column < num-1 && biaoji != 3){exchange(begin, row, column + 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column + 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1);if(temp_zhi == 1)return 1;exchange(begin, row, column + 1, row , column);}}return 0;}void shuru(int begin[][num],int blank[]){int temp, node, zero = 0;for (int i = 0; i < num; i++)for(int j = 0; j < num; j++){node = 1;printf("请输入第%d行，第%d列的元素的值：", i+1, j+1);scanf("%d", &temp);for (int q = 0; q <= i && node == 1; q++)for (int w = 0; w < j; w++)if(temp == begin[q][w]){printf("输入重复，请重新输入\n");node = 0;j--;break;}if(temp < 0 || temp > num*num-1){printf("请输入从%d到%d的数\n", zero, num*num-1);node = 0;j--;}if(node == 1){if(temp == 0){blank[0] = i;blank[1] = j;}begin[i][j] = temp;}}}int main(){int jishu = 0, ji_shu[50][3][3];int row;int column;int begin[num][num], blank[2],count=1;int end[num][num] = {1, 2, 3, 8, 0, 4, 7, 6, 5};printf ("-------8数码游戏开始！--------\n");shuru(begin, blank);row = blank[0];column = blank[1];if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) == 0)printf("\n此8数码的问题可能无解！");elseshow(begin);getchar();getchar();return 0;}实验截图：实验总结：1、A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n) ≤h*(n)。

启发式搜索实验报告2015-2016第1学期《人工智能基础》实验报告实验名称:启发式搜索算法专业班级学号姓名1、实验环境Visual C++ 6.02、实验目的和要求(复述问题)使用启发式算法求解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 / 112015-2016第1学期《人工智能基础》实验报告其中A*算法中的g(n)根据具体情况设计为d(n)，意为n节点的深度，而h(n)设计为p(n)，意为放错的数码与正确的位置距离之和。

人工智能实验报告-八数码（五篇模版）第一篇：人工智能实验报告-八数码《人工智能》实验一题目实验一启发式搜索算法1.实验内容：使用启发式搜索算法求解8数码问题。

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

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

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

3.数据结构与算法设计该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：typedef struct Node//棋盘 {//节点结构体int data[9];double f,g;struct Node * parent;//父节点}Node,*Lnode;int data[9];数码数组：记录棋局数码摆放状态。

struct Chess * Parent;父节点：指向父亲节点。

下一步可以通过启发搜索算法构造搜索树。

1、局部搜索树样例：*2、搜索过程搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。

搜索过程如下：（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。

现存在的一些优缺点。

1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N 数码问题的求解过程。

最小比率旅行商问题的引力搜索算法求解最小比率旅行商问题是指对于一组点，求解一条路径使得经过所有点恰好一次，并且路径上的边中最大边权最小。

这是一个NP-hard问题，因此需要用启发式算法来求解。

引力搜索算法（GSA）是一种基于距离公式的启发式搜索算法，在解决TSP问题中被证明具有较好的性能。

1. 算法描述1）初始化粒子数量和每个粒子的位置和速度。

2）计算每个粒子到目标点集合的距离，并计算粒子之间的相对距离。

3）根据质量和距离计算每个粒子的浮力和引力。

4）计算每个粒子的总力和新速度，更新位置。

5）比较新位置的最小边权，并更新全局最优位置。

2. 算法实现对于最小比率旅行商问题，目标点集合中的每个点可以表示为一个空间中的点。

粒子群可以理解为一个移动的“云”，在搜索空间中不断漂浮，并搜寻全局最优解。

在搜索的过程中，每个粒子的位置表示了搜索路径的一个候选解。

引力搜索算法通过计算每个粒子之间的相对距离和质量，来模拟粒子间的相互作用和引力变化，从而跟进最优解。

由于算法使用了质量、距离等多个因素的综合作用，因此能够获得较高的搜索精度与鲁棒性。

3. 算法优势引力搜索算法相对于其他启发式算法的优势体现在以下几个方面：1）采用了多因素综合考虑的方式，增加了搜索算法的鲁棒性。

2）图论问题中，粒子群算法能够在一定程度上降低搜索的维度，从而使得计算量更小。

3）在管理全局的搜索质量方面，PSO 的全局最优点更新迭代速度相对比较慢，而引力搜索算法在这方面变化更灵活。

4. 实验分析本文采用引力搜索算法求解全国31个城市的TSP问题。

实验结果表明，引力搜索算法与其他启发式算法相比较的精度和效率都比较理想。

并且，最小比率旅行商问题求解流程较为简单，运算速度较快，算法的可行性也得到了验证。

总的来讲，引力搜索算法可作为一种有效的解决方案，应用于经典TSP问题的求解中。