求解有向图中三个分图问题的研究

强分图、单向分图和弱分图都是研究有向图的子图的连通性问题,求解强分图的算法有很多。总结了强分圈的求解算法,主要是算法实现的基本技术和特点;通过论述求解单向分图和相应无向图的团问题的等价性,提出了求解单向分图问题是NP问题的观点;最后又阐述了求解弱分图的方法,并给出了一个具体的算法。     

基于无向图转有向图的同构判别

无向同构图指的是在两个图中寻找顶点之间的映射关系,通过映射使原本形式各异的两图中的各条边保持对应的关系.为了有效提高寻找无向同构图的时间效率、简化操作,首先研究了无向图同构的矩阵存储方式,并针对性地提出了把无向图转换为有向图的同构算法.与矩阵存储算法相比,该判定算法的时间更为简短.最后给出了实现该算法的相关程序以及用该算法对无向图进行判定的过程和结果.     

求解图最大团的并行算法

本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。     

图与它们的表示之间的关系

本文研究了无向图的性质与无向图表示之间的关系     

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

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

混合鱼群优化算法的贝叶斯网络结构学习

针对从数据集学习贝叶斯网络结构准确率不高的问题,提出了一种基于混合鱼群优化算法的结构学习算法。首先,利用互信息和最大似然树生成初始无向图;然后,由无向图的边随机生成初始种群,将粒子群算法的个体记忆和交流意识引入鱼群算法的行为模式,减小算法搜索行为的盲目性;最后,将优势遗传算法的变异和交叉算子应用于算法的寻优过程。仿真实验结果验证了改进后的算法具有更强的寻优能力。     

基于遗传算法的二部图判定算法

应用遗传算法来判定二部图的具体过程是首先将无向图G的节点随机分配到两个不同社区中,然后用遗传算法进行进化操作,优化无向图G的模块化函数Q,当Q取最小值且无向图G的边只存在于两个社区之间,则无向图G为二部图.实例分析结果验证了算法的有效性.     

利用视觉显著性的前景目标分割

针对图像中的前景目标分割问题,提出一种视觉显著性引导的前景目标分割算法.对原始图像进行预处理后分解为互不重叠的超像素区域.将这些区域构成一个无向图,相邻两个区域间存在边,通过计算相邻区域间的特征差异得到边的权值.提取图像边缘的超像素区域作为背景区域,利用无向图计算各超像素区域相对于背景区域的视觉显著性,得到初始显著图.对初始显著图进行改进和优化,根据视觉显著性计算结果采用自适应阈值进行前景目标分割.在公开的图像数据集MASR-1000、ECSSD、Pascal-S和SOD上进行实验验证,并和目前流行的算法进行对比.结果表明,本研究算法在查准率、召回率、平均绝对误差及F-Measure等方面优于目前流行的几种算法,用于图像和视频的前景目标检测与分割是正确有效的.     

分布式两阶段混合流水车间调度

针对分布式两阶段混合流水车间调度问题(DTHFSP),提出一种教学优化算法(TLBO)求解工厂分配问题并设计一种启发式算法解决机器分配问题,以最小化最大完工时间.首先,采用均衡工厂负载的方法生成初始班级;然后,引入淘汰机制以加强对优势解的局部搜索效率,并在自学阶段增加反思过程强化教学结果;最后,通过大量实例实验验证了教学优化算法在求解分布式两阶段混合流水车间调度问题时的搜索优势.结果分析表明教学优化算法在求解分布式两阶段混合流水车间调度方面具有更好的稳定性和求解质量.     

定位路线与库存组合优化问题研究

定位路线问题是定位配给和车辆路线问题的集成决策,库存水平对定位和路线问题有重要影响.本文在分析物流系统总成本的基础上,建立了随机需求的定位路线与库存组合优化问题的数学模型.针对模型的NP-hard属性,设计了两阶段启发式算法:第一阶段用先路线后定位的方法求得初始解;第二阶段用交换法对初始解进行改进,库存控制变量在每次路线优化时根据订货费用、缺货费用和运输费用而迭代求得.最后通过实例计算,定位-路线-库存集成优化结果与定位-路线和库存独立优化时的方案相比,大大降低了物流系统成本,从而证明了物流系统优化时考虑库存策略的重要性,同时表明了该算法在求解此类问题时的可行性和有效性.