人工智能概论-搜索算法编程及实验报告

1、人工智能概论大作业学院：电子工程学院专业：智能科学与技术 PAGE 45题目一：搜索算法编程及实验报告一算法题目八数码难题的求解。二实验目的从盲目搜索和启发式搜索方法中分别选择一种解决八数码难题，给出搜索树和从起始节点到目标节点的路径。三实验设备及软件环境Win7 的笔记本电脑， VS2013（使用 c 语言编程）。四实验方法盲目搜索宽度优先搜索。（ 1） . 算法描述如果搜索是以接近其实节点的程度来依次扩展节点，那么这中搜索就叫宽度优先搜索。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。(1）把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一

2、个解答）。（2） 如果 OPEN是个空表，则没有解，失败退出；否则继续。） 把第一个节点（节点n ）从OPEN表移出，并把它放入CLOSED扩展节点表中。） 扩展节点 n。如果没有后继节点，则转向上述第（2）步。） 把 n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到 n 的指针。） 如果 n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（ 2）步。（ 2） . 算法流程图（ 3） . 程序代码#include stdio.h #include conio.h#include string.h struct picchar data10; char imo

3、perate; int father;char extend;char end10 = 1238 4765; int result100;int n; int m;pic base100;char *w;int find(int x)for (int i = 0; i = 0; i-)printf(nnn);printf(%ct%ct%cn, baseresulti.data0, baseresulti.data1, baseresulti.data2);printf(%ct%ct%cn, baseresulti.data3, baseresulti.data4, baseresulti.da

4、ta5);printf(%ct%ct%c, baseresulti.data6, baseresulti.data7, baseresulti.data8);int left(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if (i = 0 | i = 3 | i = 6) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai - 1 = basex.datai;basen.datai = basex.datai - 1; basen.

5、father = x; basen.imoperate = R; basen.extend = Y;basex.extend = N;w = basen.data; n+;if (find(n - 1) = 1)return 1;int right(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if (i = 2 | i = 5 | i = 8) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai + 1 = basex.datai;

6、basen.datai = basex.datai+1; basen.father = x; basen.imoperate = L; basen.extend = Y;basex.extend = N;w = basen.data; n+;if (find(n - 1) = 1)return 1;int up(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if (i = 0 | i = 1 | i = 2) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.data

7、j;basen.datai - 3 = basex.datai;basen.datai = basex.datai - 3;basen.father = x; basen.imoperate = D; basen.extend = Y;basex.extend = N; w = basen.data; n+;if (find(n - 1) = 1)return 1;int down(int x)int i;for (i = 0; i 10; i+)if (basex.datai = ) break;if (i = 6 | i = 7 | i = 8) return 0;for (int j =

8、 0; j 10; j+)basen.dataj = basex.dataj;basen.datai + 3 = basex.datai;basen.datai = basex.datai + 3; basen.father = x;basen.imoperate = U; basen.extend = Y;basex.extend = N; w = basen.data; n+;if (find(n - 1) = 1)return 1;void main()void showtree(int x); n = 1;int i;strcpy_s(base0.data, 2831 4765); b

9、ase0.imoperate = N; base0.father = -1;base0.extend = Y; for ( i = 0; i 100; i+)if (basei.extend = Y)if (basei.imoperate = L)if (right(i) = 1)break; if (up(i) = 1)break;if (down(i) = 1)break; continue;if (basei.imoperate = R)if (left(i) = 1)break; if (up(i) = 1)break;if (down(i) = 1)break; continue;i

10、f (basei.imoperate = U)if (left(i) = 1)break;if (right(i) = 1)break;if (down(i) = 1)break; continue;if (basei.imoperate = D)if (right(i) = 1)break; if (up(i) = 1)break;if (left(i) = 1)break; continue;if (basei.imoperate = N)if (left(i) = 1)break; if (right(i) = 1)break; if (up(i) = 1)break;if (down(

11、i) = 1)break; continue;printf(搜索结束 n); showline(n - 1);showtree(n - 1); getchar();void showtree(int x)printf(nnn搜索树nnn); int i;for (i = 0; i = x; i+)if (i = 0)printf(ttt%c%c%cn, basei.data0, basei.data1, basei.data2);printf(ttt%c%c%cn, basei.data3, basei.data4, basei.data5);printf(ttt%c%c%cn, basei.

12、data6, basei.data7, basei.data8);printf(ttt|n); printf();for (int j = 0; j 0 & i 4 & i = 12)printf( %c%c%c, basei.data0, basei.data1, basei.data2);for (int j = 1; j 8; j+)printf(%c%c%c, basei+j.data0, basei+j.data1, basei+j.data2);printf(n %c%c%c, basei.data3, basei.data4, basei.data5);for (int j =

13、1; j 8; j+)printf(%c%c%c, basei + j.data3, basei + j.data4, basei + j.data5);printf(n %c%c%c, basei.data6, basei.data7, basei.data8);for (int j = 1; j 12 & i = 20)printf( %c%c%c, basei.data0, basei.data1, basei.data2);for (int j = 1; j 8; j+)printf(%c%c%c, basei + j.data0, basei + j.data1, basei + j

14、.data2);printf(n %c%c%c, basei.data3, basei.data4, basei.data5);for (int j = 1; j 8; j+)printf(%c%c%c, basei + j.data3, basei + j.data4, basei + j.data5);printf(n %c%c%c, basei.data6, basei.data7, basei.data8);for (int j = 1; j 8; j+)printf(%c%c%c, basei + j.data6, basei + j.data7, basei + j.data8);

15、printf(n|);printf(|);printf(printf(|);|n);printf();for (int j = 0; j 7;j+) printf();printf(n |);for (int j = 0; j 20 & i = 36)printf(n%c%c%c, basei.data0, basei.data1, basei.data2);for (int j = 1; j 11; j+)printf( %c%c%c, basei + j.data0, basei+ j.data1, basei + j.data2);printf(n%c%c%c, basei.data3,

16、 basei.data4, basei.data5);for (int j = 1; j 11; j+)printf( %c%c%c, basei + j.data3, basei+ j.data4, basei + j.data5);printf(n%c%c%c, basei.data6, basei.data7, basei.data8);for (int j = 1; j 11; j+)printf( %c%c%c, basei + j.data6, basei+ j.data7, basei + j.data8);i = 36;continue;启发式搜索有序搜索） 算法描述有序搜索又

17、称最好优先搜索，他总是选择最有希望的节点作为下一个要扩展的节点。（ 1)把起始节点 S 放到 OPEN表中，计算 f(S) 并把其值与节点S联系起来。如果 OPEN是个空表，则失败退出，无解。从 OPEN表中选择一个 f 值最小的节点 i 。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i 。把节点 i从 OPEN表中移出，并把它放入CLOSED的扩展节点表中。如果 i是个目标节点，则成功退出，求得一个解。扩展节点 i ，生成其全部后继节点。对于i 的每一个后继节点j ：计算 f(j)。如果 j既不在 OPEN表中，又不在 CLOSED表中，则

18、用估价函数f 把它添入 OPEN表。从 j 加一指向其父辈节点i 的指针，以便一旦找到目标节点时记住一个解答路径。果 j已在 OPEN表上或 CLOSED表上，则比较刚刚对j计算过的 f 值和前面计算过的该节点在表中的f 值。如果新的 f 值较小，则以此新值取代旧值。从 j指向 i ，而不是指向它的父辈节点。如果节点 j在 CLOSED表中，则把它移回OPEN表转向(2) ，即 GO TO(2)。） 算法流程图） 程序代码#include stdio.h #include conio.h #include struct picchar data10; char imoperate; int f

19、ather;int num; int d;char end10 = 1238 4765;int result100; int n;int m;pic base100;int open20 = 0; void inopen(int x)int i;for (i = 0; openi != 0; i+);openi = x;int errornumber(int x)int j = 0;for (int i = 0; i 9; i+)if (basex.datai != endi) j+;return j;int find(int x)for (int i = 0; i = 0; i-)print

20、f(nnn);printf(%ct%ct%cn, baseresulti.data0, baseresulti.data1, baseresulti.data2);printf(%ct%ct%cn, baseresulti.data3, baseresulti.data4, baseresulti.data5);printf(%ct%ct%c, baseresulti.data6, baseresulti.data7, baseresulti.data8);int left(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if

21、 (i = 0 | i = 3 | i = 6) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai - 1 = basex.datai;basen.datai = basex.datai - 1; basen.father = x; basen.imoperate = R;basen.d = basex.d + 1; basen.num = errornumber(n); inopen(n);n+;if (find(n - 1) = 1)return 1;int right(int x)int i;f

22、or (i = 0; i 10; i+)if (basex.datai = )break;if (i = 2 | i = 5 | i = 8) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai + 1 = basex.datai;basen.datai = basex.datai + 1; basen.father = x; basen.imoperate = L;basen.d = basex.d + 1; basen.num = errornumber(n); inopen(n);n+;if (f

23、ind(n - 1) = 1)return 1;int up(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if (i = 0 | i = 1 | i = 2) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai - 3 = basex.datai;basen.datai = basex.datai - 3; basen.father = x; basen.imoperate = D;basen.d = basex.d + 1; ba

24、sen.num = errornumber(n); inopen(n);n+;if (find(n - 1) = 1)return 1;int down(int x)int i;for (i = 0; i 10; i+)if (basex.datai = )break;if (i = 6 | i = 7 | i = 8) return 0;for (int j = 0; j 10; j+)basen.dataj = basex.dataj;basen.datai + 3 = basex.datai;basen.datai = basex.datai + 3; basen.father = x;

25、 basen.imoperate = U;basen.d = basex.d + 1; basen.num = errornumber(n); inopen(n);n+;if (find(n - 1) = 1)return 1;void outopen()for (int i = 0; openi != 0; i+) openi = openi + 1;void setopen()int x,i,j;int opennum = 0;for (i = 0; openi != 0; i+) opennum+;for (i = 0; i opennum; i+)for (j = i+1; j (ba

26、seopenj.d + baseopenj.num)x = openi; openi = openj; openj = x;void main()void showtree(int x); n = 1;strcpy_s(base0.data, 2831 4765); base0.imoperate = N; base0.father = -1;base0.d = 0;base0.num = errornumber(0); for (int i = 0; i 100; i+)setopen();if (baseopen0.imoperate = L)i = open0; outopen();if

27、 (right(i) = 1)break; if (up(i) = 1)break;if (down(i) = 1)break; continue;if (baseopen0.imoperate = R)i = open0; outopen();if (left(i) = 1)break; if (up(i) = 1)break;if (down(i) = 1)break; continue;if (baseopen0.imoperate = U)i = open0; outopen();if (left(i) = 1)break; if (right(i) = 1)break;if (dow

28、n(i) = 1)break; continue;if (baseopen0.imoperate = D)i = open0; outopen();if (left(i) = 1)break; if (right(i) = 1)break;if (up(i) = 1)break; continue;if (baseopen0.imoperate = N)i = open0; outopen();if (left(i) = 1)break; if (right(i) = 1)break; if (up(i) = 1)break;if (down(i) = 1)break; continue;pr

29、intf(搜索结束 n); showline(n - 1);showtree(n - 1); getchar();void showtree(int x)printf(nnn搜索树nnn); int i;for (i = 0; i = x; i+)if (i = 0)printf(ttt%c%c%cn, basei.data0, basei.data1, basei.data2);printf(ttt%c%c%cn, basei.data3, basei.data4, basei.data5);printf(ttt%c%c%cn, basei.data6, basei.data7, basei

30、.data8);printf(ttt|n);printf();for (int j = 0; j 0 & i = 4)printf(%c%c%c, basei.data0,basei.data1, basei.data2);for (int j = 1; j 4;j+)printf(t%c%c%c, basei+j.data0, basei+j.data1, basei+j.data2);printf(n%c%c%c, end3, end4, end5); for (int j = 1; j 4; j+)printf(t%c%c%c, basei + j.data3,basei + j.dat

31、a4, basei + j.data5);printf(n%c%c%c, end6, end7, end8); for (int j = 1; j 4 & i = 8)printf( %c%c%c, basei.data0, basei.data1,basei.data2);printf(%c%c%c, basei+1.data0, basei+1.data1, basei+1.data2);printf();printf();printf(%c%c%c, basei+2.data0, basei+2.data1, basei+2.data2);printf(%c%c%c, basei+3.d

32、ata0, basei+3.data1, basei+3.data2);printf();printf(n);printf( %c%c%c, basei.data3, basei.data4,basei.data5);printf(%c%c%c, basei + 1.data3, basei + 1.data4, basei + 1.data5);printf();printf();printf(%c%c%c, basei + 2.data3, basei + 2.data4, basei + 2.data5);printf(%c%c%c, basei + 3.data3, basei + 3

33、.data4, basei + 3.data5);printf();printf(n);printf( %c%c%c, basei.data6, basei.data7,basei.data8);printf(%c%c%c, basei + 1.data6, basei + 1.data7, basei + 1.data8);printf();printf();printf(%c%c%c, basei + 2.data6, basei + 2.data7, basei + 2.data8);printf(%c%c%c, basei + 3.data6, basei + 3.data7, bas

34、ei + 3.data8);printf();printf(n);printf(|);printf();printf(|);printf(n); i = 8;continue;if (i = 9)printf(%c%c%cn,basei.data0, basei.data1, basei.data2);printf(%c%c%cn,basei.data3, basei.data4, basei.data5);printf(%c%c%cn,basei.data6, basei.data7, basei.data8);printf(|n);if (i = 10)printf(%c%c%cn,bas

35、ei.data0, basei.data1, basei.data2);printf(%c%c%cn,basei.data3, basei.data4, basei.data5);printf(%c%c%cn,basei.data6, basei.data7, basei.data8);五.实验结果宽度优先搜索搜索树搜索路径有序搜索搜索树搜索路径六.实验分析盲目搜索一般只适用于求解比较简单的问题，且需要大量的时间空间作为基础。搜索空间大，搜索速度慢。同时编程代码简易。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的

36、搜索路径，提高了效率。但对估值函数的好坏很依赖，一个坏的估值函数会导致错过正确解甚至找不到解。同时编程代码会稍微比盲目算法复杂一些。两种算法相对比，盲目搜索适用于简单问题，直接进行几轮推演便能找到答案，但面对复杂的问题时，依次搜索显得十分繁琐，需要大量时间，空间做代价才能找到结果。启发式搜索就正好相反。它适合于复杂问题。通过计算估值函数，进行排序找到最优点进行展开能很快地找到答案也节省很多的空间。但有时一个不适用的估值函数会导致搜索不到正确解。于盲目式搜索相比，每步都需要对节点估值和排序，所有当问题简单时，用启发式会浪费时间。七.结论当问题简单，需要步骤少时，用盲目式搜索会省时省事地找到正确解

37、。当问题复杂，所需的步骤很多时，用启发式搜索可以快速并且节省空间地找到正确解，但同时一个好的估值函数是启发式搜索不可缺少的。题目二：计算智能编程及实验报告一、所选题目遗传算法求解问题并实现最优化二、问题提出函数 f 2( x, y)0.9exp( (x5)2( y5)222)0.999exp( x5)( y5)1020（ x,y 在-10 到 10 之间），利用遗传算法求函数的最大值及对应的位置。已知：种群数 N=50，交叉位数 n/2 ，即个体位数的一半 , 且位置自行设计，异位数自定， x,y 分辨率为 0.0001 。效果比较：交叉个数 =20,28,36,44变异个数=1,5,10,1

38、5三、实验目的利用遗传算法求解所提出问题，并实现最优解的算法，画出它的收敛曲线，记录实验结果，并求出最大值、最小值、平均值和标准差。四、实验设备及软件环境Win7 的笔记本电脑， MATLA。B五、实验方法1. 遗传算法）算法描述遗传算法（ Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带

39、有特征的实体。染色体作为遗传 物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（ generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（ fitness）大小选择（ selection）个体，并借助于自然遗传学的遗传算子（ genetic operators）进行组合交叉（ cros

40、sover ）和变异（ mutation ），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（ decoding ），可以作为问题近似最优解。第 1 步在论域空间 U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc 和变异率 Pm，代数 T；取适度函数为 f(x)=sinx/x，种群规模 N=50，用 popsize表示。x,y的精度为 0.0001 .交叉率 (crossover rate)：参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc, 取值范围一般为0.4 0.99 ，根据要求本例中选为20/5

41、0 、28/50 、36/50 、44/50 。变异率 (mutation rate)：发生变异的基因位数所占全体染色体的基因总位数的比例，记为 Pm，取值范围一般为0.0001 0.1 ，根据要求本例中选为1/50 、 5/50 、10/50 、15/50 。最大换代数：本题中取100 次第 2 步随机产生 U中的 N个染色体 s1, s2, sN ，组成初始种群S=s1, s2, sN ，置代数计数器t=1 ；第 3 步计算 S 中每个染色体的适应度f()；第 4 步若终止条件满足，则取S 中适应度最大的染色体作为所求结果， 算法结束。第 5 步按选择概率 P(xi)所决定的选中机会，每次

42、从S中随机选定 1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；第 6 步按交叉率 Pc 所决定的参加交叉的染色体数c，从 S1 中随机确定 c 个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；第 7 步按变异率 Pm所决定的变异次数m，从 S2中随机确定 m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；第 8 步将群体 S3 作为新一代种群，即用S3 代替 S，t=t+1 ，转步 3；）算法流程图生成初始种群计算适应度终止？结束选择-复制交叉变异生成新一代种群）程序代码计算目标函数值% calobjvalue.m函数的

43、功能是实现目标函数的计算%遗传算法子程序%Name: calobjvalue.m%实现目标函数的计算function objvalue=calobjvalue(pop) temp1=decodechrom(pop,1,18);%将 pop 每行转化成十进制数temp2=decodechrom(pop,19,18);x=temp1*20/262143;%将二值域中的数转化为变量域的数y=temp2*20/262143;objvalue=0.9*exp(x-5).2/10+(y-5).2/10)+0.9999*exp(-(x-15).2/20- (y-15).2/20); %计算目标函数值主程序%遗传算法主程序clearclfpopsize=50;%群体大小chromlength=36;%字符串长度（个体长度）pcc=20/50,28/50,36/50,44/50,20/50; pmm=1/50,5/50,10/50,15/50,1/50;pop=initpop(popsize,chromlength);%随机产生初始群体for i=1:100%100为 迭 代 次 数 pc=pcc(round(rand *4)+1);%交叉概率pm=pmm(round(rand *4)+1);%变异概率objv