如何连接通信站使费用少.ppt

数学实验 第12章如何连接通信站使费用最少 最小生成树 2019 12 27 数学家之擅长证明缘于对证明过程的大量研读和反复实践 同样 可以通过涉猎引人入胜 特色各异的算法 尝试设计各种问题的解决方法 培养算法设计的成熟性和机敏性 作者 2019 12 27 实验目的 掌握最小生成树的Prim算法和Kruskal算法 了解贪婪算法的基本思想 发挥联想力 把知识融会贯通 举一反三 初步领会用Matlab语言编写非数值计算问题的编程技术 通过实例学习怎样建立最小生成树模型 通过自己提出问题 动手做实验 并在文献检索 调查研究 动手和动脑等方面得到锻炼 提高创造力和解决实际问题的能力 2019 12 27 主要内容 树图 直观现象的表示工具引例 计算机网络的线路设计生成树算法及其MATLAB程序实现范例 制造系统设计的分组技术布置实验 2019 12 27 12 1树图 直观形象的表示工具 2019 12 27 12 1树图 直观形象的表示工具 一个连通图 连通图 其中任意两点之间都有路径 当一条路径的起点和终点是同一顶点时 称这条路径为圈 2019 12 27 12 1树图 直观形象的表示工具 树 没有圈的连通图 树中任意两点间有唯一路径 树的边数恰好为顶点数减1 在树中任意去掉一条边 将会不连通 树中任意两个不相邻顶点间添一边后 就恰好含一个圈 2019 12 27 12 1树图 直观形象的表示工具 2019 12 27 12 2引例 计算机网络的线路设计 城市电信局有许多业务如收费 营业 112 114等 希望在全市范围实现计算机联网服务 共享各种资源 一个主要关心的问题是用数据通讯线把一组站点联结起来 而不允许通讯线在非站点处相交 如何连接可使通讯线的花费最小 2019 12 27 12 2引例 计算机网络的线路设计 假设各站点间可以铺设通讯线路进行连接的情况如图所示 顶点为站点 边为连接两站点之间的通讯线 边的权为其费用 2019 12 27 12 2引例 计算机网络的线路设计 思考 1 左图中哪些是多余的 2 最经济的网络应具备什么特性 3 如何求出最经济的连接路线图 2019 12 27 12 2引例 计算机网络的线路设计 最经济的网络不应该有任何封闭的回路 橡筋圈上剪一刀后 仍然是一个整段 联想 2019 12 27 12 2引例 计算机网络的线路设计 生成数或支撑树 spanningtree 若G的子图T是树 且其顶点集等于G的顶点集 2019 12 27 12 2引例 计算机网络的线路设计 确定应在哪些站点之间铺设通讯线路 是否可看作是在相应的加权图中构造最小费用的生成树的问题 生成树的权 其上所有边权之和 2019 12 27 12 2引例 计算机网络的线路设计 2019 12 27 12 2引例 计算机网络的线路设计 2019 12 27 12 3生成树算法及其MATLAB程序实现 Kruskal算法算法的MATLAB程序实现背景聚焦Prim算法 2019 12 27 Kruskal算法 2019 12 27 Kruskal算法 思考 计算机如何实现上述非数值计算算法 计算机如何判断一些边是否形成圈 2019 12 27 Kruskal算法 2019 12 27 Kruskal算法 给每个子树一个不同的编号 2019 12 27 2019 12 27 Kruskal算法 2019 12 27 2019 12 27 Kruskal算法 2019 12 27 最小生成树算法的背景聚焦 1956年 美国电话电报公司 AT T 利用最小生成树计算出对几家商业客户的索价 一张大比例的美国地图铺在地板上 寻找联结所有站点的总长度最小的网络 用手工 并且跪着 操作的方式完成的问题很有限 2019 12 27 最小生成树算法的背景聚焦 2019 12 27 最小生成树算法的背景聚焦 2019 12 27 Prim算法 算法的手工操作 任选一个顶点v1 将其涂红 在一个端点为红色 另一个端点为黄色的边中 找一条权最小的边涂红 把该边的黄端点也涂成红色 重复 直到所有顶点都成红色为止 最终的红色边和顶点便是最小生成树 2019 12 27 Prim算法 2019 12 27 提示 2019 12 27 注意 2019 12 27 12 4范例 制造系统的分组技术 2019 12 27 12 4范例 制造系统的分组技术 2019 12 27 12 4范例 制造系统的分组技术 2019 12 27 12 4范例 制造系统的分组技术 思考 1 i j 0和 i j 1分别表示什么 2 表达了什么 2019 12 27 建模 2019 12 27 2019 12 27 2019