树的最大连通分支问题-说明书.doc

数学与计算机学院 课程设计说明书 课 程 名 称 算法设计与分析 课程设计 课 程 代 码 7106620 题 目 树的最大连通分支问题 年级 专业 班 2008 信息与计算科学 2 班 学 生 姓 名 何德宏 学 号 312008070102221 开 始 时 间 2011 年 12 月 5 日 完 成 时 间 2011 年 12 月 18 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际能 力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 树的最大连通分支问题 目 录 1 1 引引 言言 1 1 1 1 问题的提出 1 1 2 任务与分析 1 2 2 程序的主要功能程序的主要功能 3 3 2 1 树的存储功能 3 2 2 连通分支的计算功能 3 3 3 程序运行平台程序运行平台 3 3 4 4 总体设计总体设计 3 3 4 1 算法设计 3 4 2 流程设计 6 5 5 模块分析模块分析 7 7 5 1 树的存储模块 7 5 2 计算树的最大连通分支模块 9 6 6 系统测试系统测试 1010 7 7 结论结论 1414 8 8 致谢致谢 1515 9 9 参考文献参考文献 1616 附录附录 1717 树的最大连通分支问题 摘摘 要要 随着计算机的普及 人们解决问题的方法也变得多样化 同一个问题总想 用简单实用的方法去解决 其中树的最大连通分支问题就是一个很典型的例子 我们可以用蛮力法和动态规划法去实现 但用动态规划的方法效率更高 因此该 系统利用动态规划的方法编程实现了求解树的最大连通分支问题 该程序能够快 速输入树的结构 并能计算出树的最大连通分支 此外 代码简洁易懂 界面友 好 能一目了然的看出最终的结果 便于操作 关键词 树的最大连通分支 动态规划 1 树的最大连通分支问题 1 1 引引 言言 1 11 1 问题的提出问题的提出 连通分支定义 设 X 是一个拓扑空间 对于 X 中的点的连通关系而言的每一个等价 类称为拓扑空间 X 的一个连通分支 如果 Y 是拓扑空间 X 的一个子集 Y 作为 X 的子 空间的每一个连通分支称为 X 的子集 Y 的一个连通分支 拓扑空间 X 的每一个连 通分支都不是空集 X 的不同的连通分支无交 以及 X 的所有连通分支之并便是 X 本 身 此外 x y X 属于 X 的同一个连通分支当且仅当 x 和 y 连通 树作为一种特殊 的图 它本身就是连通的 里面还有许多的连通子图 当每个顶点加入权值后 可以 计算出权值最大的连通子图 使用的方法可以有很多 其中蛮力法和动态规划是两种 比较典型的方法 相对于蛮力法而言 动态规划的方法效率更高 所以最后选择了动 态规划方法来计算树的最大连通分支问题 1 21 2 任务与分析任务与分析 给定一棵树T 树中每个顶点u都有一个权值w u 而且权值可以是正数或者负数 现在要找到树T的一个连通子图使该子图的权之和最大 要求编程实现计算出树的最大 连通分支 传统的方法为蛮力法 即依次以每一个顶点为根节点 然后找出以该节点为根节点 的所有连通子图 分别计算出连通子图的权值之和 最后找出权值之和最大的连通子 图 便可得出最后的结果 但该方法效率不高 如果给定是一棵有很多节点的树 那 么这效率将会非常低下 为此 我们将使用动态规划的方法来求解此问题 对于以X为 根的子树分两种情况考虑 1 包含根 f x 1 f x 1 等于所有大于0的f son x 1 的和加w x 2 不包含根 f x 0 f x 0 max max f son x 1 f son x 0 记 忆话搜索递归求解 算法分析 最大连通分支在子树或树中 因此对树进行遍历 依次求出以每个结点为树根的 最大连通分支权值 2 树的最大连通分支问题 树根 root T1T2 W0 Wr Wr Wt1 root T1T2 W0 该问题具有两个子性质 最有子结构性质 子问题重叠性质 算法实现 1 对于叶子结点或儿子个数为0的结点 其最大连通分支权值为该 结点的权值 2 某一结点的最大连通权值 0 则将其值加到它的父亲结点的最大连通权值 反 之舍弃该值 3 最后求出根结点的最大连通权值 结束遍历 4 所求最大连通分支权值即结点 的最大连通权值 最后采用动态规划求解 类似于图的后续遍历 这方法避免了很多蛮力法的缺点 因 此效率也得到了很大的提高 树根 root T1 T2 W 0 W 0 3 树的最大连通分支问题 2 2 程序的主要功能程序的主要功能 2 12 1 树的存储功能树的存储功能 要想计算树的最大连通分支 首先需要给定一棵树 因此需要存储树的基本信息 其中最重要的就是节点信息 用结构体来表示 包括结点的权值 weight 结点的父 亲结点 father 结点的儿子结点 child 结点的最大连通分支权值 wmax 和结 点是否被访问过 visited 最后需要用数组 动态创建 表示树 2 22 2 连通分支的计算功能连通分支的计算功能 树创建完后 首先要对树结构进行初始化 并需要输入数据建立树结构 然后确定 一个树根 对每一个结点用动态规划的方法进行遍历 找出最大连通分支并计算出权 值 最后输出最大的连通分支和其权值 3 3 程序运行平台程序运行平台 WINDOWS XP WIN 7 VC 6 0 具体操作如下 进入 Visual C 6 0 开发环境 在开发环境的主窗口中选择 File New 菜单项 在弹出的对话框中单击 Project 选项卡 选择 C Source File 命名为 树的最大连通分支问题 再制定保存路径 单击 OK 键完成新建 再在编辑 窗口中编辑代码 编译 链接 进行调试 执行 然后输出结果 4 4 总体设计总体设计 4 14 1 算法设计算法设计 1 数据结构 struct Cnode 用结构体来表示结点 long weight 结点的权值 int father 结点的父亲结点 int childnum 结点的儿子个数 long wMax 结点的最大连通分支权值 4 树的最大连通分支问题 bool visited 该结点是否被访问过 int save 100 最大连通分支权值来源 2 动态创建数组表示树 Cnode tree new Cnode n 1 3 树的初始化 for i 1 i tree i weight tree i wMax tree i weight tree i save 0 0 tree i save 1 0 tree i save 2 0 tree i save 3 0 tree i save 4 0 tree i save 5 0 4 树结构的建立 cout 请输入各结点的关系 endl for i 1 i u v tree v father u 5 树的最大连通分支问题 tree u childnum cout endl 5 动态规划算法实现计算树的最大连通分支 int root int m 1 for i 1 i0 遍历树 for i 1 i0 tree tree i father wMax tree tree i father wMax tree i wMax tree tree i father save i i for int m 0 m 5 m if tree i save m 0 tree tree i father save m tree i save m 6 树的最大连通分支问题 6 结果的输出 long max tree 1 wMax int h 1 for i 2 imax max tree i wMax h i cout 最大权值为 max endl cout endl cout 最大连通分支包含的结点为 endl for int j 1 j n j if tree h save j 0 cout tree h save j endl if j h cout h endl 4 4 2 2 流程设计流程设计 总体设计的流程图如图 4 1 所示 7 树的最大连通分支问题 图 4 1 总体流程图 5 5 模块分析模块分析 5 15 1 树的存储模块树的存储模块 代码分析 struct Cnode 用结构体来表示结点 long weight 结点的权值 int father 结点的父亲结点 int childnum 结点的儿子个数 开始 初始化 树 动态规划求最 大连通分支 计算最大权值 输出结果 完成 未完成 建立树结构 8 树的最大连通分支问题 long wMax 结点的最大连通分支权值 bool visited 该结点是否被访问过 int save 100 最大连通分支权值来源 树的初始化及建立 cout 请输入树结点的个数 endl n cout endl Cnode tree new Cnode n 1 动态创建数组表示树 cout 请依次输入各结点的权值 endl for i 1 i tree i weight tree i wMax tree i weight tree i save 0 0 tree i save 1 0 tree i save 2 0 tree i save 3 0 tree i save 4 0 tree i save 5 0 cout endl cout 请输入各结点的关系 endl for i 1 i u v tree v father u tree u childnum 5 25 2 计算树的最大连通分支模块计算树的最大连通分支模块 代码分析 int root int m 1 for i 1 i0 遍历树 for i 1 i0 tree tree i father wMax tree tree i father wMax tree i wMax tree tree i father save i i for int m 0 m 5 m if tree i save m 0 10 树的最大连通分支问题 tree tree i father save m tree i save m long max tree 1 wMax int h 1 for i 2 imax max tree i wMax h i cout 最大权值为 max endl cout endl cout 最大连通分支包含的结点为 endl for int j 1 j n j if tree h save j 0 cout tree h save j endl if j h cout h endl 6 系统测试系统测试 程序完成后需要对程序进行测试 在本程序中需要输入树结点的个数 各结点的权值 各节点之间的对应关系 最后即可输出相应的结果 输入树的实例如图 6 1 所示 输 入过程和输入结果如 6 2 到 6 5 所示 11 树的最大连通分支问题 1 1 3 3 1 1 1 1 1 1 1 2 3 4 5 图 6 1 输入实例 图 6 2 输入树结点的个数 图 6 3 输入各结点的权值 图 6 4 各结点的对应关系 每行有表示树 T 的一条 边的 2 个整数 u v 表示顶点 u 与顶点 v 相连 12 树的最大连通分支问题 图 6 5 树的结构图 图 6 6 计算出得最大权值及包含的结点 图 6 7 最大连通分支 13 树的最大连通分支问题 从上述结果可知 此程序能够很好地解决树的最大连通分支问题 从最终的结果来 看此次设计还是比较成功的 上面显示的就是计算树的最大连通分支的问题 从例子可以看出 我们输入相应的数据后可以一目了然的看到最终的结果 不用看 太多的复杂关系 能给我们一种简洁明了的感觉 但从用户体验上来看 界面不够友 好 只是大体的显示了结构 从另外一方面讲显得很抽象 因此这点需要改进 14 树的最大连通分支问题 7 7 结论结论 本次课程设计用 C 进行开发 采用了动态规划算法 动态规划算法和递归算法是 在解决很多问题中比较通用的算法 此次课程设计通过动态规划算法和递归能成功地 解决树的最大连通分支问题 经过此次对次问题的解决 再次加深了我对动态规划这 种思想的理解 刚开始选题的时候觉得很简单 能够很容易的去实现 但是仔细想后 发现并不是 想象中的那样子 甚至无从下手 虽然树的最大连通分支问题是用动态规划实现的一 个很好的例子 但是真正去实现的人并不多 因此可供参考的资料很少 通过查阅资 料 知道了几种解决此问题的方法 其中比较有名的为蛮力算法和动态规划算法 但 综合其时间效率和实现过程 最后选择了动态规划 在程序设计时 使用了结构体来 存储树的各节点的信息 也使用了数组来表示数 此程序有以下几大优点 1 代码简 练易懂 2 方便用户使用 3 能成功地解决树的最大连通分支问题 当然由于时间 比较紧 再加上有些基础知识的原因 只是大体实现了功能 界面之类的不够友好 需要在下来的时间不断钻研 刻苦学习 争取能够学到更多的东西 让自己变得更好 15 树的最大连通分支问题 8 8 致谢致谢 首先需要感谢的是指导老师王晓明老师 在他的督促下才能按时完成这个课程设 计 感谢他这学期对我们的细心教导与帮助 在他的帮助下我虽不能说学到了全部的 知识 但收获却不少 让我很好的理解了算法设计与分析这门课程的重要性 给我以 后在遇到问题的时候提供了很多的思路 王老师总是很对我们提出各种问题很热情耐 心的解答 没有他的帮助与辅导我们是不可能完成学习和课程设计的 再者需要感谢 的是与我们相关的各门课的老师 没有他们 我们就不会有很好的基础做课程设计了 当然整个完成的过程中周围的同学也给了不少帮助 总之在此真的非常感激每个人 有进步是因为有帮助 16 树的最大连通分支问题 9 9 参考文献参考文献 1 宋文 算法设计与分析 重庆 重庆大学出版社 2001 2 Anany Levitin 算法设计与分析基础 北京 清华大学出版社 2006 3 王晓东 算法设计与实验题解 M 北京 电子工业出版社 2006 4 王红梅 算法设计与分析 M 北京 清华大学出版社 2006 5 郑晓明 算法设计与分析 M 北京 清华大学出版社 2005 17 树的最大连通分支问题 附录 include iostream h include using namespace std struct Cnode 用结构体来表示结点 long weight 结点的权值 int father 结点的父亲结点 int childnum 结点的儿子个数 long wMax 结点的最大连通分支权值 bool visited 该结点是否被访问过 int save 100 最大连通分支权值来源 int main int i long n u v cout 请输入树结点的个数 endl n cout endl Cnode tree new Cnode n 1 动态创建数组表示树 cout 请依次输入各结点的权值 endl for i 1 i tree i weight tree i wMax tree i weight tree i save 0 0 tree i save 1 0 tree i save 2 0 tree i save 3 0 tree i save 4 0 tree i save 5 0 cout endl cout 请输入各结点的关系 endl for i 1 i u v tree v father u tree u childnum cout endl cout endl cout 树的结构如下图所示 endl cout endl cout 4 1 endl cout endl cout endl 19 树的最大连通分支问题 cout endl cout endl cout 1 1 5 1 endl cout endl cout endl cout en