631306050113程强+状态空间搜索+启发式搜索.doc

重庆交通大学计算机与信息学院验证性实验报告班 级： 计算机软件开发专业 2013级1班 学 号： 631306050113 姓 名： 程强 实验项目名称： 状态空间搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 13 日评阅意见：实验成绩： 签名： 年 月 日一、 实验目的1. 理解和掌握状态空间搜索的策略。二、实验内容及要求1实验内容：在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。2实验要求：用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）三、实验设备及软件 一台PC，Java四、设计方案 题目 状态空间搜索 设计的主要思路状态空间法 建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中 建立CLOSED表，且置为空表 判断OPEN表是否为空表，若为空，则问题无解，退出 选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表将此节点记为节点n 考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转 扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中 对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点, 设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过，并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。 按某一任意方式或某种策略重排OPEN表中节点的顺序 转宽度优先搜索算法 (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。深度优先搜索算法 (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。 (4) 考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出 (5)如果没有后继节点，则转向上述第(2)步。 (6) 扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。 主要功能通过一系列的数码移动，讲初始位置转化为目标位置五、主要代码package .nwsuaf.qhs.artificialintelligence.eightpuzzle;import java.util.Arrays;public class EightPuzzle implements Cloneable/*利用一个二维的数组来存储数据*/public int data;private int blankPos_x,blankPos_y;private int depth;/无参构造函数public EightPuzzle()data = new int33;/传递一个数组，进行初始化的构造函数public EightPuzzle(int data)this.data = data;/判断是不是和目标位置相同/*int data1 = new int1,2,3,4,5,6,7,8,9;int data2 = new int1,2,3,4,5,6,7,8,9;System.out.println(Equals-+Arrays.equals(data1, data2); falseSystem.out.println(deepEquals-+Arrays.deepEquals(data1, data2); true*/public boolean isEquals(EightPuzzle ep)return Arrays.deepEquals(this.data, ep.data);public String toString()StringBuffer sb = new StringBuffer(20);for (int i = 0; i 3; i+)for (int j = 0; j 3; j+)sb.append(this.dataij);sb.append( );return sb.toString();/ 获取空格的位置public void getPostion() for (int i = 0; i 3; i+) for (int j = 0; j 3; j+) if (this.dataij = 0) this.setBlankPos_x(i);this.setBlankPos_y(j);public void setBlankPos_x(int blankPos_x) this.blankPos_x = blankPos_x;public void setBlankPos_y(int blankPos_y) this.blankPos_y = blankPos_y;public int getBlankPos_x() return blankPos_x;public int getBlankPos_y() return blankPos_y;public int getDepth() return depth;public void setDepth(int depth) this.depth = depth;public void print()System.out.println(this.toString();/浅拷贝Overrideprotected EightPuzzle clone() throws CloneNotSupportedException / TODO Auto-generated method stubreturn new EightPuzzle(Arrays.copyOf(this.data, this.data.length);/深拷贝public EightPuzzle depthClone()EightPuzzle tmp_ep = new EightPuzzle();for (int i = 0 ; i 3; i+)for (int j = 0 ; j 3; j+)tmp_ep.dataij = this.dataij;tmp_ep.depth = this.depth;return tmp_ep;public static void main(String args) Overridepublic boolean equals(Object obj) / TODO Auto-generated method stubreturn this.isEquals(EightPuzzle)obj);/&(this.getDepth() = (EightPuzzle)obj).getDepth()package .nwsuaf.qhs.artificialintelligence.eightpuzzle;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Stack;public class EightPuzzleAlgorithm private int array = new int33;private int target = new int33;private EightPuzzle ep, target_ep;private int depth = 0;private Stack ep_stack = new Stack();private LinkedList searched_list = new LinkedList();private Queue ep_queue = new LinkedList();public EightPuzzleAlgorithm() / 初始化栈和队列，以及列表ep_stack.clear();searched_list.clear();ep_queue.clear();Scanner scanner = new Scanner(System.in);/ 输入初始位置System.out.println(请输入初始位置（其中输入0代表空白块，例如：2 8 3 1 0 4 7 6 5）：);for (int i = 0; i 3; i+) for (int j = 0; j 3; j+) arrayij = scanner.nextInt();/ 输入目标位置System.out.println(请输入目标位置（其中输入0代表空白块，例如：2 8 3 1 4 0 7 6 5）：);for (int i = 0; i 3; i+) for (int j = 0; j _%);/ 深度优先搜索(有界，最大深度为5)/ 栈的方式实现搜索public void boundedDepthFirstSearch() System.out.println(有界深度优先搜索方法路径！);if (!searched_list.isEmpty()searched_list.clear();while (!ep_stack.isEmpty() EightPuzzle move_ep = ep_stack.pop();depth = move_ep.getDepth();move_ep.getPostion();int x = move_ep.getBlankPos_x(), y = move_ep.getBlankPos_y();move_ep.print();searched_list.add(move_ep);if (move_ep.isEquals(target_ep) System.out.println(终于找到了，b汗);return;if (depth _%);/*public void search() / this.getPostion();/ this.depthFirstSearch(blankPos_x, blankPos_y, 1);this.depthFirstSearch();this.boundedDepthFirstSearch();this.breadthFirstSearch();*/* * param args */public static void main(String args) / TODO Auto-generated method stubEightPuzzleAlgorithm epa = new EightPuzzleAlgorithm();epa.depthFirstSearch();epa.boundedDepthFirstSearch();epa.breadthFirstSearch();六、测试结果及说明【实验测试结果】测试中的一组数据：请输入初始位置（其中输入0代表空白块，例如：2 8 3 1 0 4 7 6 5）：2 8 3 1 0 4 7 6 5请输入目标位置（其中输入0代表空白块，例如：2 8 3 1 4 0 7 6 5）：2 8 3 1 4 0 7 6 5深度优先搜索：深度优先搜索方法路径！2 8 3 1 0 4 7 6 5 2 8 3 0 1 4 7 6 5 2 8 3 7 1 4 0 6 5 2 8 3 7 1 4 6 0 5 2 8 3 7 1 4 6 5 0 2 8 3 7 1 0 6 5 4 2 8 3 7 0 1 6 5 4 2 8 3 0 7 1 6 5 4 2 8 3 6 7 1 0 5 4 2 8 3 6 7 1 5 0 4 2 8 3 6 7 1 5 4 0 2 8 3 6 7 0 5 4 1 2 8 3 6 0 7 5 4 1 2 8 3 0 6 7 5 4 1 2 8 3 5 6 7 0 4 1 2 8 3 5 6 7 4 0 1 2 8 3 5 6 7 4 1 0 2 8 3 5 6 0 4 1 7 2 8 3 5 0 6 4 1 7 2 8 3 0 5 6 4 1 7 2 8 3 4 5 6 0 1 7 2 8 3 4 5 6 1 0 7 2 8 3 4 5 6 1 7 0 2 8 3 4 5 0 1 7 6 2 8 3 4 0 5 1 7 6 2 8 3 0 4 5 1 7 6 2 8 3 1 4 5 0 7 6 2 8 3 1 4 5 7 0 6 2 8 3 1 4 5 7 6 0 2 8 3 1 4 0 7 6 5 有界深度优先搜索：有界深度优先搜索方法路径！2 8 3 1 0 5 7 4 6 0 8 3 2 4 5 1 7 6 2 8 3 4 7 5 1 0 6 2 0 3 4 8 5 1 7 6 2 8 0 4 5 3 1 7 6 2 8 3 4 0 6 1 5 7 0 8 3 2 5 6 4 1 7 2 8 3 5 1 6 4 0 7 2 0 3 5 8 6 4 1 7 2 8 0 5 6 3 4 1 7 2 8 3 5 0 7 4 6 1 0 8 3 2 6 7 5 4 1 2 8 3 6 4 7 5 0 1 2 0 3 6 8 7 5 4 1 2 8 0 6 7 3 5 4 1 2 8 3 6 0 1 5 7 4 0 8 3 2 7 1 6 5 4 2 8 3 7 5 1 6 0 4 2 0 3 7 8 1 6 5 4 2 8 0 7 1 3 6 5 4 2 8 3 7 0 4 6 1 5 0 8 3 2 1 4 7 6 5 2 8 3 0 1 4 7 6 5 2 8 3 7 1 4 0 6 5 2 8 3 1 0 4 7 6 5 0 8 3 2 1 4 7 6 5 8 0 3 2 1 4 7 6 5 0 8 3 2 1 4 7 6 5 8 1 3 2 0 4 7 6 5 8 3 0 2 1 4 7 6 5 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 0 7 5 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 0 7 5 2 8 3 1 6 4 7 5 0 2 8 3 0 6 4 1 7 5 2 8 3 1 6 4 0 7 5 2 8 3 6 0 4 1 7 5 0 8 3 2 6 4 1 7 5 2 8 3 1 6 4 7 5 0 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 0 7 5 2 8 3 1 6 0 7 5 4 2 8 3 1 0 6 7 5 4 2 8 0 1 6 3 7 5 4 2 8 3 1 0 4 7 6 5 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 0 7 5 2 8 3 1 4 0 7 6 5 广度优先搜索：广度优先搜索方法路径！2 8 3 1 0 4 7 6 5 2 0 3 1 8 4 7 6 5 2 8 3 1 4 0 7 6 5 七、实验体会本次实验比较麻烦，遇见了很多问题。查询了很多资料，用Java利用图的搜素算法深度优先搜索、广度优先搜索、有界深度优先搜索三种算法完成八数码问题的求解，利用Java程序设计语言编程，过程中遇到了诸多问题，以前太注重算法这一块的练习，实验中，每一块都是自己努力完成，也解决了遇到的问题，所以还是很有收获的。重庆交通大学计算机与信息学院验证性实验报告班 级： 计算机软件开发专业 2013级1班 学 号： 631306050113 姓 名： 程强 实验项目名称： 启发式搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 13 日评阅意见：实验成绩： 签名： 年 月 日二、 实验目的理解和掌握A*算法二、实验内容及要求1实验内容：在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。 2实验要求：用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）三、实验设备及软件 一台PC，VC6+四、设计方案 题目 启发式搜索 A*算法 设计的主要思路搜索策略启发式搜索技术（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2） 估价函数计算一个节点的估价函数，可以分成两个部分：1、 已经付出的代价（起始节点到当前节点）；2、 将要付出的代价（当前节点到目标节点）。节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 = + 。是从初始节点到达当前节点n的实际代价； 是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。算法Begin：读入初始状态和目标状态，并计算初始状态评价函数值f；根据初始状态和目标状态，判断问题是否可解；If(问题可解)把初始状态假如open表中；While（未找到解&状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；End whileEnd if输出结果；End五、主要代码#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/记录0的位置，zero0:r行；zero1:c列 typedef int Piece;struct Chessboard/棋盘信息 Piece posNN;/记录每个数码a的位置r行c列int d,f,move;/d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1:/向左移，不能出界：zero1=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 数 码 问 题 求 解n); printf(n请输入初始状态：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盘状态：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close); printf(A*算法:); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=St