算法论文设计分治法和分支限界

《算法论文设计分治法和分支限界》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档成绩评定表学生姓名xx班级学号xx专业信息与计算科学课程设计题目1.分治法解决最近距离问题2.分支限界解决旅行商售货员问题评语组长签字：成绩日期标准文案实用文档20年月日课程设计任务书学院理学院专业信息与计算科学学生姓名xx班级学号xx课程设计题目1.分治法解决最近距离问题2.分支限界解决旅行商售货员问题标准文案实用文档实践教学要求与任务:1、巩固和加深对计算机算法分析与设计基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。4、具体任务

2、（1）分治法解决最近距离问题（2）分支限界解决旅行商售货员问题工作计划与进度安排:第一天查阅资相关料；第二、三天程序设计；第四天程序调试；第五天答辩指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要标准文案实用文档计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂，计算量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题，这就产生了理论可计算而现实不可计算的矛盾，而算法设计与分析的任务就是对各类具体的问题设计高质量的算法，以及研究设计算法的一般

3、规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。问题一：运用分治法对多点最近距离问题进行算法设计，把问题分解为不是相互独立的子问题，计算保存子问题的答案，从而再求重复子问题时可以直接找到答案。通过反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。问题二：运用分支限界对旅行商售货员问题进行算法设计，求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。）分支限界法首先确定一个合理的限界函数，并根据限界函

4、数确定目标函数的界；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的下界，对最大化问题，估算结点的上界）。如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理。关键词：算法设计与分析；分支限界法；分治法标准文案实用文档目录1分治法解决最近距离问题11.1问题描述11.2算法设计21.3算法实现31.4运行结果与分析62分支限界解决旅行商售货员问题72.1问

5、题描述72.2算法设计82.3算法实现92.4运行结果与分析14总结15参考文献16标准文案实用文档1分治法解决最近距离问题1.1问题描述已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。算法每次选择一条垂线L，将S拆分左右两部分为SL和SR，L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2，（否则以其他方式划分S，有可能导致SL和SR中点数目一个为1，一个为n-1，不利于算法效率，要尽量保持树的平衡性）依次找出这两部分中的最小点对距离：δL和δR

6、，记SL和SR中最小点对距离δ=min（δL，δR），如图1.1：图1.1以L为中心，δ为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处，如图1.1中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于δ，最小点对计算才有意义。标准文案实用文档1.2算法设计　　分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。　　分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则

7、将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。　　如果原问题可分割成k个子问题，1

8、对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法在每一层递归上都有三个步骤：　　分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；　　解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；　　合并：将各个子问题的解合并为原问题的解。分治法所能解决的问题一般具有以下几个特征：　　1)该问题的规模缩小到一定的程度就可以容易地解决