n皇后问题和罗马尼亚问题实习报告.doc

人工智能课程实习报告题目：n皇后问题和罗马尼亚问题 班号： 191122 学号： 20121003553 姓名： 叶 超 指导老师：赵曼 2014.11 目录 人工智能课程实习报告1目录2罗马尼亚问题4一、问题描述4二、图的数据结构5三、实现算法51.宽度优先51.1数据结构：51.2算法思想：61.3运行结果：62.深度优先72.1数据结构：72.2算法思想：72.3运行结果：73.贪婪算法83.1数据结构：83.2算法思想：83.3运行结果：84.A*算法94.1数据结构：94.2算法思想：94.3运行结果：9四、比较结论9N皇后问题11一、问题描述：11二、数据结构11三、实现算法111、回溯法121.1数据结构：121.2算法思想：121.3运行结果:122、遗传算法122.1数据结构：132.2算法思想：132.3运行结果133、CSP最小冲突法133.1数据结构：133.2算法思想：143.3运行结果:14四、比较结论14总结15附源代码15罗马尼亚问题 15N皇后问题26递归算法27遗传算法29csp 最小冲突法35 罗马尼亚问题一、问题描述（1）罗马尼亚问题：Find Bucharest starting at Arad分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。（2） 附（罗马尼亚地图）（3）（3）各结点启发值：二、图的数据结构(1)节点信息：typedef structchar cityname20;城市名int value;启发函数值int cost;路径花费Ver;()地图信息typedef structVer VMaxV;一维城市数组int edgeMaxVMaxV;二维边数组int numofedges;Graph;（3）图的操作函数void Read_V(Graph &G)；/从文件读取顶点信息void Read_edge(Graph &G)；/从文件读取边的信息int GetFirstV(Graph G,int v)；/取节点v的第一个子节点int GetNextV(Graph G,int v1,int v2)；/取节点v1子节点v2后的第一个子节点三、实现算法1.宽度优先 1.1数据结构： 队列（BFS，贪婪，*公用）typedef structint queueMaxSize;int rear;int front;int count; SeqCQuene; 队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(SeqCQuene Q)； int QueueDelete(SeqCQuene *Q,int *d)； int QueueAppend(SeqCQuene *Q,int x)；先进先出（BFS） 记录父亲用于打印路径typedef structint father;int me;way; 1.2算法思想： 从Arad结点出发，判断是否为目标结点，若否，宽度优先搜索系统地 探寻与该结点相连的结点，算法首先搜索和Arad相距（深度）为k的所有顶点，然后再去搜索和Arad相距为k+l的其他顶点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。该算法同时能生成一棵根为Arad且包括所有可达顶点的宽度优先树 1.3运行结果：2.深度优先 2.1数据结构： 堆栈 typedef struct int a100;记录入栈城市序号int top1;栈顶int weight;最大路径用于剪枝 Stack; 2.2算法思想： 深度优先搜索是一种每次都要达到被搜索结构的叶结点的搜索方法 ，直到不能再深入为止，然后返回到另一个结点，继续对该结点进行深搜。当有目标结点出现时，返回目标结点，搜索结束；否则，若待扩展结点表已空，且未找到目标结点，则返回失败，停止搜索。同样，深度优先搜索从Arad结点出发，判断是否为目标结点，若否，探寻与该结点相连的结点，算法首先搜索一条分支上的所有顶点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。该算法同时能生成一棵根为Arad且包括所有可达顶点的深度优先树。在深度优先搜索中，我用到堆栈来存储待扩展结点表。 2.3运行结果： 说明：深度优先找到解生成的节点数为12，路径长度为605，程序中增加回溯和剪枝功能，所以会继续搜索优于当前解的路径，当生成14个节点时找到了最优解418，但此时不能确定该解就是最优解，因为还有路径没有遍历，当生成30个节点时，所有路径都已尝试，确定最优解为418。3.贪婪算法 3.1数据结构： 队列（BFS，贪婪，*公用）typedef structint queueMaxSize;int rear;int front;int count; SeqCQuene;队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(SeqCQuene Q)； int QueueDelete(SeqCQuene *Q,int *d)； int QueueOrderAppend(SeqCQuene *Q,int x,Graph G)；越小优先级越高记录父亲用于打印路径typedef structint father;int me;way; 3.2算法思想： 贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪婪算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。在解决罗马尼亚度假问题时，贪婪算法通过比较每个待扩展结点的h值，即启发函数生成的到目标结点的启发函数值，选取一个最小的，来确定当前要扩展的结点，并将生成的结点放进fringe结点表。在贪婪算法中，我用到队列存储待扩展结点表。 3.3运行结果：4.A*算法 4.1数据结构： 队列（BFS，贪婪，*公用）typedef struct int queueMaxSize;int rear;int front;int count; SeqCQuene; 队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(SeqCQuene Q)； int QueueDelete(SeqCQuene *Q,int *d)； intQueue_A_OrderAppend(SeqCQuene *Q,int x,Graph G)越小优先级越高 4.2算法思想： A*算法用公式表示为： f(n)=g(n)+h(n), 其中f(n) 是从初始点经由结点n到目标点的估价函数；g(n) 是在状态空间中从初始节点到n节点的实际代价， h(n)是从n到目标节点最佳路径的估计代价。 A*能找到最优解的条件，关键在于估价函数h(n)的选取；若估价值<实际值, 则能保证得到最优解。 4.3运行结果： 四、比较结论 节点数路径长度效率Optimality: Completeness: BFS114502NoYESDFS（一般） 126053NoNODFS（回溯+剪枝）304185YESYESGreedy84501NONOA*算法164184YESYES 通过比较，Greedy搜索生成的结点数目最少，为8个，效率最高； DFS（回溯+剪枝）生成的结点数目最多，为30个，效率最低。DFS（一般）、BFS和Greedy搜索找到的都不一定最优解，DFS（回溯+剪枝）和A*算法具有完备性且始终找到的都是最优解。宽度优先虽然是完备的（如果分支因子有限的话），在任何情况下宽度优先都能找到一个解，但是，它找到的第一个解并非最优的，此外，最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时，它将耗费大量的时间。宽度优先时间复杂度：（b为分支因子，d为深度）；空间复杂度为所存储的节点的个数。DFS不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。深度优先的时间复杂度：；空间复杂度：（b为分支因子，m为深度，仅有一枝需要存储）；。贪婪算法不是完备的。同时，它找到的解也不一定是最优解。其时间复杂度：（b代表分支数，m为深度）；空间复杂度为）。所以只有A*算法和DFS（回溯+剪枝）是完备的，且能够找到最优解；其时间复杂度：扩展节点的数目；空间复杂度：所有生成的结点。综合来看，BFS和贪婪算法的效率较高，但解并非最优，而A*算法的效率稍逊色，但解为最优；DFS（回溯+剪枝）搜索虽能找到最优解但效率最低。N皇后问题 一、问题描述：（1）n皇后问题：在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上， （2）分别用回溯法（递归）、GA算法和CSP最小冲突法求解n皇后问题。要求：. 输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率，并列表给出结果。. 比较同一算法在n不相同时的运行时间，分析算法的时间复杂性，并列表给出结果二、数据结构int *NQueen = new intn三、实现算法1、回溯法1.1数据结构： int *NQueen = new intn;1.2算法思想： 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于n皇后问题，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了，在目标状态终止。1.3运行结果:回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在n>35时，用回溯法已不能较好的解决n皇后问题。2、遗传算法2.1数据结构： int *arry =NULL; arry=new int *zhongqun;/种群 arryi=new int n+1;/个体2.2算法思想：遗传算法（Genetic Algorithm）是模拟物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。对于一个求函数最大值的优化问题，首先初始化，包括种群的大小，编码的方案，遗传的代数，变异的概率，等等；然后进行选择操作；接着是将选择的个体进行交叉；然后再进行选择，并将选择的个体进行变异；最后就是更新最优值了。大概分为：初始化，循环杂交、变异、选择、检测解，终止计算。2.3运行结果遗传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间长，且容易受参数的影响。3、CSP最小冲突法3.1数据结构： struct dd int csp;/冲突数 int position;/位置 ; dd *arry; NQueen=new intn;/皇后矩阵 arry=new ddn;/CSP矩阵3.2算法思想：最小冲突法基本思想和爬山法相同，每次寻找使冲突值最小的状态，直至找到冲突值为0的情况、既满足条件的N皇后摆放位置。3.3运行结果: 与爬山法一样CSP最小冲突法容易陷入局部最优，86%的时间会卡住；但是CSP最小冲突法较简单，在皇后的个数较多时体现出来效率最高，处理多约束大规模问题时往往不能得到较好的解。四、比较结论 Nt/ms816 24 32 3550 64100200回溯1111511027142469812865301 - - - -GA1140243931 - - 9103451819280 - -CSP470 16 156 500 62512972266139898回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在n=35时，用回溯法已不能较好的解决n皇后问题。遗传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间中等，且容易受n值的影响。遗传算法的运行时间在n很小时没有回溯法快，但是随着n值的增加，遗产算法的优点也就显现出来，它能够解决回溯法不能解决的问题。CSP最小冲突法是一种始终都比较快的算法，它的运行时间与皇后是个数没有必然的联系，而且在n很大时，它显现出来运行时间短，效率高的优势，但它的缺点是会出现山脊、高原，86%的时间会卡住。总的来说，CSP最小冲突法较简单，也比较快，在皇后的个数较多时体现出来效率最高，处理多约束大规模问题时往往不能得到较好的解。 总的来说，回溯在n值很小时，效率很高，但其求解范围很小，超过35基本就解不出来，遗传算法求解范围适中。在n值很大(>100)时，前两者都不能再解决，此时，CSP最小冲突法的效率最高，且与n值没有必然的联系。总结 通过此次课程实习不仅大大加深了我对几种经典搜索算法的理解，而且帮助我很好的复习了队列、堆栈、图、文件读写这几部分的内容，使我对几种基本的数据结构类型的运用更加熟练。在解决这些问题的过程中我不但很好的巩固了数据结构的相关知识，而且提高了编程及程序调试能力，增强了自己编程的信心。 总之，在这次课程实习过程中我是实实在在学到了一些课堂上学不到的东西，同时也提高了实践能力。同时在这个过程中也暴露了自己的不少问题，在今后的学习过程成也会更加有针对性。最后还要感谢老师的悉心指导，解答我编程过程中的疑问、指出我程序中的不足，及提出可行的解决方法，让我的程序的功能更加完善。附源代码 罗马尼亚问题 /*罗马尼亚问题*/*代码清单：Graph.hStack.hQueue.hmain.cpp*/ /*Graph.h*#include<iostream.h>#include<stdlib.h>#include<fstream.h>#include<string.h>#define MaxV 20 typedef structchar cityname20;int value;int cost;Ver;typedef structVer VMaxV;int edgeMaxVMaxV;int numofedges;Graph;void Read_V(Graph &G) int i,v;char ch20;fstream infile("heuristic_value.txt",ios:in); i=0; while(infile>>ch && infile >>v) G.Vi.value=v;G.Vi.cost=0;strcpy(G.Vi.cityname,ch);i+;void Read_edge(Graph &G)int valu,i;fstream infile("map.txt",ios:in); i=0; while(infile>>valu) G.edgei/20i%20=valu;/cout<<G.edgei/20i%20;i+; int GetFirstV(Graph G,int v)int col;if(v<0|v>=20)return -1;for(col=0;col<20;col+)if(G.edgevcol>0&&G.edgevcol<1000)return col;return -1;int GetNextV(Graph G,int v1,int v2)int col;if(v1<0|v1>=20|v2<0|v2>=20)return -1;for(col=v2+1;col<20;col+)if(G.edgev1col>0&&G.edgev1col<1000)return col;return -1; /*Stack.h*#include<iostream.h>#include"Graph.h"typedef structint a100;int top1;int weight;Stack;bool StackNotFull(Stack *st)if(st->top1<100)return true;else return false;bool StakNotEmpty(Stack *st)if(st->top1>0)return true;elsereturn false;void InitiateStack(Stack *st) st ->top1=0;st->weight=0;void StackPop(Stack *st,Graph G) int x;if( StakNotEmpty(st)st->top1-; x=st->ast->top1; if(st->top1>0 )st->weight=st->weight-G.edgest->ast->top1-1x;elsecout<<"栈已空！"<<endl;void StackPush(Stack *st,int x,Graph G)if(StackNotFull(st)st->ast->top1=x;if(st->top1>0 )st->weight=st->weight+G.edgest->ast->top1-1st->ast->top1;st->top1+;elsecout<<"栈已满！"<<endl;void PrintStack(Stack *st,Graph G)int x;x=0;while(x<st->top1)cout <<G.Vst->ax.cityname<<" "x+;/cout<<"路径长度为："<<st->weight<<endl;cout<<endl;/* Queue.h *#include"iostream.h"#include "Stack.h"#define MaxSize 30typedef structint queueMaxSize;int rear;int front;int count; SeqCQuene;void QueueInitiate(SeqCQuene *Q)Q->rear=0;Q->front=0;Q->count=0;int QueueNotEmpty(SeqCQuene Q)if(Q.count!=0)return 1;else return 0;int QueueAppend(SeqCQuene *Q,int x)if(Q->count>0&&Q->rear=Q->front)cout<<"队列已满"<<endl;return 0;elseQ->queueQ->rear=x;Q->rear =(Q->rear +1)%MaxSize;Q->count +;return 1;int QueueDelete(SeqCQuene *Q,int *d)if(Q->count =0)cout<<"队列已空"<<endl;return 0;else*d=Q->queue Q->front;Q->front=(Q->front+1)%MaxSize;Q->count-;return 1;int QueueOrderAppend(SeqCQuene *Q,int x,Graph G)if(Q->count>0 && Q->rear = Q->front)cout<<"队列已满"<<endl;return 0;elseif(Q->count=0 |G.Vx.value>=G.VQ->queueQ->rear-1.value)/gai队尾插入Q->queueQ->rear=x;Q->rear =(Q->rear +1)%MaxSize;Q->count +;return 1;elseif( G.Vx.value<=G.VQ->queueQ->front.value)/队头插入Q->queueQ->front-1=x;Q->front =(Q->front-1+MaxSize)%MaxSize;Q->count +;return 1;else /排序找位置插入int position=Q->front;while(G.Vx.value>G.VQ->queueposition.value)position+;for(int i=Q->front;i<position;i+)Q->queue(i-1+MaxSize)%MaxSize=Q->queuei%MaxSize;Q->queue(i-1+MaxSize)%MaxSize=x;Q->front =(Q->front-1+MaxSize)%MaxSize;Q->count +;/A*int Queue_A_OrderAppend(SeqCQuene *Q,int x,Graph G)if(Q->count>0 && Q->rear = Q->front)cout<<"队列已满"<<endl;return 0;elseif(Q->count=0 |G.Vx.value+G.Vx.cost>G.VQ->queueQ->rear-1.value+G.VQ->queueQ->rear-1.cost)/队尾插入Q->queueQ->rear=x;Q->rear =(Q->rear +1)%MaxSize;Q->count +;return 1;elseif( G.Vx.value+G.Vx.cost<G.VQ->queueQ->front.value+G.VQ->queueQ->front.cost)/队头插入Q->queueQ->front-1=x;Q->front =(Q->front-1+MaxSize)%MaxSize;Q->count +;return 1;else /排序找位置插入int position=Q->front;while(G.Vx.value+G.Vx.cost > G.VQ->queueposition%MaxSize.value+G.VQ->queueposition%MaxSize.cost)position+;for(int i=Q->front;i<position;i+)Q->queue(i-1+MaxSize)%MaxSize=Q->queuei%MaxSize;Q->queue(i-1+MaxSize)%MaxSize=x;Q->front =(Q->front-1+MaxSize)%MaxSize;Q->count +;/*main.cpp *#include "Queue.h"typedef structint father;int me;way; way *b=new way100;int i=0;int end=2;int count=0;int visitedCity20;void Visit(int v, int u)bi.father=u;bi.me=v;i=i+1;void PrintBW(Graph G,way *b,int end,int start) int Bway=0;cout<<"遍历路径为（反序）："cout<<G.Vend.cityname<<" " while(1)for(int j=0;j<i;j+) if(bj.me=end)cout<<G.Vbj.father.cityname<<" "Bway+=G.edgebj.mebj.father;end=bj.father; if(end=start)break; cout<<endl; cout<<"路径长度为："<<Bway<<endl<<"生成节点数为："<<count<<endl;void BroadFSearch(Graph G,int v) int visited20=0;int u,w;i=0;SeqCQuene queue;visitedv=1; count+;if(v=end)return;QueueInitiate(&queue);QueueAppend(&queue,v);while(QueueNotEmpty(queue)QueueDelete(&queue,&u);w=GetFirstV(G,u);while(w!=-1)if(!visitedw) Visit( w,u);visitedw=1;count+;if(w=end)PrintBW( G, b,end,v);/ return;QueueAppend(&queue,w);w=GetNextV(G,u,w);/int MaxWeight=10000;void DepthFSearch(Graph G,int v,int visited,Stack *st)int w;i=0; visitedv=1;count+;StackPush( st,v,G);if(v=end|st->weight>=MaxWeight)w=-1;if(v=end&&st->weight<=MaxWeight)cout<<"深度优先遍历路径为：" ;PrintStack(st,G);if(MaxWeight>st->weight)MaxWeight=st->weight;cout<<"路径长度为："<<st->weight<<endl<<"生成节点数为："<<count<<endl; else w=GetFirstV(G,v); while(w!=-1)if(!visitedw)DepthFSearch(G,w,visited,st);w=GetNextV(G,v,w);visitedv=0;StackPop(st, G);void Greedy(Graph G,int v);void A(Graph *G,int v);void main()Graph G;Graph * p=&G;Read_V(G);Read_edge(G);/cout<<""<<"宽度优先："<<endl ;BroadFSearch(G,0);/cout<<""<<"深度优先"<<endl;int visited20=0;count=0;Stack *st;st=new Stack;InitiateStack( st);DepthFSearch( G, 0,visited,st);cout<<"确定深度优先找到最优路径为："<<MaxWeight<<endl;cout<<"确定深度优先找到最优解生成节点数为："<<count<<endl;/cout<<""<<"贪婪算法："<<endl ; Greedy( G,0);PrintBW( G, b,end,0); /cout<<""<<"A星算法："<<endl ;A(p, 0);/贪婪算法void Greedy(Graph G,int v) i=0;count=0; int visited20=0;int u,w;SeqCQuene queue; visitedv=1; if(v=end)return;QueueInitiate(&queue);QueueOrderAppend(&queue,v,G);count+;while(QueueNotEmpty(queue)QueueDelete(&queue,&u);if(u=end)count+;return;w=GetFirstV(G,u);while(w!=-1) if(!visited