西电人工智能大作业.doc

人工智能大作业 学 院 电子工程学院专 业 智能科学与技术学 号 姓 名 第一部分：八数码难题基于图搜索策略求解八数码问题的最优路径1、 问题简介 八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 1 2 38 47 6 52 8 31 6 47 5 初始节点 目标节点2、 基于图搜索问题的搜索方法 图搜索是人工智能的核心技术之一，人工智能的许多分支领域都涉及到图搜索。我们可以把图搜索看成是一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库，求得把一个数据库变换成另一个数据库的规则序列问题就等价于求的图中的一条路径问题。 图搜索一般过程： （1）建立一个只含有其实节点S的搜索图G，建立一个OPEN表，它只含有 初始节点S。 （2）建立一个表CLOSED，它的初始状态为空。 （3）LOOP：若OPEN为空，则失败退出。 （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成员，确定是否应该改变图G中通向它 的每个后裔节点的指针方向。 （8）按某种方式，对OPEN表中的节点重新排序。 （9）GO LOOP。图搜索的一般方法： 三、求解八数码难题的两种算法3.1 广度优先搜索 广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。 步骤步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺 序编号n；步4 若目标节点Sg=N，则搜索成功，结束。步5 若N不可扩展，则转步2；步6 扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN 表的尾部，转步2。 广度优先搜索亦称为宽度优先或横向搜索。这种策略是完备的，即如果问题的解存在，用它则一定能找到解，且找到的解还是最优解（即最短的路径）。这是优点，缺点是搜索效率低。宽度优先搜索流程图： 图1 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展个结点和生成个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。 图23.2 启发式图搜索的A*算法估价函数：将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。 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，则搜索成功，结束。 步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均有：h(x)03) h(x)是h*(x)的下届，及对所有x，h(x)=h*(x)。在本题8数码问题中，常用的启发函数为：“不在位”数码个数，或数码“不在位”的距离和。显然，后者的h(x)不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。算法搜索树如下: 算法流程如下： 图33、 算法代码3.1 宽度优先搜索的源代码及注解/*程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#include 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 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) 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)/不可以移动则返回原节点 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+) 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.front(); 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-BelockDirec = 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()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+) Target.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); cout起始图: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宽度优先最少步数的搜索过程为:endl; 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_numprivate: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=num5;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(void);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;/构造函数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)for (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_8num.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;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 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;elsenumi=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 min=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 blank):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,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-set_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;elsep-leaf_next=new_8num;p=new_8num;memery_used+;OK_leaf-get_numbers_to(num);if(move_left(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;elsep-leaf_next=new_8num;p=new_8num;memery_used+;OK_leaf-get_numbers_to(num);if(move_right(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;elsep-leaf_next=new_8num;p=new_8num;memery_used+;p-leaf_next=OK_leaf-leaf_next;if(OK_leaf-leaf_next!=NULL)OK_leaf-leaf_next-leaf_pre=p;OK_leaf-leaf_next=OK_leaf-leaf_pre=NULL;Finish=clock( ); if(bingo=1)time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC;eight_num *p;for (p=OK_leaf-parent;p!=NULL;p=p-parent)coutshow();step+;coutTime cost:;couttime;coutmsn;coutTotaly covered steps:;coutstep;coutn;elsecoutFail to find!;return 0;运行结果： 4、 小结图搜索是人工智能的核心技术之一，人工智能的许多分支领域都涉及到图搜索。任一搜索过程也都是一个推理过程,隐式图的搜索过程是一种利用局部性知识构造全局性答案的过程。在各种搜索过程中，人工智能最感兴趣的是那些具有很强选择性的启发式方法，即那些利用很局部的状态空间可以有效地找到问题的解的方法。机器学习等很多过程都是在假设空间中搜索目标的过程。五、参考文献【1】人工智能及其应用 蔡自兴、徐光佑 清华大学出版社【2】人工智能原理辅导与练习 王文杰、史忠植 清华大学出版社出【3】人工智能导论 王勋、凌云、费玉莲 科学出版社第二部分：进化计算综述报告遗传算法与蚁群算法概述摘要：遗传算法来源于进化论和群体遗传学，是计算智能的重要组成部分，是计算数学中用于解决最优化的搜素算法，是一种性能出色的进化算法。蚁群算法是一种用来在图中寻找优化路径的机率型算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，是一种性能优良的模拟进化算法。二者思想不同，却都同属进化计算范畴，其性质有很多互补性。本文结合进化计算领域的遗传算法与蚁群算法的定义与进展进行阐释，并部分涉及到二者的相关性及其融合的研究成果。关键词：遗传算法 蚁群算法 互补融合引言：自霍兰德（Holland）1975年在他的著作Adaptation in Natural and Artificial Systems中首次提出遗传算法以来，进过近30年的研究，遗传算法现在已经发展到一个比较成熟的阶段，并在实际中得到良好运用。而同样在进化计算高速发展的20世纪90年代，意大利学者多里戈、马佐尼和科洛龙等从生物进化和仿生学角度出发，研究蚂蚁寻找路径的自然行为，提出了蚁群算法，并用该方法求解TSP问题、二次分配问题和作业调度等问题，取得较好结果。蚁群算法已经显示其在求解复杂优化问题尤其是离散优化问题方面的优势，是一种很有发展前景的计算智能方法。正文： 1.进化计算 a)什么是进化计算在计算机科学领域，进化计算（Evolutionary Computation）是人工智能（Artificial Intelligence），进一步说是智能计算（Computational Intelligence）中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。 b)进化计算起源 运用达尔文理论解决问题的思想起源于20世纪50年代。 20世纪60年代，这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程（Evolutionary programming），而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（Genetic algorithms）。在德国，Ingo Rechenberg 和Hans Paul Schwefel提出了进化策略（Evolution strategies）。 这些理论大约独自发展了15年。在80年代之前，并没有引起人们太大的关注，因为它本身还不够成熟，而且受到了当时计算机容量小、运算速度慢的限制，并没有发展出实际的应用成果。 到了20世纪90年代初，遗传编程（Genetic programming）这一分支也被提出，进化计算作为一个学科开始正式出现。四个分支交流频繁，取长补短，并融合出了新的进化算法，促进了进化计算的巨大发展。Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。Ingo Rechenberg在上世纪 60 年代和 70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。特别是John Holland的作品让遗传算法变得流行起来。随着学术研究兴趣的增长，计算机性能的迅速提高使包括自动演化的计算机程序等实际的应用程序成为现实。比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。 2.遗传算法 a)简介遗传算法(Genetic Algorithms，简称GA)是由美国Michigan大学的John Holland教授创建的。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。 b)基本原理 与传统搜索算法不同，遗传算法从一组随机产生的初始解，称为群体，开始搜索过程。群体中的每个个体是问题的一个解，称为染色体。这些染色体在后续迭代中不断进化，称为遗传。遗传算法主要通过交叉、变异、选择运算实现，交叉或变异运算生成下一代染色体，称为后代，染色体的好坏用适应