应用破圈法求图的最优树的一种新算法

本文依据破圈法的原理提出了求图的最优树的一种新算法,并给出了具体的实现步骤。     

基于地理信息系统的配电网停电范围智能识别方法

为了能够在设备检修时快速准确地得到该设备影响的停电范围,在系统梳理配电网陪同停电规则的基础上提出了一种基于地理信息系统(GIS)与拓扑分析的设备停电范围智能识别算法.利用GIS图形化功能直观高效地识别由于空间距离的相互影响导致需要陪同停电的设备.结合图论和配电网的特点,提出节点分裂改进邻接矩阵的方法来描述配电网结构.该方法可在设备检修导致配电网拓扑结构发生变化时,避免建立和维护繁琐的开关状态信息表,对改进的邻接矩阵通过广度优先算法实现陪停范围的智能辨识.IEEE 6算例和某省级配电网实际应用表明,本文所提方法可以快速准确地识别陪停范围.     

求解U型装配线平衡的改进启发式算法

在假设条件下建立单U型装配线第一类平衡规划模型,根据表达产品作业优先关系的邻接矩阵特征,确定入口和出口候选作业集合,依据综合阶位值大小依次选择分配作业,求解单U型装配线平衡问题.结合小算例,详细说明了改进启发式算法的求解过程并编程计算,运用改进启发式算法程序计算了32个经典算例,将计算结果和评价指标分别与启发式算法和遗传算法进行对比,验证了该改进启发式算法有效,且计算速度快、计算结果稳定.     

最短路径算法在校园导游系统中的应用

用无向网表示学校的平面图,设计了该平面图的存储结构,并应用最短路径算法实现了查询图中各景点的相关信息,以及查询图中任意两个景点间的最短路径的功能;应用克鲁斯卡尔算法构造该平面图的最小生成树,求出可以连通所有景点的最短路径。该系统为新生熟悉校园环境提供了方便。     

点和边有容量约束的网络最小费用最大流算法*

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明：点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。     

一种基于生成树的分类去除关联规则冗余方法

在信息及数据爆炸的时代,冗余问题已经成为数据挖掘者获得知识的重大障碍,而目前解决的方法会导致关联规则的不完整性。基于此,文中引入了有向超图表示关联规则,重定义了邻接矩阵,介绍了冗余规则分类处理思想,将冗余规则分为从属规则和重复路径规则,通过VB编程去除了从属规则冗余,以及利用生成树算法去除了重复路径规则冗余。实验结果证明,此方法创新性地结合了图论中有向超图、生成树与关联规则的知识,维护了关联规则的完整性和准确性,同时去除了全部冗余规则。     

基于改进AdaBoost算法的复杂网络链路预测

链路预测是复杂网络的重要研究方向,当前的链路预测算法因可利用的网络信息有限,导致预测算法的精确度受限。为了提高预测算法的性能,采用改进的AdaBoost算法进行链路预测。首先根据复杂网络样本建立邻接矩阵,完成样本的矩阵化处理;然后采用AdaBoost算法进行分类训练,通过权重投票获取预测结果;最后,考虑到复杂网络弱分类器预测正负误差分布的不均衡问题,设置权重调整因子η及其调整范围[η1,η2],并根据η值动态调整AdaBoost算法的多个弱分类器分类结果的权重,从而获得准确的链路预测结果。实验结果证明,相比其他常用网络链路预测算法及传统AdaBoost算法,改进的AdaBoost算法的预测准确率优势明显,且在节点数量较多时,其预测时间性能和其他算法的差距较小。     

利用Excel求解邻接矩阵的幂矩阵

邻接矩阵的幂矩阵可以用于求解集合上二元关系的传递闭包及图论中的路径矩阵、强分支等,但当邻接矩阵的阶数较高时手工求解计算量大且繁琐。针对此问题,利用Excel中的函数求解功能,简化求解过程。     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

产品协同设计的任务分解与耦合机制研究

在产品协同设计的初始阶段,合理的任务分解有利于协同设计的顺利进行,从而提高设计效率与质量。文章研究了任务的分解与耦合策略,采用按功能划分和按结构划分相结合的方式,并根据设计组的满意度对产品协同设计的任务进行了分解,用设计结构矩阵描述设计任务的耦合关系,提出了利用图论中基于邻接矩阵的深度优先搜索算法求出耦合任务集的原理与方法,并通过具体实例验证了该方法。