下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 人工智能课程设计报告(八皇后问题与罗马尼亚问题)

人工智能课程设计报告(八皇后问题与罗马尼亚问题).doc

人工智能课程设计报告(八皇后问题与罗马尼亚问题)

刘Debby
2018-09-13 0人阅读 举报 0 0 暂无简介

简介:本文档为《人工智能课程设计报告(八皇后问题与罗马尼亚问题)doc》,可适用于综合领域

人工智能课程设计报告(八皇后问题与罗马尼亚问题)人工智能课程设计报告目录(N皇后问题…………………………………………………………需求分析设计…………………………………………………设计表示…………………………………………………………运行结果…………………………………………………………用户手册即测试数据……………………………………………结论………………………………………………………………主要算法代码……………………………………………………罗马尼亚问题…………………………………………………………需求分析设计…………………………………………………设计表示详细设计……………………………………………用户手册…………………………………………………………运行结果…………………………………………………………主要算法代码……………………………………………………实习心得………………………………………………………………………N皇后问题(问题描述、需求分析在N*N的棋盘上分布N个皇后其中N个皇后不能在同一行同一列也不能出现在同一对角线上此时N个皇后不会相互攻击。程序需能手动输入皇后个数并分别采用回溯法、爬山法、遗传法得出皇后的分布情况输出皇后的位置即棋盘。(设计思想形式化N个皇后的位置可用一个N维数组表示如……意思是第一个皇后在第一列的第行。程序模块CreatIndividual()函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组即产生一组互不相等的~N之间的整数便于快速求解。IsLegal()函数用于判断新放置的皇后是否合法在回溯法中用到。AttackQueenNum()用于计算整个棋盘的攻击皇后个数相当于一个评价函数在爬山法和遗传法中用到Find()回溯法求解函数ClimbHill()爬山法求解函数GA()遗传算法求解函数()函数调用关系图如下:()函数接口规格说明:下图中的箭头指向表示为被指向函数所用IsLegal()CreatIndividual()AttackQueenNum()Find()GA()ClimbHill()主函数详细设计a:CreatIndividual(int*A,intQueenNum):以当时时间为种子循环产生随机数为了使得产生的随机数都不想等设计集合SN并初始化为表示还没有产生一个皇后当产生的皇后不在SN中即SN~=时将Sn置为接着产生下一个皇后如此循环便产生一组互不相等的值。b:IsLegal(int*A,intt)此函数用于判断第t列的皇后是否合法即有没有皇后在同一行、同一列同一对角线上并返回true或者false。c:AttackQueenNum(int*A,intQueenNum)循环调用IsLegal()函数对攻击数进行累加并返回其值此函数作为棋盘的评价函数。d:Find(int*A,intk,intQueenNum,longbeginTime)回溯法求解因为回溯法的每一层都是for循环所以不能单纯的用break语句进行控制因为即使当前层循环停止了程序还会继续执行上一层的循环所以将起始时间作为参数进行传递以便求出算法执行时间然后用exit()语句终止程序所以要将回溯法放在其它两个算法的后面执行。e:ClimbHill(int*A,intQueenNum):由于在产生一个棋盘个体的时候所有的皇后就不在同一行同一列所以在爬山法中只对棋盘的列进行交换这样即使再怎么交换所有的皇后还是不在同一行同一列但在交换的时候需要调用AttackQueenNum()函数进行棋盘的评价如果交换前的攻击数大于交换后的攻击数则进行交换否则与下一列进行交换比较如此循环直到找出解。f:GA()(用户手册运行程序输入皇后个数N各种算法得到的皇后分布情况、耗时自动显示(测试数据及测试结果测试,,皇后测试结果如下:分别程序运行结果:皇后运行结果皇后运行结果如下皇后运行结果如下:皇后运行结果如下由于皇后的棋盘稍大这里只给出运行时间结论:根据输入皇后个数递增的运行结果可以看出爬山法的速度是相当快的在皇后个数比较少时回溯法的速度要快于遗传算法而当皇后个数比较多时回溯法的深度搜索明显慢于遗传算法。主要算法程序代码::boolIsLegal(int*A,intt)判断第t列的皇后位置是否合法{intifor(i=i<ti)首先判断前面几列同一行有没有皇后{if(Ai==At)returnfalse}if(t>abs(AtAt)==)然后再判断是否与相邻前一列皇后发生冲突returnfalsereturntrue}:voidCreatIndividual(int*A,intQueenNum){inti,x在产生随机数时使用int*s=newintQueenNum集合用于产生一组皇后位置for(i=i<QueenNumi)si=srand((unsigned)time())种子A=rand()QueenNum第一列的皇后可以没有限制的产生所以先产生sA=for(i=i<QueenNumi){do{x=rand()QueenNum}while(sx==)sx==表示此位置已有皇后则重新产生新的位置Ai=xsAi=}}:voidFind(int*A,intk,intQueenNum,longbeginTime){inti,jif(k==QueenNum){for(i=i<QueenNumi){printf("")for(j=j<QueenNumj){if(Aj==i)printf("#")elseprintf("O")}printf("n")}longendTime=clock()获得结束时间(endTimebeginTime)<单位为毫秒printf("回溯法d皇后耗时:dmsn",QueenNum,endTimebeginTime)exit()}else{for(i=i<QueenNumi){Ak=i对Ak从开始进行赋值下面再判断所赋的值是否合法合法的话进行下一列皇后位置的赋值if(IsLegal(A,k))Find(A,k,QueenNum,beginTime)当循环结束时仍然找不到则返回一层Ak的层数加}}}:intAttackQueenNum(int*A,intQueenNum){inti,CountAttack=if(abs(AA)==)判断第一列CountAttackfor(i=i<QueenNumi)首先判断前面几列同一行有没有皇后{if(abs(AiAi)==)与前一列是否冲突CountAttackif(abs(AiAi)==)与后一列是否冲突CountAttack}if(abs(AQueenNumAQueenNum)==)判断最后一列CountAttackreturnCountAttack}:voidClimbHill(int*A,intQueenNum){inti,j,temp,Mark,Count,CountAttackMark用于标记交换的位置intMinCountAttack在选取移动方案时使用int*SaveTry=newintQueenNum存储临时方案用于比较CreatIndividual(A,QueenNum)CountAttack=AttackQueenNum(A,QueenNum)MinCountAttack=CountAttackfor(i=i<QueenNumi)SaveTryi=Aiwhile(CountAttack!=){for(i=i<QueenNumMinCountAttack!=i){Mark=MinCountAttack=AttackQueenNum(SaveTry,QueenNum)在每一列与其他列交换之前MinCountAttack都等于当前的Try的攻击数for(j=j<QueenNumMinCountAttack!=j){if(i!=j)只与其他列进行交换{temp=SaveTryjSaveTryj=SaveTryiSaveTryi=tempCount=AttackQueenNum(SaveTry,QueenNum)if(Count==){MinCountAttack=Count即为Mark=j记录交换列的位置break如果攻击数位直接跳出循环}if(Count<MinCountAttack){MinCountAttack=CountMark=j记录交换列的位置}temp=SaveTryj再将刚刚交换的位置复原用于与下一列进行比较交换两次即达到交换的效果SaveTryj=SaveTryiSaveTryi=temp}}if(MinCountAttack==)breakif(Mark!=){temp=SaveTryMark再将刚刚交换的位置复原用于与下一列进行比较交换两次即达到交换的效果SaveTryMark=SaveTryiSaveTryi=temp}}CountAttack=AttackQueenNum(SaveTry,QueenNum)}for(i=i<QueenNumi)Ai=SaveTryi存储存储最终结果}罗马尼亚问题(需求分析:从文件中读取图和启发函数分别用Dijkstra、深度优先、广度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径即为罗马尼亚问题的一个解在求解的过程中记录扩展节点的个数(用于比较几种算法的优劣)记录每种算法得到的解即输出每种解得到的条路径。(设计:设计思想对于图的存储采用邻接矩阵进行存储因为此图节点与边比较多(若比较少则采用邻接表结构此时效率比较高)采用堆栈和队列等进行路径的存储并且在某条路径走到最大深度都没有发现目标节点时具有返回上一节点的能力(好处:在某条路上找不到时可以进入相邻的一条路径并不是单纯的返回:索索失败)为了不重复访问同一个节点(此时路径会出现环导致程序循环执行)利用集合的思想即将访问过的节点状态置为没有访问过的置为以此来避免路径出现环。设计表示()函数调用关系图ReadGraphFile()GreedySearth()BFSearth()DFSearth()ReadHFile()Dijkstra()主函数ASearth()详细设计a:Dijkstra()设置集合数组GatherMaxVertices按照路径长度递增的顺序逐步产生最短路径并将起始点到其他节点的距离存放到数组distance中将到每一个节点的最短路径的前一节点存至path数组中从起始节点Arad开始将其状态标为重复执行如下步骤N次直至所有节点的状态都为)在所有不在集合的顶点中选取选取distancei最小的一个顶点设置为第u个顶点)将选出的终结点序号U并入集合中即其状态改为)以u作为新考虑的中间点修改不在集合中的个顶点的distancej值如果distanceuGedgeu,j<distancei则令distancei=distanceuGedgeu,j同时记下此路径pathj=u在主函数中利用堆栈和path数组将起始节点到目标节点的路径找出来(因为寻找路径时是从目标点向前倒推寻找的所以先将路径入栈再出栈得到的既是从起始点到目标点的一条路径)。b:DFSearth()设置集合数组GatherMaxVertices采用堆栈寻找路径首先将起始节点入栈然后执行如下循环:)读取栈顶元素获得栈顶元素的一个邻接点(此节点的状态需是即未访问过)在获得邻接顶点的过程中如果发现目标顶点则进栈退出循环)如果此节点未访问过则进栈并将其状态标为)如果找不到邻接点则出栈执行()在执行循环的过程中对扩展的节点个数进行计数并将堆栈中的路径出栈到数组在主函数中进行输出。c:BFSearth()设置集合数组GatherMaxVertices采用队列寻找路径首先将起始节点入队列然后执行如下循环:)出队列并将出队列的节点入栈(用于保存路径))循环获取此节点的邻接顶点(未访问过的即状态为的节点)并入队列状态标为在寻找邻接点的过程中如果发现目标节点则退出循环)将每一次出队列的顶点都进栈保存(用于输出路径)然后执行寻找路径部分:此处再定义一个堆栈首先将目标点进栈设此栈为栈先前存储出队列元素的栈设为栈:)栈出栈)栈循环出栈如果出栈的顶点状态为并且与当前顶点不在图的同一行即不相邻那么由栈出栈的顶点即为栈出栈顶点的父节点将此节点入栈执行()最后将栈中的所有节点出栈即为宽度优先寻找到的一条路径同样在寻找的过程中记录扩展节点的个数d:GreedySearth()设置集合数组GatherMaxVertices采用堆栈首先将起始节点入栈执行如下循环:)读出栈顶元素(只读并不进行出栈操作))循环获取此元素的邻接顶点(即其所有的还未访问过的孩子)利用排序找到启发函数值最小的孩子结点将此孩子节点入栈状态标为执行())如果读出的栈顶元素以找不到邻接顶点即孩子说明此条路径已经走到最大深度处则出栈(即返回上一层)此时执行()因为只对入栈的元素状态值为所以返回上一层的时候寻找出所有的邻接顶点并找出最小值此时的最小值是次小值(因为最小值那条路不通)这样程序便进入下一条路径的寻找e:ASearth()设置集合数组GatherMaxVertices采用堆栈首先将起始节点入栈执行如下循环:)读取栈顶元素获取此节点的所有邻接顶点(即所有孩子)选取实际路程g(N)与启发函数值最小的节点入栈将其状态标为在此过程中如果发现目标顶点则循环结束)如果此条路已走到最大深度处则出栈寻找下一条路径执行()在此函数中定义了一个*的数组GHFMaxVertices用于比较f(N)=g(N)h(N)(作业的表相似执行过程相同)f:ReadGraphFile()与ReadHFile()完成文件的读操作利用fgetc(fp)函数进行一位一位的读并将读取的数据转换为整数形式进行存储以供于其他算法的使用在循环读取文件的过程中注意文件尾的处理。(用户手册直接运行程序即可得到Dijkstra、深度优先、广度优先、贪婪算法、A*算法得到的解即根据相应的算法的到从起始节点到目标节点的一条路径。(整体运行结果如下:(主要算法代码如下:Dijkstra算法voidDijkstra(AdjMGraphG,intv,intdistance,intpath){intn=Gverticessizeint*s=(int*)malloc(sizeof(int)*n)集合intminDis,i,j,u初始化for(i=i<ni){distancei=Gedgevisi=if(i!=vdistancei<MaxWeight)pathi=velsepathi=}sv=for(i=i<ni){minDis=MaxWeightfor(j=j<nj)if(sj==distancej<minDis){u=jminDis=distancej}if(minDis==MaxWeight)returnsu=for(j=j<nj)if(sj==Gedgeuj<MaxWeightdistanceuGedgeuj<distancej){distancej=distanceuGedgeujpathj=u}}}深度优先搜索voidDFSearth(AdjMGraphG,intv,intvg,intpath,int*Expand,int*AnswerWay){inti,x,SumExpand=intVertex用于寻找目标节点intGatherMaxVertices集合SeqStackSStackInitiate(S)for(i=i<MaxVerticesi)Gatheri=StackPush(S,v)首先将起始节点入栈SumExpandGatherv=while(){StackTop(S,x)Vertex=GetFirstVex(G,x)获取第一个临接点while(GatherVertex==){Vertex=GetNextVex(G,x,Vertex)}while(Vertex==)此时未找到下一个临接点{StackPop(S,x)StackTop(S,x)Vertex=GetFirstVex(G,x)while(GatherVertex==){Vertex=GetNextVex(G,x,Vertex)}}StackPush(S,Vertex)SumExpandGatherVertex=同一条路径上那个不允许出现相同的节点防止转圈if(Vertex==vg)break}*Expand=SumExpand*AnswerWay=Stopif(Stop==)printf("深度优先搜索失败!!!")else{while(StackNotEmpty(S)){StackTop(S,x)pathStop=xStackPop(S,x)}}}宽度优先搜索voidBFSearth(AdjMGraphG,intv,intvg,intpath,int*Expand,int*AnswerWay){inti,x,y,SumExpand=intVertex用于寻找目标节点intGatherMaxVertices集合SeqStackSaveQ,LineSaveSaveQ将出队列的节点全部进栈,LineSave用于保存路径,StackInitiate(SaveQ)StackInitiate(LineSave)SeqCQueueQQueueInitiate(Q)for(i=i<MaxVerticesi)Gatheri=QueueAppend(Q,v)首先将起始节点入队列SumExpandGatherv=while(){QueueDelete(Q,x)StackPush(SaveQ,x)将每一个出队列的结点进行保存Vertex=GetFirstVex(G,x)获取第一个临接点if(Vertex==vg)break此时找到目标节点if(Vertex==){printf("宽度优先搜索失败!!!")return}while(Vertex!=)将x的所有邻接顶点入队列{if(GatherVertex==)表示还未扩展{QueueAppend(Q,Vertex)SumExpandGatherVertex=}Vertex=GetNextVex(G,x,Vertex)if(Vertex==vg)break此时找到目标节点截止搜索}if(Vertex==vg)break此语句用于终止外层循环}StackPush(LineSave,Vertex)此时Vertex为目标节点StackPush(LineSave,x)此时x为Vertex的父节点StackPop(SaveQ,x)while(StackNotEmpty(SaveQ)){StackPop(SaveQ,x)StackTop(LineSave,y)if(IsShareFatherEdge(G,x,y)<IsEdge(G,x,y)Gatherx==)如果没有相同的父亲,被访问过并且之间有边则保存路径StackPush(LineSave,x)}*Expand=SumExpand*AnswerWay=LineSavetopi=while(StackNotEmpty(LineSave)){StackPop(LineSave,x)pathi=xi}}贪婪算法voidGreedySearth(AdjMGraphG,intH,intv,intvg,intpath,int*Expand,int*AnswerWay){inti,x,SumExpand=intMinWorth,MinXMinX用于记录具有最小权值的扩展节点intVertex用于寻找目标节点intGatherMaxVertices集合SeqStackSStackInitiate(S)for(i=i<MaxVerticesi)Gatheri=StackPush(S,v)首先将起始节点入栈SumExpandGatherv=while(){MinWorth=MaxWeightMaxWeight=表示无穷大StackTop(S,x)Vertex=GetFirstVex(G,x)获取第一个临接点if(Vertex==vg){StackPush(S,Vertex)将目标节点压栈GatherVertex=SumExpandbreak此时找到目标节点}if(GatherVertex==HVertex<MinWorth){MinWorth=HVertexMinX=Vertex记录最小节点}if(Vertex!=){while(Vertex!=){Vertex=GetNextVex(G,x,Vertex)if(Vertex==){StackPush(S,MinX)将当前最小节点压栈GatherMinX=SumExpandbreak}if(Vertex==vg){StackPush(S,Vertex)将目标节点压栈GatherVertex=SumExpandbreak此时找到目标节点}if(HVertex<MinWorth){MinWorth=HVertexMinX=Vertex记录最小节点}}}else{while(Vertex==)此时未找到下一个临接点,往回退一步{StackPop(S,x)}}}*Expand=SumExpand*AnswerWay=Stopif(Stop==)printf("贪婪算法失败!!!")else{while(StackNotEmpty(S)){StackTop(S,x)pathStop=xStackPop(S,x)}}}A*算法voidASearth(AdjMGraphG,intH,intv,intvg,intpath,int*Expand,int*AnswerWay){inti,j,x,SumExpand=intMinF,MinX记录最小f(N)与对应的节点在比较f(N)时使用intVertex用于寻找目标节点intGatherMaxVertices集合intGHFMaxVertices分别用于存储g(N)h(N)f(N)SeqStackSStackInitiate(S)for(i=i<MaxVerticesi){Gatheri=GHFi=GHFi=对f(N)进行初始化因为在后面要进行比较所以必须初始化}StackPush(S,v)首先将起始节点入栈GHFv=g(N)GHFv=Hvh(N)GHFv=GHFvGHFvf(N)=g(N)h(N)SumExpandGatherv=i=while(){MinF=MaxWeightMaxWeight=表示无穷大StackTop(S,x)Vertex=GetFirstVex(G,x)获取第一个临接点if(Vertex==vg){StackPush(S,Vertex)将目标节点压栈GatherVertex=SumExpandbreak此时找到目标节点}if(Vertex!=){if(GatherVertex==){GHFVertex=GedgexVertexGHFxg(N)GHFVertex=HVertexh(N)GHFVertex=GHFVertexGHFVertexf(N)=g(N)h(N)if(GHFVertex<MinF){MinF=GHFVertexMinX=Vertex}}while(Vertex!=){Vertex=GetNextVex(G,x,Vertex)if(Vertex!=GatherVertex==){GHFVertex=GedgexVertexGHFxg(N)GHFVertex=HVertexh(N)GHFVertex=GHFVertexGHFVertexf(N)=g(N)h(N)if(GHFVertex<MinF){MinF=GHFVertexMinX=Vertex}}if(Vertex==){StackPush(S,MinX)将当前最小节点压栈GatherMinX=SumExpandbreak}if(Vertex==vg){StackPush(S,Vertex)将目标节点压栈GatherVertex=SumExpandbreak此时找到目标节点}}}else{while(Vertex==)此时未找到下一个临接点,往回退一步{StackPop(S,x)}}}*Expand=SumExpand*AnswerWay=Stopif(Stop==)printf("贪婪算法失败!!!")else{while(StackNotEmpty(S)){StackTop(S,x)pathStop=xStackPop(S,x)}}}voidReadGraphFile(FILE*fp,AdjMGraph*g,intn,inte){inti,j,x=,x=,x=x用于读取栈中的数据存入图数组charchSeqStackSStackInitiate(S)for(i=i<ni){j=while(j<n)j为当前需要读进数组的列下标{ch=fgetc(fp)if(ch!=''ch!=ch!=)为换行符号StackPush(S,ch)将字符转换为数字入栈else{if(i!=jStop!=)如果不是,此时只将边读出来{if(Stop==){StackPop(S,x)g>edgeij=x将读出的值变为数值存储}if(Stop==){StackPop(S,x)StackPop(S,x)g>edgeij=x*x将读出的值变为数值存储}if(Stop==){StackPop(S,x)StackPop(S,x)StackPop(S,x)g>edgeij=x*x*x将读出的值变为数值存储}}while(StackNotEmpty(S)){StackPop(S,x)}j}}}}voidReadHFile(FILE*fp,intH,intn)度启发式函数文件{inti=,x=,x=,x=x用于读取栈中的数据存入图数组charchSeqStackSStackInitiate(S)while(i<n){ch=fgetc(fp)if(ch!=''ch!=):正常读入时遇到空格为下一个的开始但在读取最后一个数据时没有空格读出StackPush(S,ch)将字符转换为数字入栈else{if(Stop==){StackPop(S,x)Hi=x将读出的值变为数值存储}if(Stop==){StackPop(S,x)StackPop(S,x)Hi=x*x将读出的值变为数值存储}if(Stop==){StackPop(S,x)StackPop(S,x)StackPop(S,x)Hi=x*x*x将读出的值变为数值存储}i}}}本次上机心得:进过调试、跟踪熟悉了回溯函数的执行过程更深一层次的理解到什么是回溯。八皇后问题和罗马尼亚问题实现了函数功能的模块化独立函数的功能。像产生一个皇后棋盘的改进使得产生的皇后既不在同一行也不在同一列便于爬山法和遗传算法啊的执行此时函数的执行只需要交换列与列。计算攻击皇后个数的函数扮演了一个评价棋盘的角色方便爬山法和遗传算法的执行。对于罗马尼亚问题做的时间比较久第一个做的算法是深度优先搜索完成此算法用了一下午主要的问题在于对深度优先搜索的思想不是很透彻之后的三个算法在理解了深度优先搜索的基础上进行功能的实现都是比较顺利的在此过程中也意识到很多问题其实是相似的真正理解了一种问题的解法之后其他问题都可在原先的基础上加以修改得到解决。对于相同的问题采用不同方法进行处理比较各种算法的优劣性。当程序的运行结果与自己的结论不相同的时候最好的办法就是进行跟踪既可以发现程序的漏洞也可以加深自己的理解。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/36

人工智能课程设计报告(八皇后问题与罗马尼亚问题)

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利