《算法设计与分析》实验指导书-xin
4页1、算法设计与分析实验指导书实验一 递归与分治1、实验目的(1)掌握设计有效算法的分治策略;(2)通过合并排序和快速排序两个示例学习分治策略设计技巧。2、实验要求(1)熟练掌握分治法的基本思想及其应用实现;(2)理解所给出的算法,并对其加以改进。3、实验内容(1)分治法基本思想如果原问题可分割成k个子问题,1=Wi), fi-1,j 这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为fv;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”,此时能获得的最大价值就是fv-c再加上通过放入第i件物品获得的价值。 这样,可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值,也就是fn,w 。实验三 贪心算法1、 实验目的(1)掌握设计贪心算法的基本思想;(2)通过最优装载、单源最短路径实例理
2、解贪心算法设计的策略。2、实验要求(1)熟练掌握贪心算法的基本思想及其应用实现;(2)理解所给出的算法,并对其加以改进。3、实验内容贪心算法:总是作出在当前看来最好的选择,而不考虑对后面的未处理部分这种选择是否合理,并且已有的选择不会改变。贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。注意:贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解,如单源最短路经问题,最小生成树问题等;在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。4、实验方法1)最优装载:一批集装箱要装上一艘载重量为 c 的轮船。其中集装箱 i 的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。 2)单源最短路径:给定带权有向图G =(V,E),其中每条边的权是非负实数。给定V中的一个顶点,称为源。要求:计算从源到所有其它各顶点的最短路长度。说明:路的长度是指路上各边权值之和。注意:路长最短不一定边数最少。实验四 回溯法1、 实验目的(1)掌握设计回溯法的基本思想;(2)通过-n后问题、旅行售货员问题理解回溯算法设计的策略。2、实验要求(1)熟练掌握回溯算法的基本思想及其应用实现;(2)理解所给出的算法,并对其加以改进。3、实验内容回溯法:回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树;算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。4、实验方法1)n后问题:在88的棋盘上摆放八个皇后;使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上;把八皇后问题扩展到n皇后问题,即在nn的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。2)旅行售货员问题:某售货员要到若干城市去推销商品,已知各城市之间的路程(旅费),他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(总旅费)最小。注意:各算法程序实现见教材。
《《算法设计与分析》实验指导书-xin》由会员cn****1分享,可在线阅读,更多相关《《算法设计与分析》实验指导书-xin》请在金锄头文库上搜索。
2022年高三生物复习 精选专题练 DNA的结构与复制(含解析)
2012版国寿新康宁终身重大疾病保险条款8页
实习生自我鉴定
常用电路图及电器地文字符号和图形符号
幼儿园中班下学期安全工作总结2023年(2篇).doc
【苏教版】一年级上册数学:第9单元认识10~20各数教案第2课时写数和数的组成
金工实习总结报告范文2
2022年考博英语-吉林大学考试题库及模拟押密卷15(含答案解析)
关于安全的演讲稿3篇
三年级反义词教案
2013-2014学年度上学期语文九年级形成性测试题答案
四年级工作总结.doc
必备实习自我鉴定模板汇总9篇
2022年小学安全工作总结模板汇编7篇
矿泉水厂员工管理制度范文2篇
笔记本电脑维修指导手册(DOC 11页)
简洁的伤感的话语录47条
学校“两基”迎国检汇报材料参考提纲
2022年承包合同模板合集九篇
(完整版)大理石、花岗岩验收标准
2023-12-04 7页
2022-12-21 35页
2023-04-02 61页
2022-07-27 10页
2023-10-08 36页
2023-01-04 12页
2023-01-14 7页
2022-09-25 54页
2023-01-29 24页
2023-08-30 32页