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

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