基于图的任意域内点集的Delaunay三角剖分算法

本文提出了一种基于图的二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分算法．该算法首先求出任意域内点集的约束最小生成树，然后逐次加入一边构造三角形网格，最后通过局部优化变换，得到二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分．

度限制最小树的蚂蚁算法

Based on the ant system methodology,this paper offers an algorithm for the degree constrained minimum spanning tree problem.Compared with some other algorithms, numerical examples are tested which give promising results and useful conclusions.

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。

主网与配电网协调规划的评价指标和规划方法

城市110kV变电站作为连接主网与配电网的纽带,其选址和供电范围的划分是主网与配电网协调(以下简称主配网协调)规划的关键。文中提出协调因子及主配网协调规划评价模型,强调以提高总体运行均衡性为目标的电网规划思想。首先对变电站的基本属性进行分析,提出由运行率和关联度构成的负重系数的概念;然后利用约束圆环协调规划范围,将负重系数作为权值,利用改进后的加权Steiner最小树理论优化变电站选址;进而确定变电站的容量及供电范围。实际算例表明,从主配网协调程度考虑,所提出方法的规划结果优于传统选址规划结果。

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试和验证,并与其它算法的结果进行了比较,得到了较好的结果.

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能。提出了基于过程控制的生成树编码方法——PC编码。PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从而得到唯一生成树。为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计了过程可控的度约束生成树构造PC-Prim算法。给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法。仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法。

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

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

用于评价通信网节点重要性的多参数优化算法

为更有效地评价通信网节点间的重要性,以节点删除算法为基础,提出一种多参数优化算法。定义节点重要性参数,通过比较该参数的大小评价节点重要性,进而反映删除节点后对整个通信网的影响程度。实验结果表明,相比于节点删除算法,多参数优化算法对各节点重要性的评估更为精确。

传感器网络中基于模拟退火算法的拓扑控制方案

为了研究符合网络生命期目标要求的传感器网络拓扑控制方案,针对传统方案所获拓扑的连通冗余度过高或结构健壮性较低等弊端,从理论上对拓扑需求进行了建模分析,最终转化模型为度约束最小生成树问题,并设计了一种模拟退火算法对该问题进行处理,进而提出了一种基于模拟退火算法的拓扑控制方案。通过实验对方案进行了性能分析和验证,结果表明该方案所获拓扑具有网络整体功耗低、结构健壮性高和节点间通信干扰可控的折衷特点,并能够有效地延长传感器网络生命期。

一种能量有效的传感器监测网络成簇协议

提出了一种分布式能量有效的传感器监测网络成簇协议EECTS(energy-efficient clustering protocol for target surveillance).在该协议中,节点根据邻居节点的分布情况以及自己的剩余能量来竞争簇首.为了降低簇首的能量消耗,簇首间形成一个以基站为根的最小生成树,将监测到的数据通过多跳方式直接发送到生成树的上游节点.由于监测网络的首要任务是能够对移动目标进行不间断的监测,此协议还提出了一种簇内调度方法EECTS-1,可监测到网络中的大部分区域,并在此基础上提出了改进方法EECTS-2.这两种方法在目标进入网络时都能取得较高的持续监测度.随着节点密度的提高,EECTS协议在保证监测性能的前提下,使得传感器监测网络的寿命相应于节点数量呈线性增长.仿真结果表明,在监测性能相同的情况下,运行EECTS-1协议的网络寿命与HEED协议相同,比DEEG协议的网络寿命延长了约35%。EECTS-2协议比EECTS-1和HEED协议的网络寿命延长了约70%～80%.EECTS成簇协议可应用于军事目标监测等领域,工作时间长,监测结果具有很高的可靠性.

基于免疫—蚁群算法的度约束最小生成树算法

针对度约束最小生成树问题,借鉴人体免疫系统的适应能力和蚁群算法的全局寻优能力,提出了一种基于免疫—蚁群算法的求解方法。该算法采用Prüfer数对树进行编码及度的改进,利用免疫算法和蚁群算法的融合提高算法的执行速度和进化效率。实验结果表明,用该算法解决度约束最小生成树问题是有效的。

基于稀疏差异度的聚类方法在信息分类中的应用

针对文本信息聚类中的高属性维稀疏数据聚类问题,采用计算对象间稀疏特征差异度来度量文本对象之间的相关度,结合最小生成树的方法来进行聚类分析,提出一种基于稀疏特征差异度的聚类方法。通过实例表明,该算法对于多关键字匹配的文本信息分类十分有效,并可根据关键字的重要程度进行加权计算,使聚类更加符合实际情况。该算法将在高维稀疏数据挖掘中有着重要应用。

基于相异度计算的模块库聚类分析方法

为提高产品模块库的重用度,提出了一种模块库的聚类分析方法。给出模块库、模块重用度、模块实例相异度、相异矩阵和聚类中心的定义,以及相异度、最小生成树和聚类中心的计算方法。对模块库进行聚类分析来消除冗余的模块实例,从而提高了模块的重用度。以轮式装载机的铲斗模块库为例说明了该方法的合理性和有效性,在阈值为0.03时消除了模块库原来39种实例中11种冗余的模块实例,提高重用度39.2%,此时冗余模块与替代模块之间最大的误差小于4%。

矿井风速传感器可变模糊优选方案

针对目前矿井风流参数测试无法获得巷道的平均风速,存在不能全面监测通风网络的全部信息、监测数据达不到准确测定点、出现监测盲区等问题,结合矿井通风系统的经济型和合理性要求,重点研究风速传感器的最少监测数量和最优安装位置.采用可变模糊集理论分析影响风速传感器选址的指标因素,通过三交河煤矿为例进行现场实验和分析,建立风速传感器可变模糊优选模型.研究结果表明:通过计算相对优属度得出各分支安装风速传感器的合理权重,利用宽度优先搜索算法求出通风网络最小生成树,寻根法确定其基本回路,从而快速准确地确定出风速传感器具体安装的回路分支,得到风速传感器最优选址方案.研究结论为实现通风网路风量无盲区实时动态监测和模拟创造条件.

基于蚂蚁搜索度约束最小生成树的改进算法

针对度约束最小生成树问题,对基本的蚁群算法进行改进。提出了度信息的概念来改进转移概率,保证算法获得可行解;同时采用基于度的禁忌表这种数据结构来表示度约束生成树,并与深度优先搜索的思想结合,保证得到树的连通性;将遗传算法中的变异特征引入蚁群算法,对生成树进行局部优化。不仅提高算法的效率,而且避免早熟收敛。通过数值试验验证新算法的可行性,并与其他算法进行比较,取得了良好的效果。

基于prüfer数的遗传算法求解度约束最小树问题

度约束最小树问题属于NP-完全问题,是一类比较难解的问题,但在现实中具有非常重要的应用价值。探讨了如何将基于prüfer数的遗传算法应用于该问题,并给出了相应的算法。采用C语言和MATLAB的混合编程实现该算法,数值分析的结果显示了遗传算法求解该问题的有效性及其应用价值。

基于混合遗传算法求解CMST问题

ＣＭＳＴ （Ｃｏｎｓｔｒａｉｎｅｄ Ｍｉｎｉｍ ｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ）是通信网络拓扑结构设计中经常遇到的问题，一般解决此问题采用启发式方法，本文提出了使用混合遗传算法求解ＣＭＳＴ问题的新算法。

多目标度约束最小生成树的蚁群优化算法求解

多目标最小生成树问题与度约束最小生成树问题分别是网络优化中两个NP难题,在实际中一直有着重要的应用.本文针对同时考虑多目标和度约束情况下的最小生成树求解问题,采用蚁群优化算法思想,设计了一种求解方案,并在计算机上用Delphi予以实现.经大量数值算例求解测试,验证了算法的有效性和可行性.

求解度约束最小生成树的快速近似算法

针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.

约束最小支撑树(C-MST)问题:复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 NP-完全的 .然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 。