Application of rough graph in relationship mining

Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relationship mining shows effectiveness of it.     

粗糙集代数关系的图结构分析

粗糙图理论是知识发现、知识挖掘的新的理论工具.结合粗糙图理论,构造了基于代数算子的粗糙图结构,将分析多个粗糙集之间的代数关系映射为相应粗糙图的结构分析.结合粗糙图理论中的类最短路算法,以情感计算中挖掘性格规律为例说明了该方法的应用过程.粗糙集代数关系的图结构分析是粗糙集理论中又一研究方向.     

新型公交网络模型与最优线路选择算法

针对公交线路的最优线路选择问题,给出了基于标号公交网络二分图模型,在此模型基础上给出了最小换乘条件下的可行线路的“纺锤-修剪”搜索算法,进而给出在最小换乘条件下的最短路径和换乘站点的数学规划方法.最后给出算例并验证了该方法的有效性．     

赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。     

基于带宽剩余率的脉冲耦合神经网络最短路径算法

利用脉冲耦合神经网络（pulse coupled neural network, PCNN）寻找最短路径是一种非确定性算法,运算的复杂度只和最短路径的长度有关,和路径图的复杂程度无关。已有的PCNN最短路径算法只考虑路径长度,而未考虑其他参数,如带宽和时延等。这里除了考虑路径长度,同时考虑实际中带宽剩余量对网络的影响,提出了一种基于带宽剩余率的最短路径算法,用带宽剩余率参数来控制神经元阈值,寻找最短路径。仿真结果表明,该算法可以寻找到全局最优解。     

带二次参数赋权的多阶段网络最短路算法

当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的.     

基于仿射混杂系统控制设计的机器人导航控制

根据单纯形仿射混杂系统的可达性分析设计控制律,使机器人在平面任意两点间运行,保证其安全性并考虑其最优性.对机器人的状态空间进行三角划分,根据目标吸引原理来建立其对偶图,针对对偶图提出路径规划算法得到最短路径穿越的三角形序列.然后根据仿射系统在单纯形中的性质,提出运动规划算法,得到机器人的角速度和线速度,控制机器人穿越给定的三角形序列到达目标点.仿真结果表明了方法的有效性.     

新型公交网络模型与最优出行路径算法

给出一种标号的二分图公交网络模型,在此模型基础上给出线路换乘与最优出行路径的算法,这种算法充分利用标号信息给出站点网络图的边权函数.基于站点网络图不仅能够搜索换乘线路而且能够找到最短路径.最后利用天津市部分公交系统验证了该模型及方法的有效性.     

HAMILTONICITY IN 2-CONNECTED {K_(1,3) F}-FREE GRAPHS

ＨＡＭＩＬＴＯＮＩＣＩＴＹＩＮ２－ＣＯＮＮＥＣＴＥＤ｛Ｋ_（１，３）Ｆ｝－ＦＲＥＥＧＲＡＰＨＳ￥ＬＩＧｕｏｊｕｎ（ＭａｔｈｅｍａｔｉｃｓＤｅｐｅｒｔｍｅｎｔｏｆＹａｎｔａｉＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ，Ｙａｎｔａｉ２６４０００，Ｃｈｉｎａ）ＬＩＵ?..     

基于脉冲耦合神经网络的Live wire新方法的仿真研究

提出了一种基于脉冲耦合神经网络(PCNN)的Live wire分割新方法,Live wire方法是把图像当作一个连通图,在边上定义一个代价函数,然后通过搜索最短路径来找物体的边界,把用户指定的物体边界上的两点之间的最短路径当作物体的边界。最短路径是Live wire方法的重要步骤,本文在介绍脉冲耦合神经网络的基本工作原理和特性的基础上,将改进的脉冲耦合神经网络算法引入到Live wire边缘检测的算法中,用于最短路径算法的研究。并在改进算法中应用路径封锁和在线训练来提高算法的准确性和应用性。     

多目标最短路径进化求解方法

提出一种无圈有向图条件下的多目标最短路径进化算法。使用变长染色体对路径编码。进行染色体适应值分配时同时考虑支配关系及密度信息，保持了种群的多样性。有界精英保留策略保证了算法的优化性能。对算法的收敛性进行了证明。理论分析和实验表明，该算法可以在较短时间内获得多条多目标优化路径。     

给定限制期条件下最小风险路径的选取算法

讨论在给定限制期情况下，边的长度（权值）为区间数的赋权图最小风险路径的选取算法，该算法将非线形比例路径问题的求解转化为最短路问题的变权迭代，算例及实际应用取得了令人满意的效果。     

粗糙网络及其应用

粗糙图理论是知识发现、知识挖掘的新的理论工具。对粗糙图理论做进一步的研究,首先给出了有向粗糙图的定义,并进一步定义了粗糙网络及粗糙网络中的类流,又讨论了有向粗糙图及粗糙网络的表示形式。通过推广传统最大流算法,给出了粗糙网络中的类最大流算法,并将其应用于新的一类关系挖掘问题中。     

TDMA战术数据链中最小时延抖动的固定时隙分配算法

现有TDMA战术数据链的时隙分配算法主要关注战术信息传输的时延,随着以数据链网络为中心的联合作战的深入发展,战术信息高实时性的传输需求日益凸显。提出一种基于最小时延抖动的固定时隙分配算法,首先将TDMA战术数据链时隙均匀分配问题转化为图论中包含确定边数的不含回路的最短路径环问题,然后采用动态规划法来求解这个包含确定边数的不含回路最短路径环问题并给出具体的算法步骤,最后进行仿真实验来验证算法的正确性和有效性,算法较好地满足了高实时性战术信息的传输需求。     

最短路树的计数、产生和优化问题

首先给出了在非负网络中构造最短路网络的算法，然后将树形图的计数算法到最短路网络中，设计出了最短路树计数问题的算法，将Gabow算法应用到最短路网络中，设计出了产生全部最短路树的算法，最后研究了最短路树的优化问题。     

基于网络图的网络化防空作战系统分析与优化

采用图论的有关理论方法,建立了网络化防空作战系统与空袭目标交战的网络图模型;以此模型为基础,利用改进的关键路径算法,得到网络化防空作战系统与目标对抗过程中的关键路径;进而根据得到的关键路径,提出了优化系统性能的方法,为网络化防空作战系统的分析和优化,提供了一种新的思路和行之有效的定量分析方法。     

基于二分图最优匹配的虚拟网络映射算法

针对现有虚拟网络映射存在开销较大、资源利用不够合理的问题,提出了一种基于二分图最优匹配的虚拟网络映射算法。首先以虚拟节点和物理节点为顶点构建二分图,将节点映射问题转化为二分图最优匹配问题;其次将节点资源评价最高的物理节点与节点需求评价最高的虚拟节点优先匹配,并利用Kuhn-Munkres算法求解二分图最优匹配,依据匹配结果进行节点映射;最后利用 k-最短路径算法实现链路映射。实验表明,与以往的映射算法相比,提出的映射算法在保持较高映射成功率的同时,提高了长期收益开销比,且资源利用更加合理。     

有向最短哈密尔顿路问题的DNA算法

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。     

最短路网络及应用

首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 0 ( n2 )的构造最短路网络的算法 .最后研究了最短路网络在最小成本最短路 ,最短路计数和最短路树中的应用     

精度与程度的逻辑差粗糙集模型及其算法

基于精度与程度的逻辑差需求,提出了精度与程度的逻辑差粗糙集模型,定义了粗糙集区域概念. 在精度与程度的逻辑差粗糙集模型中,得到了粗糙集区域的基本结构和精确描述,提出了计算粗糙集区域的宏观算法和结构算法, 并进行了算法分析与比较,得到了结构算法具有时间优势和空间优势的结论. 最后用一个医疗实例对模型及其算法进行了说明. 精度与程度的逻辑差粗糙集模型,部分拓展了程度粗糙集模型和经典粗糙集模型,在决策表应用中具有广阔前景.