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

人工智能课程实人工智能课程实 习报告习报告 题目：n 皇后问题和罗马尼亚问题皇后问题和罗马尼亚问题 班号： 191122 学号： 20121003553 姓名： 叶叶 超超 指导老师：赵曼赵曼 2014.11 目录目录 人工智能课程实习报告人工智能课程实习报告.1 目录目录.2 罗马尼亚问题罗马尼亚问题.4 一、问题描述一、问题描述.4 二、图的数据结构二、图的数据结构.5 三、实现算法三、实现算法.5 1.宽度优先 .5 1.1数据结构：.5 1.2算法思想：.6 1.3运行结果：.6 2.深度优先 .7 2.1数据结构：.7 2.2算法思想：.7 2.3运行结果：.7 3.贪婪算法 .8 3.1数据结构：.8 3.2算法思想：.8 3.3运行结果：.8 4.A*算法.9 4.1数据结构：.9 4.2算法思想：.9 4.3运行结果：.9 四、比较结论四、比较结论.9 N N 皇后问题皇后问题.11 一、问题描述一、问题描述：.11 二、数据结构二、数据结构.11 三、实现算法三、实现算法.11 1、回溯法 .12 1.1数据结构：.12 1.2算法思想：.12 1.3运行结果:.12 2、遗传算法 .12 2.1数据结构：.13 2.2算法思想：.13 2.3运行结果.13 3、CSP 最小冲突法.13 3.1数据结构：.13 3.2算法思想：.14 3.3运行结果:.14 四、比较结论四、比较结论.14 总结总结.15 附源代码附源代码.15 罗马尼亚问题 .15 N 皇后问题.26 递归算法.27 遗传算法.29 csp 最小冲突法.35 罗马尼亚问题罗马尼亚问题 一、问题描述一、问题描述 （1）罗马尼亚问题：Find Bucharest starting at Arad 分别用宽度优先、深度优先、贪婪算法和 A*算法求解“罗马利亚度假 问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几 种算法在问题求解时的效率，列表给出结果。 （2）附（罗马尼亚地图） （3） （3）各结点启发值： 二、图的数据结构二、图的数据结构 (1)节点信息： typedef struct char cityname20;城市名 int value;启发函数值 int cost;路径花费 Ver; ()地图信息 typedef struct Ver VMaxV;一维城市数组 int edgeMaxVMaxV;二维边数组 int numofedges; Graph; （3）图的操作函数 void Read_V(Graph 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 struct int 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 struct int 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 struct int 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)的选取；若估价值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 数据结构：数据结构： structstruct dddd intint csp;/csp;/冲突数冲突数 intint position;/position;/位置位置 ; dddd *arry;*arry; NQueen=newNQueen=new intn;/intn;/皇后矩阵皇后矩阵 arry=newarry=new ddn;/CSPddn;/CSP 矩阵矩阵 3.2 算法思想：算法思想： 最小冲突法基本思想和爬山法相同，每次寻找使冲突值最小的状态，直至找 到冲突值为 0 的情况、既满足条件的 N 皇后摆放位置。 3.3 运行结果运行结果: 与爬山法一样 CSP 最小冲突法容易陷入局部最优，86%的时间会卡住；但是 CSP 最小冲突法较简单，在皇后的个数较多时体现出来效率最高，处理多约束 大规模问题时往往不能得到较好的解。 四、比较结论 N t/ms 816 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.h Stack.h Queue.h main.cpp*/ /*Graph.h* #include #include #include #include #define MaxV 20 typedef struct char cityname20; int value; int cost; Ver; typedef struct Ver VMaxV; int edgeMaxVMaxV; int numofedges; Graph; void Read_V(Graph char ch20; fstream infile(heuristic_value.txt,ios:in); i=0; while(infilech G.Vi.cost=0; strcpy(G.Vi.cityname,ch); i+; void Read_edge(Graph fstream infile(map.txt,ios:in); i=0; while(infilevalu) G.edgei/20i%20=valu; /cout<<G.edgei/20i%20; i+; int GetFirstV(Graph G,int v) int col; if(v=20) return -1; for(col=0;col0 return -1; int GetNextV(Graph G,int v1,int v2) int col; if(v1=20|v2=20) return -1; for(col=v2+1;col0 return -1; /*Stack.h* #include #includeGraph.h typedef struct int a100; int top1; int weight; Stack; bool StackNotFull(Stack *st) if(st-top1top10) return true; else return 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-top10 ) st-weight=st-weight-G.edgest-ast-top1-1x; else cout<<栈已空！<ast-top1=x; if(st-top10 ) st-weight=st-weight+G.edgest-ast-top1-1st-ast-top1; st-top1+; else cout<<栈已满！<<endl; void PrintStack(Stack *st,Graph G) int x; x=0; while(xtop1) cout <ax.cityname<< ; x+; /cout<<路径长度为：<weight<<endl; cout<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-count0 Q-rear =(Q-rear +1)%MaxSize; Q-count +; return 1; int QueueDelete(SeqCQuene *Q,int *d) if(Q-count =0) cout<<队列已空<queue Q-front; Q-front=(Q-front+1)%MaxSize; Q-count-; return 1; int QueueOrderAppend(SeqCQuene *Q,int x,Graph G) if(Q-count0 Q-rear =(Q-rear +1)%MaxSize; Q-count +; return 1; else if( G.Vx.valuequeueQ-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.valueG.VQ-queueposition.value)position+; for(int i=Q-front;iqueue(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-count0 Q-rear =(Q-rear +1)%MaxSize; Q-count +; return 1; else if( G.Vx.value+G.Vx.costqueueQ- 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;iqueue(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 struct int 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<weight=MaxWeight) w=-1; if(v=end cout<<路径长度为：<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;