Loading...
墨滴

进击的土豆同学

2021/08/29  阅读:31  主题:默认主题

网络模型2-最小生成树算法

在上篇文章中,我介绍了网络模型中的一些相关概念,在这篇文章,我将介绍网络模型中的最小生成树算法,又叫最小支撑树算法。

最小生成树(最小支撑树)算法

0 原理

        最小生成树算法的作用是连接一个网络的所有节点,使树上边的总长度达到最小。 两个例子:

  1. 需要在几个城镇之间修路,使得任意两个城镇都有路相连,中间可以穿过一个或者多个其他城镇,这时需要一个修路方案使修路的里程最小。
  2. 某海湾上需要设计一个海面上的天然气管道网路,将各个井口连接到岸边的运输点,设计的目标是最小化修建管道的费用。

        最小生成树算法原理其实很简单:把节点分为已连接节点、未连接节点,在未连接节点中选一个节点 ,使得 到已连接节点中某个节点的弧长最小。其实主要使用的思想还是贪心思想,从第一个节点开始,每次从未选节点中选一个节点,让该节点到已选节点中的路径最短,并将另一端的节点放入已选接节点中。

1 步骤

最小生成树的具体步骤是:

<1> 令N={1, 2, ..., n},为网络中节点的集合,定义:

<2> 第0步:令 .

<3> 第1步:从 中的任意一个节点 开始,令 ,那么 .设定 .

<4> 一般的第 步:在还没连接的节点集合 中选择一个节点 ,使得 中某个节点之间的弧长最小,然后将 放入 中,并将 中删除,即:

<5> 停止条件:如果未连接节点的集合 是空集,则停止。否则,设定 ,重复<4>。

2 栗子

        某地的5个城镇需要铺设天然气管道,下图中给出了5个城镇之间可以铺设管道的情况的以及距离,先求一个设计方案,用最短的管道将5个城镇连接起来。 在这里插入图片描述

解题过程 从节点1开始(可以选择其他任意一个节点),则 .下图中将为连接的点与已连接的点分为两个区域,并用线表示所有连接集合 的侯选边,其中,红线表示的是所有候选边中最短的一条,令集合R存储每次选取的弧。开始迭代。

迭代1: 由图可见,边(1,2)是所有候选边中最短的一条,则确定节点2为下一连接节点,得到

在这里插入图片描述 迭代2: 边(2,5)是所有候选边中最短的,则确定节点3为下一连接节点,得到 .其中,黑线表示已经连接的边。 在这里插入图片描述 迭代3: 边(2,4)是所有候选边中最短的,则确定节点4为下一连接点,得到 . 在这里插入图片描述 迭代4: 边(4,6)是所有候选边中最短的,则确定节点6为下一连接点,得到 .

在这里插入图片描述 迭代5: 边(1,3)和边(4,3)是所有候选边中最短的任选其中的一条,这里我们选(1,3),则确定节点3为下一连接点,得到 .

在这里插入图片描述 最终得到的路线是:R={(1,2),(2,5),(2,4),(4,6),(1,3)},长度为:1+3+4+3+5=16.如下图

在这里插入图片描述
其实最小生成树又叫最小支撑树,不同教材或者书籍的叫法不同,比如人民邮电出版社出版的《运筹学导论》中叫“最小生成树”,而科学出版社出版的《运筹学(第三版)》中叫“最小支撑树”。而最小生成树的生成算法也有很多,其中比较常用的是破圈法和避圈法,而上面介绍的算法即避圈法

进击的土豆同学

2021/08/29  阅读:31  主题:默认主题

作者介绍

进击的土豆同学