1、 I 成成 绩绩 评评 定定 表表 学生姓名 班级学号 专 业 信息与计算 科学 课程设计题目 1.分支限界解决布 线问题2.船只停泊 港口管理动态规划 解决最长公共子序 列问题 评 语 组长签字： 成绩 日期 20 年 月 日 II 课程设计任务书课程设计任务书 学 院 理学院 专 业 信息与计算科学 学生姓名 班级学号 课程设计题目 1. 分支限界解决布线问题 2. 动态规划解决最长公共子序 列问题 实践实践教学教学要求与任务要求与任务: : 1、巩固和加深对计算机算法分析与设计基本知识的理解。 2、初步掌握简单软件的分析方法和设计方法。 3、了解与课程有关的工程技术规范，能正确解释和分析
2、设计结果。 4、具体任务 （1）分支限界解决布线问题 （2）动态规划解决最长公共子序列问题。 工作计划与进度安排工作计划与进度安排: : 第一天 查阅资相关料； 第二、三天 程序设计； 第四天 程序调试； 第五天 答辩 指导教师： 201 年 月 日 专业负责人： 201 年 月 日 学院教学副院长： 201 年 月 日 III 摘 要 “计算机算法设计与分析” 着重介绍了计算机算法设计领域的基本原则和 根本原理。深入分析了一些计算机模型上的算法，介绍了一些和设计有效算法有 关的数据结构和编程技术，为读者提供了有关递归方法、分治方法和动态规划方 面的详细实例和实际应用，并致力于更有效算法的设计
3、和开发。同时，对 NP 完 全等问题能否有效求解进行了分析，并探索了应用启发式算法解决问题的途径。 本文第一问，随着信息技术的发展和嵌入式设备的广泛使用电路布线问题 越来越受到人们的重视要使电子电路获得最佳性能不仅元器件的布置占有着 重要的地位而且导线的布设也是非常重要的特别是在涉及到线路成本的布线 方案中一个好的布线算法就显得尤为重要 本文首先对一类电路板低成本布线 问题进行了分析进而给出了解决这一问题的分支限界解法并对所提出算法的 时间复杂度进行了分析和讨论。 本文第二问，掌握动态规划法的原理，并能够按其原理编程实现求两个序列 数据的最长公共子系列，以加深对其的理解。 关键字关键字：分支限
4、界；布线问题；动态规划 IV 目 录 1 分支限界解决布线问题 1 1.1 问题重述 1 1.2 问题分析 1 1.3 算法分析与设计 2 1.4 算法的实现与结果 3 2 动态规划解决最长公共子序列问题 9 2.1 问题重述 9 2.2 问题分析 9 2.3 算法分析与设计 9 2.4 算法实现与结果 10 参考文献 15 1 1 分支限界解决布线问题 1.1 问题重述 布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。精确的电 路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。在布线时，电 路只能沿直线或直角布线，如图1所示。为了避免线路相交，已经布线的方格做 了封锁标记（如图1中阴影部分） ，其他线路不允许穿过被封锁的方格。 1.2 问题分析 题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决 问题，也就是从a开始朝着b的方向垂直布线即可。实际上，再看一下图2，就知 道贪婪算法策略是行不通的。 因为已布线的放个没有规律的所以直观上说只能用 搜索方法去找问题的解。 根据布线方法的要求，除边界或已
