关于Kruskal算法的一种新实现

通过给网络G的每一个顶点赋予一个所在连通分支编号的方法 ,来判定每条边的加入是否构成圈 ,讨论了Kruskal算法中判定圈的新途径 ,给出了Kruskal算法的一种新的实现方法     

一种支持QoS的多播路由算法

对支持QoS(服务质量)的多播路由技术作了较详细的分析,提出了一种后向搜索最小生成树算法作为有实时性要求的多播业务的路由算法,并模拟分析了该算法的优越性。     

寻找欧拉生成子图最大边数的一个方法

设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数.     

基于笔画识别的视频图片文字提取方法

通过对笔画的对称边缘特点与文字几何特征的认识,根据二阶边缘检测算子捕捉边缘点亮暗变化趋势的能力,使用高斯型拉普拉斯算子寻找边缘点对,并构建来自笔画等窄带区域的对称边缘点对样本集.从样本集的分布规律中自适应地定出文字笔画搜索窗的尺度及方向.利用最小生成树算法实现由系列搜索窗得到的所有笔画子区域的关联聚类,通过剪枝、伪区域鉴别和阈值分割,将文字以行(含非水平行)或列的形式提取出来.实验表明,该方法对复杂背景下不同的语言类型、亮暗类型、文字行方向及文字尺度具有适应性,在ICDAR数据集上的查准率和查全率分别达到76%和75%.     

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

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

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

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

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

实际配送中多个配送点闭回路最短路径的选取

将Dijkstra算法与Kruskal算法相结合求由配送中心到多个销售点然后返回配送中心最短的闭路径,比单一的用Dijkstra算法和Floyd算法简单,比单一的用Kruskal算法精确,从而给实际计算带来方便。     

一种基于功率控制的无线传感器网络跨层通信协议

提出一种新的跨层通信协议基于功率控制的定向生成树(PCDST).本协议采用定向生成树算法以解决数据传输过程中的无效能耗问题,并控制节点的传输功率以降低网络通信竞争强度.为了更好地控制传输功率这一关键因素,构建了一个网络效用最大化模型,并基于原始-对偶算法设计拉格朗日对偶函数,推导出传输功率的最优解集.这些跨层策略的应用能够使无线传感器网络在节能的同时保持良好的通信状态.仿真实验结果表明,本协议在节约能量和提高通信吞吐量方面具有很好的表现.     

含正对角元的极小本原矩阵

本文研究对角元全为正的 n 阶木原矩阵的结构,它的本原指数为k,2≤k≤n-2,它含正元的个数为最少。我们得出,从同构观点看,仅当 k 为偶数旦 2(n-1)/k 为大于3的整数时,这样的极小矩阵才是唯一的。