基于“最小差值法”的网络模型耗费代价技术条

　　中图分类号 TP311.12 文献标识码：A 文章编号：1009-3044（2014）28-6650-09
　　最小生成树在生活中有广泛的实际应用[1-3]，经常用于求网络模型耗费代价的最优解。例如：实际生活中会遇到电力网路，通信线路，交通线路等求铺设总代价最小问题，这类问题通常可转化为最小生成树问题[4]。几十年来，人们对生成树相关的问题研究的很深刻，先后诞生了很多优秀的相关算法，如Kruskal算法[5]，Prim算法[6]，破圈法[7] Dijkstra算法[8]等，还有对最小生成树算法的分析[9]，有最新研究表明：生成树个数与无向连通图的无向圈定向数有关[10]。然而在实际生活中，往往还要兼顾其它因素，其中有些因素是无法控制和预测的。一棵最小生成树对应一种解决方案，一种方案不足以应对这些复杂多变的问题，因此找到所有的解决方案是必要的，与此对应的需要求出全部最小生成树。只有在全部最小生成树中，选择与实时情况匹配程度最高的最小生成树，才能更好的解决问题。基于“破圈法”每次去掉圈中最长的边的思想，在一个圈中去掉的边若不是唯一最长边，则选择去掉边的可能性有多种。在一个基本回路中，使连枝与圈中其它树枝两者比较权值大小，并作差求最小差值。根据最小差值是否为零，来判断多个最小生成树的存在情况，就此提出了一种新的求所有最小生成树的算法。
　　1 理论根据
　　1.1 最小生成树的定义
　　定义1[11]：设G=（V，E）为无向连通带权图。若T是一个包含G的所有顶点且无回路的连通子图，则T为图G的一颗生成树。图G的所有最小生成树中，各边权值之和最小的生成树称为最小生成树。
　　1.2 破圈法相关定义
　　定义2[12]：设T=（V，E）是G的一棵生成树，则T为最小生成树树的充要条件是：对于任意不属于E的边e，在把e加入T后的子图的唯一圈中，e是最长边。
　　定义3[13]：设T=（V，E）是G的一棵生成树，e是属于G，而不属于E的一条边。把e加入T所得的子图中必存在唯一的一个圈。
　　定义4[14]：将无向连通图G=（V，E）按照两句话反复进行：“任取一个圈，去掉圈上最长的边。”直到图上没有圈时为止，这时，剩下的边组成的子图就是要找的最小生成树，这种方法叫做破圈法。
　　定义5[15]：不含圈的图称为无圈图，连通图的无圈图称为树。在树的任意二个点之间添加一条边，称得到的圈为一个基本圈。
　　2 最小差值法
　　2.1最小差值法的方法
　　一个连枝加入最小生成树形成唯一的一个圈。在一个圈中令连枝的权值不断和其它树枝权值进行作差，求出最小差值，将符合“差值为零”这个条件的连枝和树枝进行换边操作：连枝换进圈中，树枝换出圈外。换边操作完成后，可形成新的最小生成树。选取不同的圈进行换边操作，直到能找到所有的最小生成树。
　　2.1.1相关定义
　　最小差值法的相关定义如下：
　　1）最小生成树的连枝和树枝。设T=（V，E）是G的一棵最小生成树，存在边ei，px∈G。边ei∈T，ei称为树枝， px ?T，px称为连枝。设P={p1，p2，…，pX，…，pn}为连枝集合。
　　2） 无向连通图中的圈（或称为基本回路）。由定义3和定义5可知： 任意连枝px∩T都会形成唯一的一个圈（或称为一个基本回路），将圈记为Cx。在圈Cx中除边px外，其它边均为树枝exi，exi∈T。px∈Cx，exi∈Cx。连枝集合P={p1，p2，…，pX，…，pn}对应着圈集合C={C1，C2，…，CX，…，Cn}。
　　3） 最小差值函数。最小差值法定义一个最小差值函数为：Min（pX）=min（w（pX）-w（exi））。Min（pX）为圈CX中连枝px的最小差值函数，w（pX）和w（exi）分别为圈CX中的连枝pX和树枝exi的权值。min（w（pX）-w（exi））表示连枝pX的权分别与圈中其它的树枝exi的权作差，最后只输出最小的差值。
　　4）置换操作。圈CX中所有符合条件w（pX）=w（exi）的边可组成一个置换对（pX，exi）。针对置换对的概念提出一种置换对的置换操作的方法，该方法将树枝exi从圈CX中去掉，将连枝pX加入圈CX中，也即用连枝pX替换掉树枝exi。
　　2.1.2最小差值法的步骤
　　最小差值法的步骤如下：
　　1）用破圈法求出一棵最小生成树T0，并找出所有的连枝。
　　2） 求出所有连枝的最小差值函数值Min（pX）。若函数值为0，则该连枝达到置换要求。
　　3） 将所有达到置换要求的连枝所在的圈，组成一个新的集合B={b1，b2，…，by，…，bm}，每一个圈为一个置换组，则一共存在m个置换组，每个置换组只能同时选取一个置换对进行置换操作。
　　4）在m个置换组中，同时选取a个置换组参与置换操作，最后形成新的最小生成树。
　　2.2最小差值函数的相关证明
　　推论1：若圈CX的最小差值函数Min（pX） ≥0，则T为最小生成树。[]
　　证明：由Min（pX） ≥0说明pX的权值在圈CX中最大，pX为CX的最长边。根据定义2， T为最小生成树。
　　推论2：若圈CX的最小差值函数Min（pX） >0，则该最小生成树是唯一的。
　　证明：由Min（pX） >0说明pX的权值在圈CX中最大，且pX为CX中唯一的最长边。根据破圈法定义4，每次去掉圈上最长的边。此时pX为CX中唯一的最长边，在圈CX中，每次一定先去掉pX，则剩下的树枝不会产生变更。由这些不变更的树枝组成的最小生成树是唯一的。
　　推论3：若圈CX的最小差值函数Min（pX）=0， 则图G的最小生成树不唯一。
　　证明：由Min（pX）=0说明pX的权值在圈CX中最大，pX不是CX中唯一的最长边。即圈CX中存在树枝exi，使w（pX）=w（exi）。根据定义4，每次去掉圈上最长的边。则在圈CX去掉最长边时，可能去掉pX，也可能去掉exi。去掉的边有多种可能，则剩下的树枝也可能会产生变更。由这些会变更的树枝组成的最小生成树不是唯一的。
　　2.3用最小差值法求全部最小生成树
　　2.3.1找出所有的置换组
　　只有当Min（pX）=min（w（pX）-w（exi））=0时，图G的最小生成树不是唯一的。在圈集合C中，找出符合条件Min（pX）=min（w（pX）-w（exi））=0的所有圈集合B={b1，b2，…，by，…，bm}，每一个圈为一个置换组，则一共存在m个置换组。
　　2.3.2找出置换组中所有的置换对以及置换对的选取原则
　　1） 选取原则1：每个 置换回路只能选取一个置换对
　　任选第y个置换组by（1≤y≤m），假设在圈by中符合条件w（pX）=w（exi）的树枝exi有q个，即{ex1， ex2，…， exk，…exq}，构建置换对（pX，exi）。一个置换对（pX，exi）表示将树枝exi从圈by中去掉，将连枝pX加入圈by中。也即用连枝pX替换树枝exi。
　　在m个置换组中同时选取a个置换组，这用概率统计的被选择的某个置换组中，存在这样的情况：在该组中，有多个树枝exi可以被连枝pX替换，即存在多组置换对。第y组的置换对集合为{（pX，ex1），…， （pX，exk），…， （pX，exq）}。
　　
　　图1 一个基本回路 Cy
　　假设存在如图1中的一个基本回路Cy。边<1，5>是连枝，边<1，2><2，3><3，4><4，5>是树枝。在这个回路里，存在4个置换对：
　　（<1，5>，<1，2>）（<1，5>，<2，3>）（<1，5>，<3，4>）（<1，5>，<4，5>）。在这个回路里，虽然有4个置换对可进行替换操作，但最终只能选取一个置换对进行替换操作。用Δ（pX）表示圈by中置换对的个数，则对于符合置换条件的任意连枝pX，都有Δ（pX）≥1（Δ（pX）为正整数）。图1基本回路 Cy中的Δ（pX）=4。
　　2） 选取原则2：不同置换组间的置换对的冲突情况
　　当2个或2个以上的置换组同时进行置换操作时，置换组间的置换对有可能产生冲突。如存在图2这样的一个无向连通图。
　　
　　图2 一个无向连通图 G1
　　图2中有两个连枝，连枝AD和连枝DC。图2有两个基本回路，第一个基本回路Cp为A→B→D→A，第二个基本回路Cq为B→C→D→B。一个基本回路为一个置换组，第一个置换组的置换对为（AD，AB）和（AD，BD），第二个置换组的置换对为（DC，BD）和（DC，BC）。现在对这两个置换组进行置换操作，每个置换组只能选取一个置换对。第一组的置换对选择（AD，BD），第二组选择（DC，BD）。
　　在第一个基本回路Cp中，连枝AD换入Cp，将树枝BD换出Cp；同时在第二个基本回路Cq中，连枝DC换入Cq，将树枝BD换出Cq，两组同时进行置换操作后，得到的不是一颗最小生成树，而是一个基本回路。原因是这两个回路同时都将树枝BD换出回路，而树枝BD是唯一的一个树枝，这就造成了置换对换边冲突的情况。当a（a≥2）个置换组同时进行置换操作时，会出现a个置换对（pk1，exi），…， （pXi，exi），…， （pka，exi），有若干个置换对含有相同的树枝，这算一种冲突情况。假设在a（a≥2）个置换组时，造成这种置换对的换边冲突的情况总共有β（ha）种，这些情况应该被舍弃。
　　2.3.3置换过程
　　找出m个所有的置换组，a为同时进行换边操作的置换组个数。符合置换要求的每个圈为一个置换组，每个置换组有Δ（pX）个置换对。每个置换组最终只能选择一个置换对。
　　a=1时，表示同时只有1个置换组参与置换。在符合置换条件的集合B={b1，b2，…，by，…，bm}中任选一个置换组，在该置换组中任选一个置换对（pX，exi），然后进行边的置换操作。
　　a=k时，表示同时有k个置换组参与置换，在符合置换条件的集合B={b1，b2，…，by，…，bm}中任选k个基本回路。将选取的k个基本回路，均进行这样的操作：在每一个置换组中任选一个置换对（pX，exi），然后进行边的置换操作，直到完成k个圈的置换操作，当然要遵守置换对的选取原则2，删掉β（ha）种冲突情况。
　a=m时，以此类推，直到输出所有的最小生成树。
　　2.3.4求所有最小生成树的个数
　　假设m个圈中，同时只有a个置换组参与置换。把a个置换组组成一个集合D={d1，d2，…，di，…，da}，D∈B∈C。每一个置换组中存在[Δpxi]个置换对。同时选取a个置换组时，则一共有[y=1zpxi∈DΔpxi-βha]种情况。其中
　　[pxi∈DΔpxi=Δpx1，d1×Δpx2，d2×...×Δpxi，di×...×Δppa，da]
　　[Δpxi，di]表示圈[di]存在[Δpxi]个置换对，[z=Cam]。
　　在前提条件中，已经给出了一棵最小生成树T0，所以全部最小生成树的总个数为：[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]（其中[z=Cam]）
　　2.4最小差值法的算法实现
　　算法具体实现步骤如下：
　　第一步：用破圈法求出一棵最小生成树T0；
　　第二步：最小差值函数Min（pX）=min（w（pX）-w（exi））判断最小生成树的唯一性；
　　Step1：令圈集合C={C1，C2，…，CX，…，Cn}，先令x=1；
　　Step2：选取一个圈Cx，Cx∈C。求圈Cx的最小差值函数值；
　　Step3：x=x+1，如果x≤m，返回Step2；
　　Step4：输出集合为：
　　Min={Min（p1），…，Min（px），…，Min（pn） }
　　Step5：若Min（pX） >0（0　　Step6：若Min（pX） =0（0　　第三步：找出所有置换组和置换对
　　Step1：找出符合Min（pX） =0这个条件的所有圈集合B={b1，b2，…，by，…，bm}，B∈C，令y=1；
　　Step2：一个圈by为一个置换组，在圈by中符合条件w（pX）=w（exi）的连枝pX和树枝exi可组成一个置换对（pX，exi）。
　　Step3：y=y+1，如果y≤m，返回Step2；
　　Step4：找到m个置换组，且每个置换组中的置换对已全部找出。
　　第四步：求所有的最小生成树
　　Step1：若集合B为空集合，则最小生成树是唯一的，输出T0后结束算法；
　　Step2：a为同时换边的置换组的个数。先令a=1；
　　Step3：在B={b1，b2，…，by，…，bm}中任选取a个置换组，并且在每个置换组中任选取一个置换对；
　　Step4：设替换后的树为Taj。符合Min（pX） =0这个条件共有m个圈，在m个圈中任选a个置换组同时进行置换操作，用概率统计中[Cam]表示。置换组的置换操作主要是指置换对的置换操作，每个置换组内有[Δpxi]个置换对，则同时选取a个置换组一共有d种情况。其中当a=1时， [d=i=1mΔpxi]；a≥2时，[d=y=1zpxi∈DΔpxi-βha]，1≤j≤d；
　　Step5：a=a+1，如果a≤n，返回Step3；
　　3 应用举例
　　3.1 实例
　　为促进经济交流发展，某市决定在ABCDEFGH这八个县城之间铺建公路，使县城网络线路之间的交通网络能够连通起来.铺设公路网络示意图如图3。无向图G的边代表铺建的公路，边上的权值表示两县之间需要铺建的路程。现该市派施工组前往实地考察，结果发现G县和D县周围环绕着群山。若要铺建通往G县和D县的公路，必须要打通山体，修建隧道。如铺建公路AG、HG、BG、GF、DE、DF、DC均需要修建隧道。现在施工组铺建公路使所有县城交通连通起来，在尽量少修建隧道的条件下，如何铺设公路，使总的铺设路程最小（外界环境条件：（1）每条线路打通隧道所花费的代价是一样的。（2）两个县城之间修建公路的主要耗费代价为铺设路程的距离代价，距离代价优先于修建隧道代价。）
　　
　　图3 无向图 G
　　3.2 用最小差值法求出所有最小生成树
　　1） 如图3为一个无向图G，图4为图G的一棵已知最小生成树T0；
　　2） 连枝为图G中的边
　　3） 连枝与树枝，组成圈A→H→G→A，连枝与树枝组成基本回路A→G→B→A，连枝与树枝组成圈B→G→F→D→C→B，连枝与树枝组成圈C→D→F→C，连枝与树枝组成圈D→F→E→D。
　　4） 求出每个连枝的最小差值函数
　　
　　
　　
　　
　　
　由于存在Min（）=0和Min（）=0，则图的最小生成树不是唯一的。有两个Min（pX） =0，表示有两个置换组。第1个置换组为（，）（，），置换组内有两个置换对，则Δ（）=2。第2个置换组为（，），则Δ（）=1。
　　5） 找出所有最小生成树。
　　a为同时进行边置换操作的置换组个数。
　　①a=1时，表示同时只有1个置换组参与置换。
　　首先对第一组进行替换，w（）=w（），用第一组中的连枝换掉树枝得到最小生成树T1。
　　
　　图5 最小生成树 T1
　　w（）=w（），用第一组中的连枝换掉另一个树枝得到最小生成树T2。
　　
　　图6 最小生成树 T2
　　再对第二组进行替换，w（）=w（），用第二组中的连枝换掉树枝得到最小生成树T3。
　　
　　图7 最小生成树 T3
　　②a=2，表示同时有2个置换组参与置换。
　　用第一组中的连枝换掉树枝，再用第二组中的连枝换掉树枝得到T4。
　　
　　图8 最小生成树 T4
　　用第一组中的连枝换掉另一个树枝，再用第二组中的连枝换掉树枝得到T5。
　　
　　图9 最小生成树 T5
　　6） 求所有最小生成树的个数。
　　所有最小生成树的个数为 [a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]（其中[z=Cam]）
　　代入具体数值进行计算：
　　[i=1mΔpxi=2+1=3]
　　[z=Cam=C22=1]
　　[y=1zpxi∈DΔpxi-βha=2×1-0=2]
　　[a=1mΔpxa+a=2my=1zpx∈DΔpx-βha+1=3+a=22y=1zpx∈DΔpx-βha+1=3+y=1zpx∈DΔpx-βha+1=3+2+1=6]
　　即图G所有最小生成树个数为6个。这与实例中找出的所有最小生成树T0 T1 T2 T3 T4 T5共有六棵最小生成树相符合。
　　3.3实例解决方案分析
　　无向连通图G的6棵最小生成树代表6种解决方案，这6种方案都能使总铺设距离最小。G县和D县周围环山，若要少修建隧道，则通往G县和D县的公路尽可能少，即令顶点G和顶点D的度尽可能小。
　　表1 最小生成树顶点G和顶点D的度
　　[最小生成树＼&顶点G的度Degree（G）＼&顶点D的度Degree（D）＼&T0＼&4＼&2＼&T1＼&3＼&2＼&T2＼&3＼&2＼&T3＼&3＼&2＼&T4＼&2＼&2＼&T5＼&2＼&2＼&]
　　由表1分析得到：在所有最小生成树中，最小生成树T4和T5中的顶点G和顶点D的度是最小的。所以T4和T5为最佳方案。
　　4 最小差值法和传统穷举算法的比较
　　4.1 时间复杂度的比较
　　4.1.1传统穷举算法求全部最小生成树
　　传统穷举算法是指：将一个带权无向图进行遍历，穷举出所有的生成树情况，然后再在该无向图中挑选出全部的边权值之和最小的生成树。根据定义1，这样找出的生成树即为全部的最小生成树。
　　时间复杂度分析：带权无向图的每一条边都有可能是某棵最小生成树的组成部分，所以每一条边都有两种状态。当一条边被选进最小生成树的组成部分时，记为状态“1”；当这条边是被舍弃的连枝时，记为状态“0”。若该带权无向图有n条边时，每一条边都有2种状态，则一共有2n种情况。因此传统穷举算法的时间复杂度为O（2n）。
　　4.1.2最小差值法求全部最小生成树
　　最小差值法：已知一棵由n条边的带权无向图G得到最小生成树T0，将p个连枝加入最小生成树T0，从而形成p个基本回路。在这p个基本回路中，用最小差值函数找出m个符合置换条件的基本回路（m　　时间复杂度分析：
　　由[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1] （其中[z=Cam]）最小生成树个数公式可知，最小差值法的主要时间耗费在置换组的挑选和置换组间的组合上面。m个基本回路同时选取a个置换组参与置换操作，即[Cam]。
　　[a=1mΔpxa=Δpx1+Δpx2+......+Δpxm=N1]，[Δpxa]是一个常数值，它表示置换组内置换对的个数，所以[N1]是一个常数值。
　　[a=2my=1zpxi∈DΔpxi-βha=C2m×px1∈DΔpx1+......+pxy2∈DΔpxy2-βha2+C3m×px1∈DΔpx1+......+pxy3∈DΔpxy3-βha3+......+Ckm×px1∈ DΔpx1+......+pxyk∈DΔpxyk-βhak+......+Cmm×px1∈DΔpx1+......+pxym∈DΔpxym-βham]
　　其中设
　　
　　[Δpxa]是一个常数值，同理[pxyk∈DΔpxyk]也是一个常数值，[βhak]是置换中的冲突情况，它也是个常数值。因此很显然[Nk]是一个常数值，所以
　　[a=2my=1zpxi∈DΔpxi-βha=C2m×N2+C3m×N3+......+Ckm×Nk+......+Cmm×Nm]
　　那么则有：
　　[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1=N1+C2m×N2+C3m×N3+......+Cam×Na+.....+Cmm×Nm+1]
　　由[C0m+C1m+C2m+......+Cam+......+Cmm=2m]可知，[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]的数量级为O（2m）。
　　所以用最小差值法求全部最小生成树的最坏时间复杂度的数量级为O（2n）。
　　两种算法的时间复杂度均在O（2n）这个数量级上，根据这个数量级可知求全部最小生成树是个NP完全问题，它没有一个多项式时间可解的算法，只能在这个问题上将算法在某些部分进行选择性的优化。
　　4.2 性能分析比较
　　4.2.1 传统穷举算法
　　传统穷举算法是指遍历无向完全图的每一条边，穷举出所有路径，没有优化效果。
　　4.2.2 最小差值法
　　用最小差值函数Min（pX）=min（w（pX）-w（exi））去检验由p个连枝加入最小生成树T0形成的p个基本回路。对于不符合最小差值函数为零的基本回路，删除该回路中的连枝。图G中删除这些连枝边，避免了一些无用的连枝边的遍历，对图G进行了约化。
　　设图有p个连枝，将p个连枝加入最小生成树T0，形成p个基本回路。在p个基本回路中，符合置换条件Min（pX） =0基本回路有m个（m　　
　　图10 分析图
　　如图10中，横坐标单位为“/个”，表示连枝个数；纵坐标单位为“/%”，表示图G中删除边的比例。
　　从分析图中可得到结论：
　　当p为一个定值时，m的值越小则y的值越大；或是当m的值一定时，p的值越大则y的值越大。y的值越大说明图G中删除边的比例越大，图G的约化程度越大，图G中不需要遍历的边的个数越多。
　　当m<　　最小差值法的实际应用意义在于首先用最小差值法找出解决问题的所有方案；其次，针对实际约束条件，在已提出的方案中进行方案的二次选择。在找到最终合适方案的过程中，这种二次选择也实现了一种问题解决的再次优化。
　　5 结论
　　基于“破圈法”去掉圈中最长边的思想，提出一种新的求所有最小生成树的算法——最小差值法。在一个圈中令连枝的权值不断和其它树枝权值进行作差，以最小差值是否等于零为标准，删去不符合置换条件的圈的连枝，完成图的初始约化。当图的规模非常大的时，对图的约化操作能使边的遍历次数减少，算法效率提高。
　　将符合“最小差值为零”条件的圈中的连枝和树枝进行置换操作：连枝换进圈中，树枝换出圈外。选取不同的圈进行换边操作，最终能找到所有的最小生成树，并能计算出所有的最小生成树的个数。
　　参考文献：
　　[1] 王化宇. 最小生成树算法及其应用[J]. 内蒙古科技与经济， 2011（6）：72-73.
　　[2] 段东东. 最小生成树算法及其应用 [J]. 西安航空技术高等专科学校学报， 2010（1）：55-57.
　　[3] 袁卫东. 最小生成树的算法及其应用 [J]. 科学技术与工程， 2009，9（15）：4409-4412.
　　[4] Salama H F， Reeves D S， Viniotis Y. The delay-constrained minimum spanning tree problem[C]//Computers and Communications， 1997. Proceedings.， Second IEEE Symposium on. IEEE， 1997： 699-703.
　　[5] Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical society， 1956， 7（1）： 48-50.
　　. Bell system technical journal， 1957， 36（6）： 1389-1401.
　　[7] 管梅谷. 求最小树的破圈法[J]. 数学的实践与认识， 1975，5（4）：38-41.
　　. Numerische mathematik， 1959，1（1）：269-271.
　　. Canadian Journal of mathematics， 1965，17（3）：449-467.
　　[10] Thomassen C. Spanning trees and orientations of graphs[J]. Journal of Combinatorics， 2010，1（2）：101-111.
　　[11] 王海英. 图论算法及其MATLAB实现[M] 北京：北京航空大学出版社，2010.
　　. Princeton university press， 2010.
　　[13] C.贝尔热.图的理论及其应用[M].李修睦，译.上海：上海科学技术出版社，1963.
　　[14] 董跃华， 李云浩， 姜在东. 用破圈法实现普里姆算法[J]. 江西理工大学学报ISTIC， 2008，29（4）：20-22.