n皇后问题和罗马尼亚问题实习报告.doc
《n皇后问题和罗马尼亚问题实习报告.doc》由会员分享,可在线阅读,更多相关《n皇后问题和罗马尼亚问题实习报告.doc(39页珍藏版)》请在三一文库上搜索。
1、 人工智能课程实人工智能课程实 习报告习报告 题目: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
2、 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 四
3、、比较结论四、比较结论.14 总结总结.15 附源代码附源代码.15 罗马尼亚问题 .15 N 皇后问题.26 递归算法.27 遗传算法.29 csp 最小冲突法.35 罗马尼亚问题罗马尼亚问题 一、问题描述一、问题描述 (1)罗马尼亚问题:Find Bucharest starting at Arad 分别用宽度优先、深度优先、贪婪算法和 A*算法求解“罗马利亚度假 问题”。要求:分别用文件存储地图和启发函数表,用生成节点数比较几 种算法在问题求解时的效率,列表给出结果。 (2)附(罗马尼亚地图) (3) (3)各结点启发值: 二、图的数据结构二、图的数据结构 (1)节点信息: typede
4、f 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 Queu
5、eDelete(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 的其他顶点 ,找出并存进待 扩展结点表,等待扩展,每次先判断待扩展结点表是否为空,若否则从待扩 展结点表中取出一个结
6、点进行扩展,并将扩展后的结点存进该表,若是,则 返回失败。该算法同时能生成一棵根为 Arad 且包括所有可达顶点的宽度优 先树 1.3 运行结果:运行结果: 2.深度优先深度优先 2.1 数据结构:数据结构: 堆栈 typedef struct int a100;记录入栈城市序号 int top1;栈顶 int weight;最大路径用于剪枝 Stack; 2.2 算法思想:算法思想: 深度优先搜索是一种每次都要达到被搜索结构的叶结点的搜索方法 ,直到 不能再深入为止,然后返回到另一个结点,继续对该结点进行深搜。当有目标 结点出现时,返回目标结点,搜索结束;否则,若待扩展结点表已空,且未找 到
7、目标结点,则返回失败,停止搜索。 同样,深度优先搜索从 Arad 结点出发,判断是否为目标结点,若否,探寻 与该结点相连的结点,算法首先搜索一条分支上的所有顶点,然后再去搜索和 Arad 的其它分支结点,找出并存进待扩展结点表,等待扩展,每次先判断待扩 展结点表是否为空,若否,则从待扩展结点表中取出一个结点进行扩展,并将 扩展后的结点存进该表,若是,则返回失败。该算法同时能生成一棵根为 Arad 且包括所有可达顶点的深度优先树。 在深度优先搜索中,我用到堆栈来存储待扩展结点表。 2.3 运行结果:运行结果: 说明:深度优先找到解生成的节点数为 12,路径长度为 605,程序中增加回溯 和剪枝功
8、能,所以会继续搜索优于当前解的路径,当生成 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 QueueDe
9、lete(SeqCQuene *Q,int *d); int QueueOrderAppend(SeqCQuene *Q,int x,Graph G);越小优先级越高 记录父亲用于打印路径 typedef struct int father; int me; way; 3.2 算法思想:算法思想: 贪婪算法是指,在对问题求解时,总是做出在当前看来是最好的选择。贪婪 算法不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。贪 婪算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他 能产生整体最优解或者是整体最优解的近似解。 在解决罗马尼亚度假问题时,贪婪算法通过比较每个待
10、扩展结点的 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); in
11、t 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 数
12、据结构:数据结构: int *arry =NULL; arry=new int *zhongqun;/种群 arryi=new int n+1;/个体 2.2 算法思想:算法思想: 遗传算法(Genetic Algorithm)是模拟物进化论的自然选择和遗传学机理的 生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 对于一个求函数最大值的优化问题,首先初始化,包括种群的大小,编码的方 案,遗传的代数,变异的概率,等等;然后进行选择操作;接着是将选择的个 体进行交叉;然后再进行选择,并将选择的个体进行变异;最后就是更新最优 值了。 大概分为:初始化,循环杂交、变异、选择、检测
13、解,终止计算。 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;/
14、CSP 矩阵矩阵 3.2 算法思想:算法思想: 最小冲突法基本思想和爬山法相同,每次寻找使冲突值最小的状态,直至找 到冲突值为 0 的情况、既满足条件的 N 皇后摆放位置。 3.3 运行结果运行结果: 与爬山法一样 CSP 最小冲突法容易陷入局部最优,86%的时间会卡住;但是 CSP 最小冲突法较简单,在皇后的个数较多时体现出来效率最高,处理多约束 大规模问题时往往不能得到较好的解。 四、比较结论 N t/ms 816 24 32 3550 64100200 回溯1111511027142469812865301 - - - - GA1140243931 - - 9103451819280 -
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 罗马尼亚 实习 报告
链接地址:https://www.31doc.com/p-11057540.html