《人工智能：基于图搜索策略求解八数码问题的最优路径.docx》由会员分享，可在线阅读，更多相关《人工智能：基于图搜索策略求解八数码问题的最优路径.docx（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能大作业 学 院 电子工程学院专 业 智能科学与技术学 号 姓 名 第一部分：八数码难题基于图搜索策略求解八数码问题的最优路径一、 问题简介 八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如
2、何移动将牌，实现从初始状态到目标状态的转变。 1 2 38 47 6 52 8 31 6 47 5 初始节点 目标节点二、 基于图搜索问题的搜索方法 图搜索是人工智能的核心技术之一，人工智能的许多分支领域都涉及到图搜索。我们可以把图搜索看成是一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库，求得把一个数据库变换成另一个数据库的规则序列问题就等价于求的图中的一条路径问题。 图搜索一般过程： （1）建立一个只含有其实节点S的搜索图G，建立一个OPEN表，它只含有 初始节点S。 （2）建立一个表CLOSED，它的初始状态为空。 （3）LOOP：若OPEN为空，则失
3、败退出。 （4）选择OPEN表中第一个节点，将其放入CLOSED表，称此节点为节点n。 （5）如果n 属于目标集（目标节点），则有解并成功退出 ，则沿着G中n 到s的指针得出一条路径，并以此返回（指针在步骤7建立）。 （6）扩展节点n，建立集合M，使M仅含有n的后继者，而不含有n的祖先， 并把M中的节点作为n的后继者加入到G中。 （7）对M中原来不在G中的节点（即不在OPEN表中也不在CLOSED表中） 建立一个从这些节点到n的指针，并把它们加入到表OPEN中。 对已经在OPEN或CLOSED表上的每一个成员M，确定是否更改通到n 的指针方向。 对于已在CLOSED表上的每个M成员，确定是否应
4、该改变图G中通向它 的每个后裔节点的指针方向。 （8）按某种方式，对OPEN表中的节点重新排序。 （9）GO LOOP。图搜索的一般方法： 三、求解八数码难题的两种算法3.1 广度优先搜索 广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。 步骤步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺 序编号n；步4 若目标节点Sg=N，则搜索成功，结束。步5 若
5、N不可扩展，则转步2；步6 扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN 表的尾部，转步2。 广度优先搜索亦称为宽度优先或横向搜索。这种策略是完备的，即如果问题的解存在，用它则一定能找到解，且找到的解还是最优解（即最短的路径）。这是优点，缺点是搜索效率低。宽度优先搜索流程图： 图1 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展个结点和生成个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。 图23.2 启发式图搜索的A*
6、算法估价函数：将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。 f(x)g(x)h(x) h(x)：启发函数，有利于搜索纵向发展，提高搜索效率，但影响完备性。 g(x)：代价函数，有利于搜索横向发展，提高搜索的完备性，但影响搜索效 率。 f(x)：是初始节点S0到达节点x处已付出的代价与节点x 到达目标节点Sg 的接近程度估计值总和。是g（x）与h（x）的折中。A算法： 步1 把附有f（S0）的初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n； 步4 若目标节点SgN，则搜
7、索成功，结束。 步5 若N不可扩展，则转步2； 步6 扩展N，生成一组附有 f(x) 的子节点，对这组节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其 中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它 们被第二次生成，需考虑是否修改已经存在于OPEN表或CLOSED表中的这 些节点及其后裔的返回指针和f（x）的值，修改原则是抄 f(x) 值小的路走”。（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表 按 f(x) 以升序排列，转步2。A*算法： 对A算法再限制其估价函数中的启发函数h(x)满足： 对所有的节点x
8、均有：h(x)03) h(x)是h*(x)的下届，及对所有x，h(x)=h*(x)。在本题8数码问题中，常用的启发函数为：“不在位”数码个数，或数码“不在位”的距离和。显然，后者的h(x)不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。算法搜索树如下: 算法流程如下： 图3三、 算法代码3.1 宽度优先搜索的源代码及注解/*程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#inc
9、lude iostream#include stdio.h#include stdlib.h#include time.h#include string.h#include #include using namespace std;const int N = 3;/3*3图enum DirectionNone,Up,Down,Left,Right;/方向static int n=0;static int c=0;struct Map/图 int cellNN;/数码数组 Direction BelockDirec;/所屏蔽方向 struct Map * Parent;/父节点;/打印图void
10、 PrintMap(struct Map *map) cout*endl; for(int i=0;iN;i+) for(int j=0;jN;j+) coutcellij ; coutendl; cout*endl;/移动图struct Map * MoveMap(struct Map * map,Direction Direct,bool CreateNewMap) struct Map * NewMap; /获取空闲格位置 int i,j; for(i = 0; i N; i+) bool HasGetBlankCell = false; for(j = 0; j cellij = 0)
11、 HasGetBlankCell = true; break; if(HasGetBlankCell) break; /移动数字 int t_i = i,t_j = j; bool AbleMove = true; switch(Direct) case Down: t_i+; if(t_i = N) AbleMove=false; break; case Up: t_i-; if(t_i 0) AbleMove=false; break; case Left: t_j-; if(t_j = N) AbleMove=false; break; ; if(!AbleMove)/不可以移动则返回原
12、节点 return map; if(CreateNewMap) NewMap = new Map(); for(int x = 0; x N; x+) for(int y = 0; y cellxy = map-cellxy; else NewMap = map; NewMap-cellij = NewMap-cellt_it_j; NewMap-cellt_it_j = 0; return NewMap;bool IsSuccess(struct Map * map,struct Map * Target) bool IsSuc = true; for(int i = 0; i N; i+)
13、 for(int j = 0; j cellij != Target-cellij) IsSuc = false; break; if(!IsSuc) break; return IsSuc;struct Map * BNF_Search(struct Map * begin,struct Map * Target) struct Map * p1, *p2, *p=NULL; bool IsSucc = false; queue Queue; if(IsSuccess(begin,Target) return begin; Queue.push(begin); do p1 = Queue.f
14、ront(); Queue.pop(); for (int i = 1; i BelockDirec)/跳过屏蔽方向 continue; p2 = MoveMap(p1,Direct,true); if(p2 != p1) /数码是否可以移动 p2-Parent = p1;switch(Direct)/设置屏蔽方向,防止往回推case Up: p2-BelockDirec = Down; break;case Down: p2-BelockDirec = Up; break;case Left: p2-BelockDirec = Right; break;case Right: p2-Belo
15、ckDirec = Left; break;if (IsSuccess(p2,Target) p = p2; return p;Queue.push(p2);n+; while(!Queue.empty() | p = NULL); return p;int Jou(struct Map *map) /将八数码转换成一个数列，并计算其逆序数int a=0;char b9;for(int i=0;iN;i+)for(int j=0;jcellij;for(int k=0;k9;k+)for(int h=0;hk;h+)if(bhbk)&bh!=0)a+;return a%2;int main()
16、int a1,a2;int i,j,m,n;int target9;int flag; Map Target; Map *begin,*T; begin=new Map; cout请输入八数码的目标状态(用0代替空格):endl;/输入目标状态for (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) flag=1;if (targeti8|flag=1) /判断输入是否正确i-;cout输入错误，请关闭重新运行!n; int k=0;for (m=0;m3;m+) /把数组target中的数传给图Targetfor (n=0;n3;n+) Targ
17、et.cellmn=targetk;k+; /输入起始状态cout请输入八数码的起始状态(用0代替空格):endl;for (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) /判断输入的数是否正确flag=1;if (targeti8|flag=1)i-;cout输入错误，请关闭重新运行!n;k=0;for (m=0;m3;m+)for (n=0;ncellmn=targetk;k+; begin-Parent = NULL; begin-BelockDirec = None; cout目标图:endl; PrintMap(&Target); co
18、ut起始图:endl; PrintMap(begin);a1=Jou(&Target);a2=Jou(begin); if(a1!=a2)cout无解endl; exit(0); /无解的话就退出，重新运行 else double start=clock(); cout有解endl; /图搜索 T=BNF_Search(begin,&Target); /打印 if(T != NULL) /把路径倒序 Map *p=T; stack Stack1; while(p-Parent != NULL) Stack1.push(p); p = p-Parent; cout宽度优先最少步数的搜索过程为:e
19、ndl; while(!Stack1.empty() PrintMap(Stack1.top(); c+; Stack1.pop(); coutn完成!endl; cout找到目标状态所需要的最少步数为:cendl; double end=clock(); cout程序运行的时间为:end-startmsendl; return 0;运行结果：3.2 A*算法源代码及其注释#include #include #include #include #include static int target9=1,2,3,8,0,4,7,6,5;/class definitionclass eight_n
20、umprivate:int num9;int not_in_position_num;int deapth;int eva_function;public:eight_num* parent;eight_num* leaf_next;eight_num* leaf_pre;eight_num(int init_num9);eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)num0=num1;num1=num2;num2=num3;num3=num4;num4=nu
21、m5;num5=num6;num6=num7;num7=num8;num8=num9;eight_num(void)for (int i=0;i9;i+)numi=i;void cul_para(void);void get_numbers_to(int other_num9);int get_nipn(void)return not_in_position_num;int get_deapth(void)return deapth;int get_evafun(void)return eva_function;void set_num(int other_num9);void show(vo
22、id);eight_num& operator=(eight_num&);eight_num& operator=(int other_num9);int operator=(eight_num&);int operator=(int other_num9);/计算启发函数g(n)的值void eight_num:cul_para(void)int i;int temp_nipn=0;for (i=0;iparent=NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_num+deapth;/构造
23、函数1eight_num:eight_num(int init_num9)for (int i=0;i9;i+)numi=init_numi;/显示当前节点的状态void eight_num:show()coutnum0;cout ;coutnum1;cout ;coutnum2;coutn;coutnum3;cout ;coutnum4;cout ;coutnum5;coutn;coutnum6;cout ;coutnum7;cout ;coutnum8;coutn;/复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)fo
24、r (int i=0;i9;i+)other_numi=numi;/设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)for (int i=0;i9;i+)numi=other_numi;eight_num& eight_num:operator=(eight_num& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;not_in_position_num=another_8num.not_in_position_num;deapth=another_8
25、num.deapth+1;eva_function=not_in_position_num+deapth;return *this;eight_num& eight_num:operator=(int other_num9)for (int i=0;i9;i+)numi=other_numi;return *this;int eight_num:operator=(eight_num& another_8num)int match=1;for (int i=0;i9;i+)if(numi!=another_8num.numi)match=0;break;if (match=0)return 0
26、;else return 1;int eight_num:operator=(int other_num9)int match=1;for (int i=0;i9;i+)if(numi!=other_numi)match=0;break;if (match=0)return 0;else return 1;/class definition over/*/空格向上移int move_up(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i3)return 0;elsenumi=numi-3;numi-3=0;return 1;/空格向下移int
27、 move_down(int num9)for (int i=0;i5)return 0;elsenumi=numi+3;numi+3=0;return 1;/空格向左移int move_left(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=0|i=3|i=6)return 0;elsenumi=numi-1;numi-1=0;return 1;/空格向右移int move_right(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=2|i=5|i=8)return 0;elsenu
28、mi=numi+1;numi+1=0;return 1;/判断可否解出int icansolve(int num9,int target9)int i,j;int count_num,count_target;for (i=0;i9;i+)for (j=0;ji;j+)if(numjnumi&numj!=0)count_num+;if(targetjparent)if(*p=num)return 1;return 0;/寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start)eight_num *p,*OK;p=OK=start;int mi
29、n=start-get_evafun();for(p=start;p!=NULL;p=p-leaf_next)if(minp-get_evafun()OK=p;min=p-get_evafun();return OK;/主函数开始int main(void)double time; clock_t Start,Finish;int memery_used=0,step=0;int num9;int flag=0;/是否输入错误标志，1表示输入错误int bingo=0;/是否查找成功标志，1表示成功int i,j;coutPlease input the number(0 for the bl
30、ank):n;for (i=0;inumi;for(j=0;ji;j+)if(numi=numj)flag=1;if (numi8|flag=1)i-;coutIllegle number!tReinput!n;eight_num S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used+;coutNow the initial numbers are:n;S.show();coutAnd the Target is:n;Target.show();if(!icansolve(num,
31、target)couti;return 1;Start=clock( );eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p;while(OK_leaf!=NULL&bingo!=1)OK_leaf=find_OK_leaf(leaf_start);if(*OK_leaf=Target)bingo=1;break;p=OK_leaf-leaf_pre;OK_leaf-get_numbers_to(num);if(move_up(num)&!existed(num,OK_leaf)new_8num=new eight_num;new_8num-se
32、t_num(num);new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p=NULL)leaf_start=new_8num;elsep-leaf_next=new_8num;p=new_8num;memery_used+;OK_leaf-get_numbers_to(num);if(move_down(num)&!existed(num,OK_leaf)new_8num=new eight_num;new_8num-set_num(num);new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p=NULL)leaf_start=new_8num;else