算法研究——最小生成树(Prim算法)

13 | 03 | 2015

唔,这道题目是某个学期的一个课程设计,就是解决下面这个问题。

GitHub地址:https://github.com/sjzar/MinimumSpanningTree-Prim

题目是这样的:

已知条件:
1.对象:
(1)区域:管理区域SA,多边形区域SD,长方形块SC,盒子SH。
(2)连接线:内部连接线LN,外部连接线LW。
2.区域之间的关系:
(1)管理区域SA:唯一一个。
(2)多边形区域SD:可以为矩形、平行四边形、多边形,有多个
(3)长方块SC:位置待求,一个多边形区域里面存在一个,长方形的多边区域SD可以有5个位置点,中间,上下左右角点存放长方块SC,对于多边形的多边区域SD可以考虑每个能放得下长方块的SC分站房的凸角点,可以为数量最多就给5个(相对的中间、上下左右角点),至少要有一个。
(4)盒子SH:每个多边形区域里面有多个(20个左右),位置给定。
3.连接线:
(1)内部连接线LN:盒子SH和长方块SC之间的连接线。
(2)外部连接线LW:外部连接线串起长方块SC之间以及长方块SC到管理区域SA的连接线,价格比内部连接线高。
求:
长方块的未知,限制条件:连接线的总价格最低。
总连接线是内部连接线总长加上外部连接线总长。
输出:
所有长方块SC的中心位置。

拿到题目后,让我们先做一个草图,可以适当的简化条件,将这个问题分步来完成。

首先,我们来用几何画板坐标系做一个简单的模型。将管理区域设为坐标系中心(0,0),在周围画出5个多边形SD,在多边形SD中,有5个备选SC,且在多边形SD中还有20个左右的SH我没画出来,太多了。

好的,画出这个简单的模型后,我们现在知道我们要求的就是SH-SC的连接线总价与SC-SA的连接线总价之和最小。

由于题目未给出SH-SC连接线与SC-SA连接线的权重,我们在这分别设SH-SC连接线权重为3,SC-SA连接线权重为5,这与我们日常生活中的大楼布置网线的情况有些类似,都是交换机与交换机的连接线价格贵于终端到路由器的连接线价格。

那么下一步,我们就要开始分析算法了。由于是单源最短路径问题,我想到的是Dijkstra算法,但是Dijkstra算法与我们的需求还有差别,Dijkstra算法所求的是固定点到其余各个点的最短距离,但是由于网络连线的特殊情况,我们求的是整体线路长度,所以我想对算法进行一些修改。

再就是因为SC的点还是不固定的,我们要通过遍历的方式,最终确定SC的点。

在算法设计时,我遇到了非常严重的智商障碍,总觉得不对,Dijkstra算法所求的是固定点对另外点的最短距离,与我们的需求(连接N个点,使得线段最短)不符合,无法用Dijkstra算法进行设计了。

在接下来的一段时间里,我参考了网络上有关的模拟退火算法,遗传算法,A*算法,动态规划算法,都没有多大进展。这就体现出了没系统学习过图论的弊端,没这方面的概念。

最终,我进行了尝试,将问题看成最小生成树问题(Minimum Spanning Tree)进行带入,发现可以实现求最短线段的目的。

那么顺理成章的敲定了使用Prim算法进行设计,那么存储结构使用我们已经学过的邻接矩阵。

Prim算法使用邻接矩阵的时间复杂度为o(n*n),使用二叉堆的话,时间复杂度缩短为o(E log n),使用斐波那契堆的话,时间复杂度为o(E+ n log n)。

介绍Prim算法。

说起最小生成树,就一定会提到两个算法,一个是Prim算法,一个是Kruskal算法(还有一种Boruvka算法,可以看作是Kruskal算法的改版)。至于我为什么会知道这些算法,那都是Google的嘛。

说起Prim算法,我们还是通过一个具体的例子来理解吧,定义可以自己WIKI上看一下。

首先,准备一份带权值的连通图(节点与带权值边的组合)。

图是由5个点(A、B、C、D、E)与多条边组成,最小生成树的目的就是找出连接5个点的边,权值之和最小。

第一步,在新图中画上所有点,但是不留边;

第二步,我们任选一个点,比如点E。那么原图中,观察连接E的3条边,EA30,EB50,ED50,那么最短边为EA,权值为30,那么在新图中画出。

第三步,观察连接E、A两点到B、C、D三点的5条边,EB50,ED50,AB90,AC120,AD90,那么这时最短边有两条,分别为EB和ED,我们任选一边EB,在新图中画出。

第四步,观察连接E、A、B三点到CD两点的5条边,ED50,AC120,AD90,BC40,BD70,连接最短边BC,在新图中画出。(这时,并不观察AB边,因为A到B已经连通)

第五步,观察连接E、A、B、C四点到D点的4条边,ED50,AD90,BD70,CD60,连接最短边ED,在新图中画出。

好了,通过5个步骤,画了四条边,我们已经成功画出了这幅图的最小生成树,权值之和为170。

因为起点E点是随机定的,那么我们可以试着从其他点定位再来一次,接下来,我们选择C点,再画一次最小生成树。

第一步,过C点找最短边。

第二步,过C、B找最短边。

第三步,过C、B、E找最短边。

第四步,过C、B、E、A找最短边。

完成!和上一次的最小生成树一样。

这就是Prim算法,一直走在找最短边的路上。

知道了算法,那么接下来就是代码实现咯,直接奉上,请看这一段代码(C#):


public double prim()
{
int n = this.GetNumOfVertex();
double s = 0;
bool[] flag = new bool[n];
double[] nearest = new double[n];
int[] cloest = new int[n];
double min;
int i,j,k;
for (i = 0; i < n; i++)
{
flag[i] = false;
}
flag[0] = true;
for (i = 1; i < n; i++)
{
nearest[i] = this.martix[0, i];
cloest[i] = 0;
}
int count = n;
while (count != 0)
{
count--;
min = double.MaxValue;
j = 0;
for (i = 0; i < n; ++i)
{
if (!flag[i] && nearest[i] < min)
{
min = nearest[i];
j = i;
}
}
s += this.martix[j, cloest[j]];
flag[j] = true;
for (i = 0; i < n; i++)
{
if (!flag[i] && this.martix[i,j] < nearest[i])
{
nearest[i] = martix[i, j];
cloest[i] = j;
}
}
}
return s;
}

我将prim定义成了点集合GraphAdjMatrix的一个方法,调用这个方法,就会返回最小生成树的最小权值之和,方便我们在题目中进行计算。

知道算法后,当然就是数据结构的设计啦,上文说了,我们采用的是邻接矩阵。让我们看一下定义:

具体的代码我之后上传至github,这里就只显示一个大纲好了。

简单来说,就是Node为XY平面坐标系上的点,martix保存两点之间的距离,numEdges当然就是图上所有的边数。

有了数据存储结构与算法,下面就是计算的思路了。我把计算分为这么几步:

一、计算内部(SH-SC)最短路径:遍历每个多边形(所有SH+单一SC)组合;

二、计算外部(SC-SA)最短路径:遍历(SA+每个多边形每个SC)组合

三、计算最小值

在主动给值后,以下是运行结果:

首先是生成了各种组合的邻接矩阵;

然后计算内部最短路径

一步一步计算出价格比前面价格低的组合,并得出最低价格组合。

完美,收工!

哦还没有,那么在接下来,我们可以编写随机生成SH的点,自动获取SC的点,自动创建多边形,甚至能够在执行的时候画出平面图。

那今天先这样啦~