631306050110董涵+状态空间搜索+启发式搜索.doc

重庆交通大学计算机与信息学院验证性实验报告班 级： 软件开发 专业2013 级1 班 学 号： 631306050110 姓 名： 董涵 实验项目名称：基于空间状态搜索的8数码问题实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 13 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。二、实验内容及要求 在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。三、实验设备及软件 TC2.0 或 VC6.0 编程语言或其它编程语言四、设计方案 题目 基于状态空间搜索的8数码问题 设计的主要思路 主要功能用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索实现8数码难题。5、 主要代码 #include #include Node.h #include Queue.h #include Search.h#include Tree.h void CreateNode1(std:vector& s) s.push_back(2); s.push_back(8); s.push_back(3); s.push_back(1); s.push_back(0); s.push_back(4); s.push_back(7); s.push_back(6); s.push_back(5); void CreateNode4(std:vector& d) d.push_back(2); d.push_back(8); d.push_back(3); d.push_back(1); d.push_back(6); d.push_back(4); d.push_back(7); d.push_back(0); d.push_back(5); void CreateNode8(std:vector& d) d.push_back(0); d.push_back(2); d.push_back(3); d.push_back(1); d.push_back(8); d.push_back(4); d.push_back(7); d.push_back(6); d.push_back(5); void CreateNode20(std:vector& d) d.push_back(2); d.push_back(0); d.push_back(8); d.push_back(1); d.push_back(4); d.push_back(3); d.push_back(7); d.push_back(6); d.push_back(5); void CreateNode27(std:vector& d) d.push_back(1); d.push_back(2); d.push_back(3); d.push_back(8); d.push_back(0); d.push_back(4); d.push_back(7); d.push_back(6); d.push_back(5); void CreateNode_test1(std:vector& d) d.push_back(7); d.push_back(6); d.push_back(5); d.push_back(4); d.push_back(0); d.push_back(1); d.push_back(3); d.push_back(8); d.push_back(2); void test_expand() std:vector s; CreateNode1(s); std:vector d; CreateNode4(d); Node source(s); Node dest(d); source.Display(); Search search(&source); std:cout source.Expand(dest, search); void test_search() std:vector s; CreateNode1(s); std:vector d; CreateNode4(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); void test_search2level() std:vector s; CreateNode1(s); std:vector d; CreateNode8(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); void test_search_lab1() std:vector s;CreateNode1(s); std:vector d; CreateNode27(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); int main(int argc, char* argv) / test_expand(); / test_search(); / test_search2level(); / test_search_lab1(); std:vector s; CreateNode1(s); std:vector d; CreateNode27(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); return 0; Node函数： #include #include #include Node.h bool IsOpposite(OP opa, OP opb) if (LEFT=opa & RIGHT = opb) return true; if (RIGHT=opa & LEFT = opb) return true; if (UP=opa & DOWN = opb) return true; if (DOWN=opa & UP = opb) return true; return false; Node:Node(std:vector const& state) : m_state(state) , m_pParent(NULL) , m_children() , m_op(EMPTY) void ShowOP(OP op) switch (op) case EMPTY: std:cout EMPTY; break; case UP: std:cout UP; break; case DOWN: std:cout DOWN; break; case LEFT: std:cout LEFT; break; case RIGHT: std:cout RIGHT; break; default: exit(-1); void ShowOPs(std:vector const& ops) for (int id=0; idops.size(); +id) ShowOP(opsid); std:cout ; std:cout std:endl; bool Node:Expand(Node const& destNode, Search& search) int spaceId = FindEmptySpaceId(); std:cout space is at spaceId std:endl; std:vector legalOPs = GenerateLegalOperators(spaceId); ShowOPs(legalOPs); while ( legalOPs.size() 0 ) OP op = legalOPs legalOPs.size() - 1 ; legalOPs.pop_back(); Node* pChild = CreateChild(op); if ( *pChild = destNode ) search.SetDestPt(pChild); return true; search.GetQueue().EnQueue(pChild); return false; void Node:Display() const for(int i=0; im_state.size(); +i) std:cout m_statei ; Queue& GetQueue() return m_queue; void Find(Node* destNode); Node* Select(); void SetDestPt(Node* pDestNode) m_pDestNode = pDestNode; void DisplayRoute() const; private: Queue m_queue; Node* m_pDestNode; ; #endif / PROGECT_1_SEARCH Tree： #ifndef PROGECT_1_TREE #define PROGECT_1_TREE #endif / PROGECT_1_TREE六、测试结果及说明 七、实验体会人工智能这门课让我学到了很多有趣的东西，这次的实验让我对人工智能也有了一些了解，今后想要了解时会更加轻松。重庆交通大学计算机与信息学院验证性实验报告班 级： 计算机软件开发专业 2013级1班 学 号： 631306050110 姓 名： 董涵 实验项目名称： 启发式搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼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=Start-board.d+pick(Start);break; Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/将S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best