毕业设计(论文)开题报告 分支限界算法的研究与实现

毕业设计（论文）开题报告

计算机科学与信息工程 学院 2013 届

题 目 分支限界算法的研究与实现 Research and application of branch threshold algorithm 课题类型 应用研究 课题来源 老师指定 学生姓名 李瑞杰 学 号 200903010017 专业班级 09届计算机科学与技术（应用） 指导教师 冯慧玲 职 称 讲师

填写日期： 2013 年 3 月 30 日

一、本课题研究的主要内容、目的和意义 1.课题内容 以旅行售货员问题、0/1背包问题、作业分配问题、布线问题、货物装载问题为例进行算法的分析、设计、实现及模拟演示。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 在现实生活中，有这样一类问题：问题有n个输入，而问题的解就由n个输入的某种排列或某个子集构成，只是这个排列或子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约定条件的排列或子集称为该问题的可行解。满足约束条件的子集可能不止一个，也就量说可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也可能给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解。如工作安排问题，任意顺序都是问题的可行解，人们真正需要的是最省时间的最优解。 2.研究方法 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3.课题研究的意义 用回溯算法解决问题时，是按深度优先的策略在问题的状态空间中，尝试搜索可能的路径，不便于在搜索过程中对不同的解进行比较，只能在搜索到所有解的情况下，才能通过比较确定哪个是最优解。这类问题更适合用广度优先策略搜索，因为在扩展结点时，可以在E-结点的各个子结点之间进行必要的比较，有选择地进行下一步扩展。分支限界法就是一种比较好的解决最优化问题的算法。分支限界法是由“分支”策略和“限界”策略两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索；“限界”策略是为了加速搜索速度而采用启发信息剪枝的策略。 二、文献综述（国内外相关研究现况和发展趋向） 1.常见的两种分支限界法 （1) FIFO搜索 先进先出搜索算法要依赖“队”做基本的数据结构。一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点为当前扩展结点,„„,直到找到一个解或活结点队列为空为止。 （2) LIFO搜索 后进先出搜索算法要依赖“栈”做基本的数据结构。一开始,根结点入栈.从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再众栈中弹出一个结点为当前扩展结点,„„，直到找到一个解或栈为空为止。 2.分支限界法与回溯法的不同 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 3.解空间树的动态搜索 （1）回溯求解0/1背包问题，虽剪枝减少了搜索空间，但整个搜索按深度优先机械进行，是盲目搜索（不可预测本结点以下的结点进行的如何）。 （2）回溯求解TSP也是盲目的（虽有目标函数，也只有找到一个可行解后才有意义） （3）分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up]；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的down，对最大化问题，估算结点的up）。如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理表。 三、拟采取的研究方法（方案、技术路线等）和可行性论证 1.拟采取的研究方法 分支限界有3种不同的搜索方式:FIFO、LIFO和优先队列。以旅行售货员问题、0/1背包问题、作业分配问题、布线问题货物装载问题为例进行算法的分析、设计、实现及模拟演示。 2.系统软件及开发平台 硬件平台： CPU：AMD X2 240 2.80GHz 内存：2.00GB 软件平台： 开发工具包：VC++6.0 服务器：运行服务器采用Windows XP 四、预期结果（或预计成果） 完成算法设计与分析中关于分支限界问题的分析，设计，实现及模拟演示。 1.以旅行售货员问题为例进行算法的分析、设计、实现及模拟演示。 2.以0/1背包问题为例进行算法的分析、设计、实现及模拟演示。 3.以作业分配问题为例进行算法的分析、设计、实现及模拟演示。 4.以布线问题为例进行算法的分析、设计、实现及模拟演示。 5.以货物装载问题为例进行算法的分析、设计、实现及模拟演示。 最后，高质量的完成论文，顺利通过毕业答辩。 五、研究进度安排 时间 任务 3.04-3.11 搜集相关资料、课题调研，根据任务书初拟开发计划； 3.12-3.19 写需求规格说明书，设计每一问题的研究思路； 3.20-3.27 翻译英文文献，撰写开题报告，初步完善各种问题的解决； 3.28-4.03 提交开题报告，并根据指导老师意见修改开题报告； 4.04-4.11 对分支限界问题进行详细设计； 4.12-4.19 完成分支限界问题的详细设计，根据导师的意见修改； 4.20-4.27 拟出解决问题的基本构架，对系统进行编码； 4.28-5.04 对每一问题进行详细的设计； 5.05-5.12 对每一问题功能模块进行测试，在导师的指导下进行修改； 5.13-5.20 写毕业设计论文，根据指导老师的意见对其进行修改和完善； 5.21-5.28 完成毕业设计论文，提交其他文档，参与毕业答辩。 六、主要参考文献 [1]Anany Levitin．算法设计与分析基础[M]．潘彦，译．北京：清华大学出版社，2004：79一154 [2]严蔚敏，吴伟民．数据结构[M]．北京：清华大学出版社，1997：142—147 [3]王晓东．计算机算法设计与分析(第2版)[M]．北京：电子工业出版社，2005：86一113 [4]宋文，吴晟，杜亚军，算法设计与分析[M]．重庆大学出版社，重庆，2008 [5]李根强，数据结构[M]．中国水利水电出版社，北京，2002 [6]冯舜玺，李学武，裴伟东，算法分析导论[M]．机械工业出版社，北京，2006 [7]李建学,李光元,吴春芳.数据结构课程设计案例精编[D].清华大学.2007 [8]李昌坤.JPEG2000标准算法研究及改进[D].四川大学.2005 [9]应莉 0-1背包问题及其算法 计算机与现代化 （2009）06-0024-03 [10]徐颖 回溯法在0-1背包问题中的应用 软件导刊（2008）12-0054-02 七、审核意见 指导教师对开题的意见： 指导教师签字： 年 月 日 院系审核意见： 审核人签字： 年 月 日 说明：1、该表每生一份，院系妥善存档；

2、课题来源填：“国家、部、省、市科研项目”或“企、事业单位委托”或“自拟课题”或 “其它”；课题类型填：“设计”或“论文”或 “其它”。