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

数学实验第12章 如何连接通信站使费用最少 ---最小生成树 数学家之擅长证明缘于对证明过程的大量研读和反复实践。同样，可以通过涉猎引人入胜、特色各异的算法，尝试设计各种问题的解决方法，培养算法设计的成熟性和机敏性。 ---作者实验目的掌握最小生成树的Prim算法和Kruskal算法，了解贪婪算法的基本思想，发挥联想力，把知识融会贯通，举一反三。初步领会用Matlab语言编写非数值计算问题的编程技术；通过实例学习怎样建立最小生成树模型；通过自己提出问题，动手做实验，并在文献检索、调查研究、动手和动脑等方面得到锻炼，提高创造力和解决实际问题的能力。主要内容树图—直观现象的表示工具引例：计算机网络的线路设计生成树算法及其MATLAB程序实现范例：制造系统设计的分组技术布置实验12.1 树图—直观形象的表示工具12.1 树图—直观形象的表示工具连通图：其中任意两点之间都有路径，当一条路径的起点和终点是同一顶点时，称这条路径为圈一个连通图12.1 树图—直观形象的表示工具 树：没有圈的连通图 --树中任意两点间有唯一路径。 --树的边数恰好为顶点数减1。 --在树中任意去掉一条边，将 会不连通。 --树中任意两个不相邻顶点间 添一边后，就恰好含一个圈。12.1 树图—直观形象的表示工具12.2 引例—计算机网络的线路设计 城市电信局有许多业 务如收费，营业，112， 114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？12.2 引例—计算机网络的线路设计假设各站点间可以铺设通讯线路进行连接的情况如图所示，顶点为站点，边为连接两站点之间的通讯线，边的权为其费用。12.2 引例—计算机网络的线路设计思考：1）左图中哪些是多余的？2）最经济的网络应具备什么特性？3）如何求出最经济的连接路线图？12.2 引例—计算机网络的线路设计最经济的网络不应该有任何封闭的回路。橡筋圈上剪一刀后，仍然是一个整段。联想12.2 引例—计算机网络的线路设计生成数或支撑树（spanning tree）：若G的子图T是树，且其顶点集等于G的顶点集。12.2 引例—计算机网络的线路设计 确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？ 生成树的权：其上所有边权之和。12.2 引例—计算机网络的线路设计12.2 引例—计算机网络的线路设计12.3 生成树算法及其MATLAB程序实现Kruskal算法算法的MATLAB程序实现背景聚焦Prim算法Kruskal算法Kruskal算法思考：计算机如何实现上述非数值计算算法？计算机如何判断一些边是否形成圈？Kruskal算法给每个子树一个不同的编号Kruskal算法Kruskal算法Kruskal算法最小生成树算法的背景聚焦 1956年，美国电话电报公司（ATT）利用最小生成树计算出对几家商业客户的索价。 一张大比例的美国地图铺在地板上，寻找联结所有站点的总长度最小的网络。 用手工（并且跪着）操作的方式完成的问题很有限。最小生成树算法的背景聚焦最小生成树算法的背景聚焦Prim算法算法的手工操作：任选一个顶点v1，将其涂红；在一个端点为红色，另一个端点为黄色的边中，找一条权最小的边涂红，把该边的黄端点也涂成红色；重复②直到所有顶点都成红色为止，最终的红色边和顶点便是最小生成树。Prim算法提示注意12.4 范例：制造系统的分组技术12.4 范例：制造系统的分组技术12.4 范例：制造系统的分组技术12.4 范例：制造系统的分组技术思考：1）ω(i,j)=0和ω(i,j)=1分别表示什么？ 2）ω表达了什么？建模布置实验布置实验实验内容实验内容9、有时候读书是一种巧妙地避开思考的方法。10、阅读一切好书如同和过去最杰出的人谈话。11、越是没有本领的就越加自命不凡。12、越是无能的人，越喜欢挑剔别人的错儿。13、知人者智，自知者明。胜人者有力，自胜者强。14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。15、最具挑战性的挑战莫过于提升自我。。16、业余生活要有意义，不要越轨。17、一个人即使已登上顶峰，也仍要自强不息。 谢谢观赏 You made my day!我们，还在路上……