约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.     

求解度约束最小生成树的一种启发式方法

针对网络设计和优化中度约束最小生成树问题,提出了一种基于贪心思想的启发式算法求解度约束最小生成树.在最小生成树的基础上,将超过度约束的顶点降低度数使之满足度约束条件.经大量数据测试并与其他算法进行比较,表明了该算法的有效性和通用性.     

基于Prim算法的度约束最小生成树问题研究

针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.     

求解最大度约束下最小生成树的新算法

针对网络优化中度约束最小生成树问题的特征,融合破圈法的基本思想,提出了一种求解网络G关于指定节点的最大度约束下最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过去掉圈中权最大的边,最终构造出网络G关于指定节点的最大度约束下的最小生成树。算法证明和算例都表明了该算法的有效性。     

基于遗传算法的一体化通风网络优化算法

概括混合型一体化通风网络优化的模型,分析目前混合型通风网络优化的4种求解方法优缺点。针对混合型通风网络优化的要求,提出混合型通风网络风量分配和风流调控一体化的优化思路。在通风网络理论和图论的基础上,引入遗传算法随机产生2个动态网络的邻接矩阵和余树弦风量值,使用附有条件的最小支撑树算法产生2个最小支撑树,进而求得相应的回路矩阵。通过余树弦风量值和回路矩阵等分别计算通风网络风量分配值和风阻调节值,基于通风总功率和约束条件构建广义最小化目标函数,依此对分风和调风方案进行评价,使用遗传算法中进化算子对分风和调风方案实施进化操作,最终得到满意解。研究结果表明：该算法是严格数学意义上全局优化算法,解决调风地点约束的通风网络优化问题,利用网络结点流量平衡的等式约束条件,减少最优化模型中变量数目,提高算法效率。     

一类度约束最小生成树问题的Dijkstra算法

度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。     

基于遗传算法的通风网络两步法风流调节优化算法

概括混合型通风网络优化模型,归纳混合型通风网络风量最优分配和风流最优调控两步法优化基本框架。首先,在满足矿井通风风量需求的基础上,实现风量分配优化。然后,结合矿井通风网络实际调风需求,引入遗传算法随机产生动态网络的邻接矩阵,使用附有条件的最小支撑树算法求解部分余树弦(调风地点)约束下的最小支撑树和独立回路矩阵,根据回路矩阵计算通风网络余树弦风阻调节值,在通风总功率和约束条件基础上构建广义最小化目标函数,依此对调节方案进行评价,使用遗传算法中的进化算子对调节方案编码实施进化操作,最后通过迭代得到满意解。研究结果表明:两步法思想简化混合型通风网络优化问题,解决调风地点约束的通风网络优化问题,执行效率高,能够解决较大规模的通风网络优化问题。     

特定材料构建支撑树问题的近似算法研究

结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w, c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。     

基于遗传算法度约束的最小生成树问题的研究

探讨了如何将遗传算法应用于度约束的最小生成树问题，并给出了相应的算法．实验结果表明，这种用遗传算法解决度约束的最小生成树问题是有效的．     

基于直方图偏差约束的快速模糊C均值图像分割法

为了解决传统模糊C均值（FCM）聚类分割算法计算耗时的问题，提出了在直方图偏差约束条件下的快速FCM图像分割算法．通过对原始图像重新采样以减小FCM算法数据处理的数量，利用平滑后归一化直方图的距离偏差作为约束条件来计算合适的采样率，以控制重新采样产生的图像失真，得到满足正确分割所需要的阈值，并在采样率计算中采用黄金分割法搜索满足约束条件的采样率．实验结果表明，在保持传统FCM聚类算法分割效果的前提下，所提算法的分割时间分别仅为传统的FCM、二维熵、Otsu等算法的3．0%～11.2%、9.2%～30．2%和15.0%～52．0%.     

多目标MIN-MAX度最小树问题及其求解

在多目标最小生成树问题和MIN-MAX度最小树问题的基础上,探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质,在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同,当网络图不存在Hamilton路时,引入改进的蚁群优化算法,将转移概率由基本的指数形式改进为线性形式,在不影响求解质量的前提下,提高计算效率。针对以上策略,设计了相应的求解方案,并在计算机上用Delphi编程实现。大量数值算例验证表明,算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。     

无线传感器网络LEACH簇树路由协议研究

基于LEACH的簇树路由协议是目前无线传感器网络研究的热点之一,由于传统的构造最小生成树的算法不能适应网络中节点密度的变化,制约其更广泛的应用。在对LEACH簇树路由和传统的连通网络中构造最小生成树算法的分析基础上,结合动态优化的思想,提出了一种新的基于Prim算法的构造最小生成树算法,并将其应用到簇树路由中,使得网络寿命延长,同时增强了对网络节点密度的适应性。仿真结果说明了该算法的可行性和有效性。     

基于DPCNN的无向赋权图的最小生成树的求解

 利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.     

遗传算法在网络最短路径问题上的应用

将网络最短路径问题抽象为求最小生成树问题,分析了最小生成树在解决实际问题时的局限性,引入了节点的度的概念;针对一般遗传算法在求解某些工程问题时存在的一些不足,提出了用量化约束条件来改进适应值函数、节点与度约束相结合编码的二进制编码方式、基于节点域的交叉和变异运算的策略.通过对公路交通网络的仿真表明,采用一般遗传算法与普通遗传算法分别求解,数值计算结果证明了改进后的遗传算法的可行性.     

用遗传算法求最小生成树

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

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

多目标优化问题的研究

针对传统方法求解多目标优化问题的局限性,应用一种新的算法求解。遗传算法从问题解的串集开始搜索,覆盖面大,可以同时处理群体中的多个个体,利于全局择优,减少陷入局部最优的风险,而最小生成树具有过程简单清晰、适用性广泛的特点,结合两者的优点,构造了基于生成树的遗传算法。首先通过加权目标规划法求出最优解,然后通过遗传算法和基于生成树的遗传算法求解,结果表明,对于小规模的多目标优化问题,两种算法都可以求出最优解,在求解时间方面,基于生成树的遗传算法比遗传算法更优越。     

基于最小生成树的多层次k-Means聚类算法及其在数据挖掘中的应用

针对传统聚类算法存在挖掘效率慢、 准确率低等问题, 提出一种基于最小生成树的多层次k-means聚类算法, 并应用于数据挖掘中. 先分析聚类样本的数据类型, 根据分析结果设计聚类准则函数; 再通过最小生成树对样本数据进行划分, 并选取初始聚类中心, 将样本的数据空间划分为矩形单元, 在矩形单元中对样本对象数据进行计算、 降序和选取, 得到有效的初始聚类中心, 减少数据挖掘时间. 实验结果表明, 与传统算法相比, 该算法可快速、 准确地挖掘数据, 且挖掘效率提升约50%.     

基于细化和最小生成树的多边形主骨架线提取

现有的不规则多边形主骨架线提取方法存在设计复杂、执行效率低等缺点,对此提出一种基于细化和最小生成树的多边形主骨架线提取方法 .首先,确定多边形的最小包围盒,并在其中生成均匀分布、数值分别为0或1的点,运用细化算法提取多边形骨架;再利用Prim算法生成最小生成树;最后,计算最小生成树上的两个叶子节点间的路径长度,将长度最长的路径定义为主骨架线.实验结果表明：本方法提取出的主骨架线效果较好,具有一定的实用性.