一种基于二进制编码的最小生成树算法

1、一种基于二进制编码的最小生成树算法论文导读:：这就需要找到带权的最小生成树。在求带权无向连通图的最小生成树时。本文试图用二进制编码的方式来解决这个问题。那么称该二进制字符串是对应该生成树的染色体。最经典的算法就是Prim算法和Kruskal算法【3】。论文关键词：最小生成树，连通图，二进制编码，染色体，算法0 引言许多应用问题都是一个求带权无向连通图【1】的最小生成树【2】问题。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。在求带权无向

2、连通图的最小生成树时，最经典的算法就是Prim算法和Kruskal算法【3】。这两个算法都是通过求解局部最优到达求解全局最优，即我们通常所说的贪心算法。一般来讲，局部最优解往往不是整体最优解，而是近似最优解。由于最小生成树的特殊性，用贪心算法【4】能够准确地计算出它的全局最优解。然而，无论Prim算法还是Kruskal算法，都只能找到带权无向连通图的一个最小生成树。如果一个带权无向连通图有多个最小生成树，要想找出所有的最小生成树连通图，用Prim算法或Kruskal算法都是无能为力的。至于所谓用遗传算法求最小生成树，由于该算法是一种近似算法，可能连一个最小生成树都找不到，最好的情形也是只能找到

3、一个最小生成树。因此，能否找到一种在全局范围内寻找所有最小生成树的算法？到目前为止，还没有相关文献作这方面的工作。本文试图用二进制编码的方式来解决这个问题。1 理论根底定义1 我们用深度优先法或广度优先法遍历一个无向图，如果所有顶点都能被访问到，那么称该图是连通图；否那么，称该图是不连通图论文参考文献格式。定义2 设一个带权无向连通图【5】有n个顶点和m条边，如果删除m-n+1条边后，该剩余图仍然是连通的，那么称该剩余图为生成树。定义3 在一个带权无向连通图的所有生成树中，所有边的权值之和最小的生成树是最小生成树。性质1 如果一个带权无向连通图有n个顶点，那么它的生成树只有n-1条边。证明：如

4、果它有n条边，那么它一定有回路，因此它就不是生成树。另一方面，如果它只有n-2条边，那么这n-2条边最多只能连接n-1个顶点，还有一个顶点没有被连接。定义4 对于一个无向图，如果用字符1表示图中的两个顶点之间存在边，用字符0表示两个顶点间不存在边，那么我们称这种用二进制字符串表示的图为对图的二进制编码。定义5 设一个无向连通图有m条边，如果我们用长度为m的二进制字符串表示它的生成树，那么称该二进制字符串是对应该生成树的染色体连通图，其中染色体的每一位对应无向图的一条边。性质2 设G是一个含有n个顶点m条边的无向连通图，如果用染色体表示该无向图的生成树，那么染色体是长度为m的含有n-m+1个1字

5、符和2m-n-1个0字符的字符串。定义6 如果一个染色体对应带权无向连通图的最小生成树，那么称该染色体是最优染色体。性质2 如果找打一个带权无向连通图的最优染色体，那么它所对应的最小生成树确定。2 算法设计2.1 带权无向连通图的矩阵表示法设G是一个含有n个顶点m条边的带权无向连通图，那么可以用一个阶矩阵表示。其中，。2.2 连通的判断算法的中心思想就是从带权无向连通图的生成树中找出最小生成树。虽然生成树是从图的条边中去掉条边形成的，但仅仅删除边还是不够的，还必须保证删除的剩余图还是连通的，否那么就不是生成树。可以通过使用深度优先法或广度优先法对剩余图进行遍历，如果图的所有结点经过一次遍历都可

6、以搜索到，那么该剩余图就是生成树。否那么，剩余图一定不是生成树。因此，通过深度优先法或广度优先法对剩余图进行遍历，可以将带权无向连通图的所有生成树找出来。然后，从生成树集中找出最小生成树就比拟自然了。2.3 对生成树进行二进制编码由于带权无向连通图有条边，因此需要用长度为的二进制字符串即染色体表示该图。当染色体的每一位都是字符1时，该染色体就是表示该带权无向连通图。一方面，带权无向连通图的生成树只有条边，故它所对应的染色体只有个字符1和个字符0；另一方面，由个字符1和个字符0组成的染色体不一定对应一棵生成树，故需要判断该染色体所对应的剩余图是否连通。因此，判断一根染色体是否对应一棵生成树，执行

7、步骤：1从;该染色体由左边的个0字符和右边的个1字符组成到;该染色体由左边的个1字符和右边的个0字符组成的染色体中筛选出只含有个字符1的染色体；2从1筛选出的染色体中进一步筛选出生成树连通的染色体。3 算法描述设G是一个含有n个顶点m条边的带权无向连通图连通图，那么生成图G的算法过程如下：Step1：初始化，最优值shortpath=-1，长度为m的二进制字符串str=;m个0字符组成，以及建立染色体每一位与带权无向连通图的某一边的对应关系;Step2：将i转化为长度为m的二进制字符串，具体转换过程为：1执行语句itoa(i,str1,2)，可以将整数i转换为二进制字符串；2求出二进制字符串s

8、tr1的长度，只需执行l=strlen(str1)；3执行strcpy(str+m-l,str1)，就可以得到i所对应的染色体str。Step3：统计染色体str中所含字符1的个数c。如果，那么转向step6；Step4：判断染色体str所对应的图是否连通。如果不连通，那么转向step6；Step5：求str所对应的生成树的边权之和curpath论文参考文献格式。如果curpathStep6：执行i=i+1；Step7：如果，那么返回Step2；Step8：从保存的生成树染色体中将边权之和等于shortpath的染色体最优染色体选择出来；Step9：输出所有最优染色体所对应的最优生成树。4 算

9、法测试及比拟4.1算法实例例 如图1所示的带权无向连通图G，求G的最小生成树。图1 带权无向连通图G解：由于带权无向连通图G的定点数和边数，因此程序执行算法的过程如下：Step1：，shortpath=-1，str=00000000;，染色体的8个二进制位从左到右依次与边、相对应；Step2：执行语句：itoa(i,str1,2)；l=strlen(str1)；strcpy(str+m-l,str1)；得到所对应的染色体str；Step3：如果str所含字符1的个数不等于4，那么转向step6；Step4：如果染色体str所对应的图不连通，那么转向step6；Step5：求str所对应的生成树

10、的4条边的权值之和curpath。如果curpathStep6：执行i=i+1；Step7：如果，那么返回Step2；Step8：从保存的生成树染色体中将4条边权值之和等于shortpath=14的染色体01101001;和11100001;选择出来；Step9：染色体01101001;和11100001;所对应的最优生成树分别如图2连通图，图3所示。图2 01101001所对应的最小生成树 图3 11100001所对应的最小生成树4.2 算法比拟如果分别用Prim算法和Kruskal算法求解图1的最小生成树，都只能得到如图2所示的一棵最小生成树。因此，当一个带权无向连通图的最小生成树不止一个

11、时，Prim算法和Kruskal算法都无法求出所有的最小生成树，它们永远只能求出其中的一个最优解。本算法先利用染色体表示各种不同的生成树，然后从所有这些生成树中找出所有最小生成树。因此，本算法通过巧妙地利用二进制编码来到达全局寻优的目的。Prim算法和Kruskal算法本质上都是通过局部最优到达全局最优，因此寻优的速度快。本算法由于是全局寻优，故寻优的速度比拟慢，但它可以找到所有的最优解。5 结束语针对Prim算法和Kruskal算法都不能寻找一个带权无向图所有最小生成树的缺点，本文提出了一种从全局范围内寻找一个带权无向图所有最小生成树的二进制编码算法。该算法充分利用深度优先遍历算法和最小生成树的性质，将不满足生成树的染色体淘汰，从而极大地提高了全局范围内的寻优速度。实验说