人工智能实习报告

人工智能实习报告第一部分罗马尼亚问题（1）问题描述：FindBuchareststartingatArad分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。罗马尼亚地图如下：各节点启发函数值如下：（2）数据结构：逻辑结构：采用数组完成，并配套设置相应标志位。存储结构：启发函数值及其对应地名采用结构体数组place[20]存储，从文件中读入。结构体声明如下：typedefstruct{charname[20];//存储地名，数组下标表示地名标号intqf;//存储相应启发函数值}路径采用二维数组data[20][20]存储，从文件中读入：（3）算法思想：宽度优先(BFS)：从初始结点出发，判断是否为目标结点。若否，宽度优先搜索与该结点相连接的结点并存进待扩展结点表needvisit[]等待扩展。当一个结点完全扩展（即与其所有相连的结点都已进入待扩展表或已扩展表），记录下此时结点的数值并立出一标志位，以等待最后输入时的判断。判断待扩展结点表是否为空，若否则从待扩展结点表表首中取出一个结点进行扩展，并将扩展后的结点存进visited[]。直到搜索到目标结点。最后输出结果result[]。访问visited[]计算出生成结点数量n_num并输出。深度优先（DFS）：大致同宽度优先算法，数据结构仍然保持不变，但采用搜索策略时优先进行深度探索，即从初始结点出发，选择一与其相连且未在visited[]中的结点（即此节点未被访问过）。不同的是对于一个结点存入已访问的判断，深度优先采取的是判断该结点是否有未被访问的后继结点，以及该后继结点又是否有未扩展的后继结点，以此类推，最后找到目标结点。最后输出结果result[]。访问visited[]计算出生成结点数量n_num并输出。贪婪算法(Greedy)：贪婪算法在对问题求解时，总是选择局部最优，逐步累加最终形成问题的相对最优解（而非绝对）。从初始结点出发后，进行比较，计算出与其相连的所有结点中，所需移动消耗最少的结点。将初始结点存入visited[]中，该结点存入needvisit[]中。然后，重新以该结点为初始结点，再进行计算并移动，最终移动至目标结点。当不可移动时（即与其相连的所有结点都已访问过），则退后一步，在此基础上再选择移动消耗最少的结点。最终一定可以到达目标结点。A*算法：A*算法用公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始点经由结点n到目标点的估价函数；g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。A*算法大致也同贪婪算法，只是对于结点的选择依据不同。（4）运行结果：宽度优先(BFS)：深度优先（DFS）：贪婪算法(Greedy)：A*算法：（5）比较结论：宽度优先深度优先贪婪算法A*算法生成结点数目111275各算法搜索路径依次如下：经过比较，显然，A*算法与贪婪算法生成的结点数目最少，效率最高。深度优先生成的结点数目最多，效率最低，但这主要是因为程序中的搜索次序由对应结点序号决定，而恰好首选的结点又不是正确的结点才导致了这样的结果。通常来讲，一般宽度优先的效率最低。从运行出的搜索路径来看宽度优先、深度优先和贪婪算法搜索找到的也都不一定是最优解，只有A*算法具有完备性且始终找到的都是最优解。即使宽度优先一定可以找到最优解，但往往它找到的第一个并非是最优的（本例中输出的就并不是最优的）。在最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时，它将耗费大量的时间。其优先时间复杂度：O（b^n+1）（b为分支因子，d为深度）；空间复杂度为所存储的节点的个数。而深度优先仅在结点有限的情况下是完备的，同样的，它也不能找到最优解。深度优先的时间复杂度：O（b^m）；空间复杂度：O（b*m+1）（b为分支因子，m为深度）。贪婪算法找到的解也不一定是最优解。其时间复杂度：O（b^m）（b代表分支数，m为深度）；空间复杂度为O(b^m)。所以只有A*算法是完备的，且能够找到最优解。第二部分N皇后问题（1）问题描述：在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，分别用回溯法（递归）、GA算法和CSP算法求解n皇后问题。要求：ⅰ.输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率，并列表给出结果。ⅱ.比较同一算法在n不相同时的运行时间，分析算法的时间复杂性，并列表给出结果。（2）数据结构：1、逻辑结构：用到线性结构包括一维数组，二维数组。2、存储结构（物理结构）：顺序存储结构。（3）算法思想：回溯法：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。在N皇后问题中基本思想是：从第一列开始放置第一个皇后，然后第二列符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置，每次放置皇后之后都进行检查，验证是否符合要求（即皇后之间无冲突），当放置要求的数量N后问题即得到解。GA算法：从定义上看，遗传算法是模拟物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。对于一个求函数最大值的优化问题，首先初始化，包括种群的大小，编码的方案，遗传的代数，变异的概率，等等；然后进行选择操作；接着是将选择的个体进行交叉；然后再进行选择，并将选择的个体进行变异；最后就是更新最优值了。在本题中，采用的选择方法为按适应度比例选择，其中适应度为染色体（棋盘）中的基因（皇后）之间的冲突数目。操作过程如下，采用单亲遗传算法：1.产生初始种群。2.对当前种群根据变异概率进行变异，生成新种群。3.检验停止准则，如果有解则停止，否则转到2重复执行。为了更快的得到解，采取了进一步的优化，在选择之后对中间个体进行一定几率的变异（将适应度较低的基因进行变异），从而使得更快的得到解决方案。CSP算法：1.初始化各个信息表，皇后位置初始化先让每列的皇后独占一行，确保每一行只有一个皇后，再随机交换任意两列皇后所在的位置，打乱棋盘2.执行最小冲突算法：1).分析棋盘，算出棋盘每个位置其他皇后对它的冲突数，一个皇后对它冲突那个位置的值+1，每个皇后会影响水平和两个倾斜线上的各个位置2).从第一列开始遍历，把列的皇后移动到本列冲突数最小的位置，当有多个最小值的随机取得其中的一个。3).更新棋盘，按皇后原来的位置和移动后的位置更新三个方向上各个位置的冲突数，原来位置三个方向上各个位置冲突数-1，移动后的位置三个方向各个位置冲突数+1，遍历到最后一列。4).判断是否满足可行解，当各个皇后所在位置冲突数为0及找到可行解。5).当本次循环各个皇后的位置和上次循环皇后的位置不变，重新初始化各个皇后的位置。跳转到2）6).当找到可行解退出循环。（4）.运行结果：回溯法：GA算法：CSP算法：（两种情况）找不到结果时：找到结果时：（笑脸表示放置皇后的位置，*表示未放置皇后）总体大致为：（5）比较结论：回溯法GA算法CSP算法时间复杂度O（n!）O(kN)O(N^N)运行时间（s）1.0090.0615.4附程序关键代码：罗马尼亚度假问题：宽度优先算法：intBFS(){inti=0,j,v=0,r=1,u=0,m=1,p=0;initdata();while(1){if(needvisit[i]!=99){visited[v]=needvisit[i];v++;u=needvisit[i];needvisit[i]=99;for(j=0;j20;j++){if(data[u][j]!=1000&&data[u][j]!=0){p=check_visit(j);if(p==0){needvisit[m]=j;m++;result[r]=j;r++;if(j==2){BFS_out();return0;}}}}}elsei++;}return0;}深度优先算法：intfind_after_node(intLine){intj;intp;for(j=0;j20;j++){Line=needvisit[1];if(data[Line][j]!=1000&&data[Line][j]!=0){p=check_visit(j);if(p==0)returnj;}}return1;}intr=1;intcal_DFS(){inti,c=0;while(needvisit[1]!=99){c=find_after_node(needvisit[1]);if(c!=1){result[r]=c;r++;needvisit[1]=c;visited[c]=c;if(c==2){printf(路径为a:);printf(%s-,place[0].name);for(i=1;result[i]!=0&&i20;i++){printf(%s-,place[result[i]].name);}return0;}}elsereturn1;}return1;}intDFS(){inti=0,p1=0;n_num=1;initdata();visited[0]=0;needvisit[1]=0;//0标括?记?为a已?访?问ê&&从洙?第台?结á点?开a始?p1=cal_DFS();while(p1==1)//没?有瓺找ò到?正y确ā?路·径?{r=r-1;result[r]=0;//结á果?还1原-1位?needvisit[1]=result[r-1];p1=cal_DFS();}for(i=0;i20;i++){if(visited[i]==99)n_num++;}printf(NULL);printf(\n生成结点数为a：%d\n,n_num);return0;}贪婪算法：intfind_Greedy_node(intLine,intr){intc1=0;//c为所需返回的下一结点编括号intj;intmin=1000;//存放最小移动消耗for(j=0;j20;j++){if(data[Line][j]!=1000&&data[Line][j]!=0&&check_visit(j)!=1){if(data[Line][j]min){min=data[Line][j];c1=j;}}}visited[c1]=c1;result[r]=c1;returnc1;}intGreedy_out(intr1){inti;intnum=0;printf(路径为a:);for(i=0;ir1&&i20;i++){printf(%s-,place[result[i]].name);}for(i=0;i20;i++){if(visited[i]!=99)num++;}printf(\n生成结点数为a:%d\n,num);return0;}intGreedy(){intLine=0;intr=1;//r-resultinitdata();visited[0]=0;while(Line!=2){Line=find_Greedy_node(Line,r);r++;}Greedy_out(r);return0;}A*算法：intfind_A_node(intLine,intr){intc=0;intj;intmin=10000;for(j=0;j20;j++){if(data[Line][j]!=1000&&data[Line][j]!=0&&check_visit(j)!=1){if(data[Line][j]+place[j].qfmin){min=data[Line][j]+place[j].qf;c=j;}}}visited[c]=c;result[r]=c;returnc;}intA_out(intr1){inti;intn