| Step6：执行i=i+1；
Step7：如果 ，则返回Step2；
Step8：从保存的生成树染色体中将边权之和等于shortpath的染色体（最优染色体）选择出来；
Step9：输出所有最优染色体所对应的最优生成树。
4 算法测试及比较
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所对应的生成树的4条边的权值之和curpath。如果curpath
Step6：执行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所示的一棵最小生成树。因此，当一个带权无向连通图的最小生成树不止一个时，Prim算法和Kruskal算法都无法求出所有的最小生成树，它们永远只能求出其中的一个最优解。
本算法先利用染色体表示各种不同的生成树，然后从所有这些生成树中找出所有最小生成树。因此，本算法通过巧妙地利用二进制编码来达到全局寻优的目的。
Prim算法和Kruskal算法本质上都是通过局部最优达到全局最优，因此寻优的速度快。本算法由于是全局寻优，故寻优的速度比较慢，但它可以找到所有的最优解。
5 结束语
针对Prim算法和Kruskal算法都不能寻找一个带权无向图所有最小生成树的缺点，本文提出了一种从全局范围内寻找一个带权无向图所有最小生成树的二进制编码算法。该算法充分利用深度优先遍历算法和最小生成树的性质，将不满足生成树的染色体淘汰，从而极大地提高了全局范围内的寻优速度。实验表明该算法能够实现全局寻优和找出全部最小生成树，并使寻优效率在整体上得到改善。
参考文献
[1]Fred Bucldey，MaryLewinter．图论简明教程[M]．北京：清华大学出版社，2005．
[2]Cormen TH，Lleiserxon CE，RivestRL．Introducton to Algorithms[M]．USA：MIT Press，2001．
[3]高一凡．<数据结构》算法实现及解析[M]．西安：西安电子科技大学出版社，2002．
[4]候识忠．数据结构算法程序集[M]．北京：中国水利水
[5]刘瓒武．应用图论[M]．长沙：国防科技大学出版社，2006．
2/2 首页 上一页 1 2 |
