用基本割集组的余组生成含指定边的生成树

利用连通图基本割集组的余组,给出了求连通图含指定边生成树的一种简单、快捷的方法.     

最小生成树的应用及拓展探讨

最小生成树的求解在很多关于最小成本的问题中具有多种应用,本文探讨了求最小生成树的拓展问题的算法,并给出了这种算法的应用.     

量子遗传算法求解度约束最小生成树

度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值.针对度约束最小生成树问题,采用量子遗传算法来求解该问题.并对基本的量子遗传算法进行改进.针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较.取得了良好的效果.     

无向图的第二大生成树的算法

在一个有生成树的赋权图 G=(V,E)中,其最大生成树的算法是早已解决了的.但它是否还有第二大生成树呢?如果有,又如何去求它呢?关于这个问题,本文给出了解答.在一个无向图 G=(V,E)中,来规定各条边的方向.对于图 G 的每一条边 e∈E,规定一个权α(e)∈R~+(R~+是非负实数集合),树的权定义为树的各条边的权之和,对于图 G 的一棵生成树,如果它具有最大可能权,称这棵树为 G 的最大生成树.如果图 G 的生成树具有     

用遗传算法求最小生成树

以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树.     

基于最小生成树的通信网络设计优化

针对通信网络的设计,利用最小生成树的KRUSCAL算法与改进的哈密顿回路等方法,建立了最小生成树模型、结点故障的环形改进模型、链条破坏的环形改进模型,运用MATLAB编程计算,得出兼顾可靠性与成本费用的合理优化铺设方案,通过比较不同可靠程度下边际新增费用大小,给出了边际新增费用最小的优化网络结构,并将规划后的网络结构拓扑图直观呈现.     

K3,4的生成子图的计数和构造

给出了生成子图的定义;证明了生成子图的计数定理和构造定理;提出了生成树的计数方法和构造方法;介绍了完全二分图K3,4的生成子图的计数和构造.     

分形曲线曲面的分形插值法及其与随机生成法比较

给出了矩形域上的分形插值数学模型,分形插值曲线曲面的MATLAB程序.应用实际的数据进行了分形插值曲线曲面的研究,并与随机生成法做了比较.这对直观显示复杂物体的几何形态,研究具有分形特征的地形地貌,断层表面和材料裂缝表面等,具有重要的理论意义和实用价值.     

基于DNA计算的遗传算法解决最小生成树问题

给出了最小生成树问题（MST）的一个基于混合DNA计算的遗传算法模型。在该模型中,为了对最小生成树的解进行编码和解码,通过引入DNA计算,提出了一种最小生成树问题的改进遗传算法编码方案,该方案吸收了DNA计算和遗传算法的优点,具有固定的长度。为了搜索需要的最佳编码,引入遗传算法搜索技术,并给出了自适应的交叉算子和变异算子。最后,根据最小生成树问题的特点,通过实例仿真验证了所提出的基于DNA计算的遗传算法的有效性     

随机P-集合及其随机特征

在P-集合概念的基础上,根据元素迁移的随机性,提出随机P-集合的概念,给出了P-集合的随机生成,P-集合的强随机生成.并根据元素迁移的概率,讨论了随机P-集合的随机特征,给出了随机P-集合的存在背景及在风险投资决策估计中的应用.     

逆向需求模糊的多车辆集散货物路线问题

研究了一类新的车辆路线问题（VRP）——整合逆向物流的多车辆路线问题（MVRPRL）．该问题的特点是客户可以同时取货和发货,而且客户发货量是在路线安排前是不确定的．首先用三角模糊数表示客户发货量,建立了基于模糊置信度理论的多目标模型;然后设计了基于模拟的改进禁忌算法来求解该模型：用模拟的方法计算路线失败值,在路线搜索中采用路线内部改善和路线间改善两类邻域操作,而且采用了重起策略．计算结果表明该方法优于传统的扫描算法,整合逆向物流的运输费用比正逆向分别运输之和减少了43％．     

关于Kruskal算法的一个简便实现

根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。     

赋权图的最小环路遍历路径分析与研究

文章联系实际问题,结合旅行商问题和中国邮递员问题,提出赋权连通图中最小环路遍历路径以及求解该路径的方案.该方案参考最小生成树的普里姆算法,依据狄杰斯特拉算法,通过往返最短路径逐次比较,在赋权连通图中实现寻找最小环路遍历路径.     

货郎担问题的若干解法

货郎担问题是组合优化中的著名问题,至今它还没有一个有效算法.主要针对多年来人们对它的研究而得到的一些较好的最优解或优秀的近似解,结合实例,说明这些算法的运行过程.并提出两个新的算法-贪心算法和修改最小生成树法.     

基于不确定数据决策树分类算法的软件外包评价模型

经典决策树算法不能处理树构建和分类过程中的不确定数据,针对这一局限,提出基于概率分布的方法,把决策树分类技术扩展到含有不确定数据的环境中。然后,针对软件外包评价中普遍存在着不确定数据,应用决策树分类方法,对软件外包公司进行客观评价。实验表明,本文提出的基于不确定数据的决策树分类算法能够实现对软件外包评价的定量研究。     

破圈法构造最小生成树算法探讨

求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。     

求解度约束最小生成树问题的自适应遗传算法

在遗传算法中一个关键问题是必须采取措施保持种群多样性，防止算法出现早熟收敛。本文提出了一种基于父个体相似度的自适应遗传算法，使用新的自适应遗传操作策略以保持种群多样性。将新算法用于求解图的度约束最小生成树问题，实验结果表明本方法到比不使用父个体相似度信息的普通遗传算法权值更低的度约束最小生成树。     

求解DCMST问题的模糊离散粒子群优化算法

提出了一种求解度约束最小生成树问题(DCMST)的模糊离散粒子群优化算法(PSO),粒子编码采用Prüfer数编码机制,并引入模糊矩阵产生Prüfer数,迭代过程中加入归一化运算对位置矩阵进行修正,利用最大数法进行解模糊化。通过仿真实验验证了算法的有效性。     

遗传算法在网络动态选路中的应用

根据安全传输的要求,提出了一种运用遗传算法来实现网络中动态寻路的方法.且结合运用遗传算法求解图的最小生成树的例子,对一个模拟网络拓扑结构的有权无向图进行了编码,为求解过程建立了相应的模型,并对该模型进行了分析.