人工智能大作业

1、 人工智能大作业 班级：021351 姓名（学号）： 2015年12月16号题目一：搜索算法编程及实验报告题目：八数码难题的求解1. 实验目的问题描述：现有一个3*3的棋盘，其中有0-8一共9个数字，0表示空格，其他的数字可以和0交换位置（只能上下左右移动）。给定一个初始状态和一个目标状态，找出从初始状态到目标状态的最短路径的问题就称为八数码问题。例如：实验问题为283104765123804765到目标状态：从初始状态： 要求编程解决这个问题，在盲目搜索和启发式搜索方法中分别选择一种方法来求解八数码难题。给出搜索树从初始节点到目标节点的路径。 2. 实验设备及软件环境利用计算机编程软件Vis

2、ual C+ 6.0，用C语言编程解决该问题。3. 实验方法法1：用启发式搜索中的有序搜索方法来解决该问题(1).算法描述：.把初始节点S放到OPEN表中，计算，并把其值与节点S联系起来。.如果OPEN表是个空表，则失败退出，无解。.从OPEN表中选择一个值最小的节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一节点作为节点。.把节点从OPEN表中移出，并把它放入CLOSED的扩展节点表中。.如果是目标节点，则成功退出，求得一个解。.扩展节点，生成其全部后继节点。对于的每一个后继节点： a.计算。 b.如果既不在OPEN表中，也不在CLOSED表中，则用估

3、价函数把它添加入OPEN表。从加一指向其父辈节点的指针，以便一旦找到目标节点时记住一个解答路径。 c.如果已在OPEN表或CLOSED表上，则比较刚刚对计算过的值和前面计算过的该节点在表中的值。如果新的值较小，则 I.以此新值取代旧值。 II.从指向，而不是指向它的父辈节点。 III.如果节点在CLOSED表中，则把它移回OPEN表。 转向，即GO TO 。 (2).流程图描述： (3).程序源代码：#include #includestruct nodeint number33;/用二维数组存放8数码 int W;/W表示与目标状态相比错放的数码数int Depth;/记录当前节点的深度st

4、ruct node *parent;/指向父节点的指针struct node *next;/指向链表中下一个节点的指针;int CounterW(int Number33)/函数说明：计算当前状态与目标状态的W值int i,j;int W=0;int Desnode33=1,2,3,8,0,4,7,6,5;for(i=0; i3; i+)for(j=0; j3; j+)if(Numberij != Desnodeij)W+; return W;void PrintNode(node *A)int i,j;for(i=0; i3; i+)for(j=0; jnumberij);printf(n)

5、;printf(n);int CheckNode(node *open, node *close, int a33)/检验该节点状态是否出现过的子程序int CheckFlag=0;int flag1,flag2;node *p=open;node *q=close;while(p != NULL) flag1=0;for(int i=0; i3; i+)for(int j=0; jnumberij)flag1+;if(flag1 = 9)break;elsep=p-next;while(q != NULL)flag2=0;for(int i=0; i3; i+)for(int j=0; jn

6、umberij)flag2+;if(flag2 = 9)break;elseq=q-next;if(flag1=9) | (flag2=9)CheckFlag=1;/如果出现过，置标志位为1return CheckFlag;struct node *FindNextNode(node *Prenode, node *open, node *close) /扩展Prenode指向的节点，并将扩展所得结点组成一条单链表int i,j,m,n; /循环变量int temp; /临时替换变量int flag=0; int a33;/临时存放二维数组struct node *p, *q, *head;

7、head=(node *)malloc(sizeof(node);/head指向该链表首结点，并且作为返回值p=head;q=head;head-next=NULL;/初始化for(i=0;i3;i+)/找到二维数组中0的位置for(j=0;jnumberij=0)flag=1;break;if(flag=1)break;/根据0的位置的不同，对a进行相应的变换 for(m=0;mnumber赋给afor(n=0;nnumbermn; if(i+1=2)/情况1，0向下移temp=aij; aij=ai+1j; ai+1j=temp;int CheckNum=CheckNode(open, c

8、lose, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;mnumber for(n=0;nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1;/子结点的深度等于其父结点深度加1 q-W=CounterW(q-number); q-next=NULL; p-next=q;/扩展节点插入head链表 p=p-next; for(m=0;mnumber重新赋给afor(n=0;nnumbermn;if(

9、i-1=0)/情况2,0向上移temp=aij; aij=ai-1j; ai-1j=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;mnumber for(n=0;nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1; q-W=CounterW(q-number); q-next=NULL; p-next=q; p=p-

10、next; for(m=0; m3; m+)for(n=0; nnumbermn;if(j-1=0)/情况3,0向左移 temp=aij; aij=aij-1; aij-1=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0; mnumber for(n=0; nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1; q-W=

11、CounterW(q-number); q-next=NULL; p-next=q; p=p-next; for(m=0;m3;m+)for(n=0;nnumbermn;if(j+1=2)/情况4,0向右移temp=aij; aij=aij+1; aij+1=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0; mnumber for(n=0; nnumbermn=amn; PrintNode(q); q-par

12、ent=Prenode; q-Depth=q-parent-Depth+1; q-W=CounterW(q-number); q-next=NULL; p-next=q; p=p-next; head=head-next;return head; node *insert(node *open,node *head) /将head链表的结点依次插入到open链表相应的位置， /使open表中的结点按从小到大排序。函数返回open指针node *p,*q;/p、q均指向open表中的结点，p指向q所指的前一个结点int flag=0;if(open=NULL) & (head != NULL)/

13、初始状态，open表为空 /首先将head表第一个结点直接放入open表中open=head;q=head; head=head-next;q-next=NULL;if(open != NULL) & (open-next=NULL) &(head != NULL)/open表中只有一个元素q=open; if(head-W + head-Depth) W + open-Depth)/若后一结点的f值小于首结点，则将它插入到首结点位置open=head;head=head-next;open-next=q; else/或者第二个结点的位置 q-next=head; head=head-next

14、; q=q-next; q-next=NULL;p=open;while(head!=NULL)q=open;if(head-W + head-Depth) W + open-Depth) /插入到表头open=head;head=head-next;open-next=q;continue;else q=q-next; p=open; /否则，q指像第二个结点，p指向q前一个结点while(q-next!=NULL) /将head的一个结点插入到链表中（非表尾的位置）if(q-W W) q=q-next;p=p-next;elsep-next=head;head=head-next;p-ne

15、xt-next=q; break;if(q-next=NULL)/将head的一个结点插入到表尾或倒数第二个位置if(q-W + q-Depth) W + head-Depth)q-next=head;head=head-next;q-next-next=NULL;elsep-next=head;head=head-next;p-next-next=q;return open; void main()int i,j;int key=0;node FirstNode; node *open, *close;node *p, *r;node *NodeList;printf(请输入初始状态的8数码

16、（按每行从左往右依次输入,用0表示空格）：n); for(i=0; i3; i+)for(j=0; j3; j+)scanf(%d,&FirstNode.numberij);printf(n);printf(搜索树为：n);for(i=0; i3; i+) for(j=0; jW = 0)/该结点的状态与目标结点相同 printf(该结点已为目标结点状态！n); return; r=&FirstNode; close=&FirstNode;r-next=NULL; open=NULL; NodeList=FindNextNode(r,open,close);/NodeList指向新扩展出来的链

17、表 open=insert(open,NodeList);/将扩展出来的结点插入到open表中 while(open != NULL) r-next=open;/将open表的第一个元素加到close表，r始终指向close表的最后一个元素 open=open-next; r=r-next; r-next=NULL; if(r-W = 0) key=1; printf(n启发式搜索成功！n); break; NodeList=FindNextNode(r,open,close);/对close表最后一个结点进行扩展，扩展得到的链表接到head表 open=insert(open,NodeLis

18、t);/将扩展的结点按顺序插入到open表中if(key = 1) p=close; printf(最优搜索过程如下：n); printf(结点深度为:%dn,FirstNode.Depth); printf(-n); while(p!=NULL) for(i=0; i3; i+) for(j=0; jnumberij); printf(n); printf(n); p=p-next; if(p != NULL) printf(结点深度为:%dn,p-Depth); printf(-n); else printf(查找失败，该问题无解！n); 法2：用盲目搜索中的宽度优先搜索法解决该问题.算法

19、描述：.把初始节点S0放入OPEN表;.如果OPEN表为空，则问题无解，退出;否则继续。.把OPEN表的第一个节点（记为n）取出放入CLOSE表;.扩展节点n。如果没有后继节点，则转向上述第步。.把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。.如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第步。.流程图： .程序源代码：#include #include #define TIME 50/限定只搜索前50步，50步以后如果仍然没有搜索到结果，认为无解。#define MAXSIZE 200int n = 1, i,j, k;int result

20、9 = 1, 2, 3, 8, 0, 4, 7, 6, 5 ;/所要达到的最终状态，0代表空格。typedef structint num9;char expension;/记录是否可以扩展，Y代表可以扩展，N代表不可以。char banOperate;/表示不可以执行的操作，L代表不能左移，R代表不能右移，/U代表不能上移，D代表不能下移，C代表可以任意移动。int father;/记录父节点的下标。Node;Node storeMAXSIZE;/将搜索过的状态存储于该数组中。int same(int temp)/判断是否达到了目标状态。for (j = 0; j9; j+)if (stor

21、etemp.numj != resultj)return 0;return 1;void printResult()/输出搜索结果。for (j = 1; j = n; j+)printf(第%d步搜索后：n, j);printf(t%dt%dt%dn, storej.num0, storej.num1, storej.num2);printf(t%dt%dt%dn, storej.num3, storej.num4, storej.num5);printf(t%dt%dt%dn, storej.num6, storej.num7, storej.num8);printf(nn);int le

22、ft(int temp)/将空格进行左移操作。for (j = 0; j9; j+)/判断空格的位置。if (storetemp.numj = 0)break;if (j = 0 | j = 3 | j = 6)return 0;for (k = 0; k9; k+)storen.numk = storetemp.numk;int tempNum = storen.numj - 1;/将移动后的状态赋给storenstoren.numj - 1 = 0;storen.numj = tempNum;storetemp.expension = N;storen.banOperate = R;sto

23、ren.expension = Y;storen.father = temp;if (same(n)/判断storen是否为最终想得到的状态。printResult();exit(1);n+;return 1;int right(int temp)/将空格进行右移操作。for (j = 0; j9; j+)if (storetemp.numj = 0)break;if (j = 2 | j = 5 | j = 8)return 0;for (k = 0; k9; k+)storen.numk = storetemp.numk;int tempNum = storen.numj + 1;stor

24、en.numj + 1 = 0;storen.numj = tempNum;storetemp.expension = N;storen.banOperate = L;storen.expension = Y;storen.father = temp;if (same(n)printResult();exit(1);n+;return 1;int up(int temp)/将空格进行上移操作。for (j = 0; j9; j+)if (storetemp.numj = 0)break;if (j = 0 | j = 1 | j = 2)return 0;for (k = 0; k9; k+)

25、storen.numk = storetemp.numk;int tempNum = storen.numj - 3;storen.numj - 3 = 0;storen.numj = tempNum;storetemp.expension = N;storen.banOperate = D;storen.expension = Y;storen.father = temp;if (same(n)printResult();exit(1);n+;return 1;int down(int temp)/将空格进行下移操作。for (j = 0; j9; j+)if (storetemp.numj

26、 = 0)break;if (j = 6 | j = 7 | j = 8)return 0;for (k = 0; k9; k+)storen.numk = storetemp.numk;int tempNum = storen.numj + 3;storen.numj + 3 = 0;storen.numj = tempNum;storetemp.expension = N;storen.banOperate = U;storen.expension = Y;storen.father = temp;if (same(n)printResult();exit(1);n+;return 1;v

27、oid init()Node start;printf(请输入初始状态，用空格分开，0代表空格:n);/输入初始的状态。for (i = 0; i9; i+)scanf(%d, &start.numi);for (k = 0; k9; k+)if (start.numk = 0)break;start.banOperate = C;start.expension = Y;start.father = -1;store0 = start;/将初始状态赋于store0。void main()init();if (same(0)printf(没有必要进行搜索，初始状态即为最终状态!);exit(1)

28、;for (i = 0; i= TIME)/50步以后仍然没有达到所要求的状态，认为无解。n-;printResult();printf(Sorry，在所在搜索范围内没有搜索到结果！);exit(1);4.实验结果（1）.有序搜索的搜索结果为：搜索树为：最短路径为：（2）.宽度优先搜索结果为：5.实验分析启发式搜索采用简单的估价函数：其中是搜索树中节点的深度；用来计算对应于节点的数据库中错放的棋子个数。例如初始节点的估价函数值为3。估价函数能够提供一个评定候选扩展节点的方法，以便确定哪个节点时最有可能在通向目标的最佳路径上。这样选择正确的估价函数，可以减少扩展节点个数，对于实验所给的初始节点和

29、估价函数，只用扩展11个节点就能找到目标节点；相比于盲目搜索可以减少被扩展的节点数，减少很多空间占用和时间损耗。利用启发信息来决定哪一个是下一步要扩展的节点，这种搜索总是选择“最有希望”的节点作为下一步被扩展的节点。这实际上是通过估价函数值的大小重排OPEN表，小的一直排在OPEN表的前面。每次取OPEN表的第一个节点放到CLOSED表中进行扩展，这样一步步靠近目标节点，直到最后找到目标节点，停止扩展。6.结论正确选择估价函数对确定搜索结果具有决定性作用。使用不能识别某些节点真是希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数，又会扩展过多的节点。在选对估价函数

30、的前提下，启发式搜索能准确识别有希望和没有希望的节点，从而很快扩展到目标节点，找到最短路径。在本次实验中如果选择估价函数值为（用来计算对应于节点的数据库中错放的棋子个数），将会扩展更少的节点，更加快的找到到达目标节点的最短路径。题目二：计算智能编程及实验报告题目：遗传算法编程求解最优化问题1.实验目的 理解基本遗传算法的原理，编写MATLAB程序，并利用程序实现利用遗传算法优化非线性函数的解。函数 f(x) = -x2 - 4x + 1，求 max f(x), x -2, 2,解的精度保留二位小数。2.实验设备及软件环境利用计算机编程软件MATLAB 7.10.0，用MATLAB编程解决该问题

31、。3.实验方法（1）算法描述：遗传算法概要遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图6.1所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素： 参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。 生成初始群体：由于遗传算法的群体型操作需要，所

32、以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生。 适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的依据。 选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和（ ），再计算每个个体的适应度所占的比例（ ），并以此作为相应的选择概率 。 交叉操作：交叉操作是遗传算法中最主要的遗

33、传操作。简单的交叉（即一点交叉）可分两步进行：首先对种群中个体进行随机配对;其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。 变异：变异操作是按位（bit）进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率 都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。算法步骤Step1：参数设置及种群初始化；Step2：适应度评价；Step3：轮盘赌选择；Step4：交叉；Step5：变异；Step6：适应度评价；Step7：终止条件判断，若未达到终止条件，则转到Step3；Step8：

34、输出结果。(2)算法流程图：(3)程序代码：主函数:clearclcmy_scale=80; %种群规模gen_len=22; %基因长度M=100; %迭代次数pc=0.7; %交叉概率pm=0.05; %变异概率new_scale=produscale(my_scale,gen_len); %产生初始种群fitfit=; fittimer=; best_f1=;best_x1=; for i=1:M my_f=cal_my_f(new_scale); %计算函数值 my_fit=cal_my_fit(my_f); %计算适应度值 next_scale=my_sellect(new_scal

35、e,my_fit); %采用赌轮盘法选择 cross_scale=my_cross(next_scale,pc); %按概率交叉 mut_scale=my_mutat(cross_scale,pm); %按概率变异 %寻找每一代中的最优适应度值所对应的个体 best_fit=my_fit(1); sx,sy=size(new_scale); for j=2:length(my_fit) if best_fitmy_fit(j) best_fit=my_fit(j); best_f=my_f(j); best_x=my2to10(new_scale(j,:); best_x=-2+best_x.

36、*4./(2sy-1); end end new_scale=mut_scale; fitfit=fitfit,best_fit; best_f1=best_f1,best_f; best_x1=best_x1,best_x; fittimer=fittimer,i;end best_fit,loca=max(fitfit); best_f=best_f1(loca); best_x=best_x1(loca); disp(best_fit,best_f,best_x=)disp(best_fit,best_f,best_x)subplot(2,2,1) plot(fittimer,fitfi

37、t) xlabel(迭代次数(1)-wxb); ylabel(适应度函数) grid on%子函数：产生初始种群function initscale=produscale(my_scale,gen_len) initscale=round(rand(my_scale,gen_len);end%子函数：计算函数值function my_f=cal_my_f(new_scale) mychange=my2to10(new_scale); sx,sy=size(new_scale); change_x=-2+mychange.*4./(2sy-1); my_f=-change_x.2-4.*chan

38、ge_x+1;end%子函数：计算适应度值function my_fit=cal_my_fit(my_f) f_min=5; for i=1:length(my_f) if my_f(i)+f_min=0 my_fit(i)=0; else my_fit(i)=my_f(i)+f_min; end end my_fit=my_fit;end %子函数：采用赌轮盘法选择function next_scale=my_sellect(new_scale,my_fit) sum_of_f=sum(my_fit); accum=my_fit/sum_of_f; accum=cumsum(accum);

39、sx,sy=size(new_scale); j=1; while j=a next_scale(j,:)=new_scale(1,:); else if accum(i)=a next_scale(j,:)=new_scale(i+1,:); j=j+1; end end end endend%子函数：按概率交叉function cross_scale=my_cross(new_scale,pc) sx,sy=size(new_scale); cross_scale=new_scale; for i=1:2:sx-1 if randpc a=round(rand*sy); cross_scale(i,:)=new_s