求解大规模结构树问题的改进算法.docxVIP

求解大规模结构树问题的改进算法 这是一个困难的问题，通常用于通信网络、能源网络、计算机网络和大型网络。长期以来，它引起了国内外许多科学家的关注。这是第一个扩展点限制的问题。该算法可以接受小型dhst问题的最佳解。cacerta等人提出了一种解决方案，该算法可以扩展到3dmst问题的最佳解。在这项算法的支持下，anderson等人提出了一种基于二元分解信息的lagrangian算法。在模型分类和切割算法的基础上，belk和其他人提出了基于二元分解信息的lagrangian算法。基于标准分支和切割算法，belk和其他人提出了基于二元分解信息的lagrangian算法。基于标准分支和切割算法，belk和其他人提出了优先分支和交叉算法的问题。近年来，许多科学家研究并应用了以遗传算法和免疫算法为代表的未来计算方法。其中一些科学家利用遗传算法和免疫算法进行了验证，并在3dmst问题的解决中提出了解决方案。在本文中，需要使用pruzer计数来表示生成树的编程方法。由薄边效应等人设计的算法动态表结构的方法是最好的分解，其中六个边滩边的重量信息由小边距的数据获得。对于在最优解中生成的树的构建方法，拓格伦等人使用了最小边界值的统计方法。对于在最优解中生成的字段信息，估计节点数为20.1的dcmst问题的权重及其最优解的概率公式，并将其用作执行突变操作的依据（1.1）。各种各样的算法都可以通过子图边缘的节点来构建。 不同的DCMST问题可分为两大类,即non-Euclidean DCMST和Euclidean DCMST完全图问题.对这两大类约束最小生成树问题求解的复杂性,不同的文献有不同的看法.多数文献作者认为,按均匀随机方式产生的non-Euclidean问题要比Euclidean问题的求解更为复杂;与之相反,文献的作者倾向Euclidean问题的求解更具有挑战性.通过大量的实验测试及分析,我们认为,以均匀随机方法生成non-Euclidean图例的DCMST问题具有更大的变化性和多样性,使得这类问题解的结构及求解的难易性具有更大的变化性.一方面,这类问题的Prim解对应的度值通常大于5,且在度为3时问题的最好解与Prim算法解的比值随不同的问题或分布范围有所不同.一些文献证实,Euclidean图例的DCMST问题对应Prim解的度最大为5,且在度值为3或4时最好解与Prim算法解的比值在一定的范围内.当度为3时,该指标的界限值在不同的文献分别为5/3,1.5和1.402.文献作者猜测性地认为,该指标界限值能进一步减小到1.103.另一方面,对均匀随机方式产生分布在某一区间的non-Euclidean问题,随着结点数增加,其解的复杂度逐渐降低.主要表现在:当结点数增大到某一值后,该类问题不再是一个难求的NP-hard问题,较多情形下能以几乎1的概率构造出一棵度值为3的最小生成树,使其与Prim算法得到的无约束生成树(对应的度值一般大于10)具有相同目标值. 通过反复的编程测试及对存在问题的分析,我们发展了基于度排列的编码方法,通过利用度维关系,不需经过完全解码就能求出及利用待考察结点的关联结点及构成边的权重信息;结合花草果树的人工种植和培育技术,提出一种带有嫁接及剪接算子的遗传算法(a genetic algorithm with grafting and pruning operators,简称GPOGA).通过将该算法用于对DCMST问题进行求解,与现有文献提供的实验数据的对比说明,本文算法在得到最好解精度以及算法的诸多性能指标均有很大提高. 1 dcmst的数学模型 假设G=(V,E)为网图,其中:V={v1,v2,…,vn}是结点的有限集合,n=|V|为结点总数;E={e1,e2,…,em}是G中边的集合,m为边的总数.设S={v1′,…,vi′,…,vt′|vi′∈V}?V且|S|≥1;设T为图G的所有满足度约束的生成树的集合因此,对DCMST问题求解就是寻找G的一棵生成树,这里用一个向量x表示,x∈T,使其满足给定的度约束并使对应边权重wij(一般指边长或费用,本文以下均指边长)之和为最小值.DCMST的数学模型可描述如下: 上述数学模型由DCMST问题的优化目标函数及约束构成,其中:第1个约束为生成树包含不同结点的n-1条边;第2个约束为每个结点应满足的度约束条件,dc为给定的度约束值;第3个约束表示生成树无环路;第4个约束为所有结点的度值和;第5个约束当xij=1时,由结点vi,vj构成的边是生成树的一条边. 2 pgoga算法系统 2.1 调整算子的作用 在对与排序或路径长度有关的组合优化问题的求解中,广泛使用一项被称为邻域有哪些信誉好的足球投注网站(local search)的策略.其基本思想是,在算子的有哪些信誉好的足球投注网站过程中,应充分利用相邻结点的路径长