关键路径求解的新算法

关键路径通常是在拓扑排序的基础上求得的。文中在按广度优先搜索基础上，提出了一种新的求解关键路径的算法，该算法采用图的十字链表结构形式，不需要进行拓扑排序，算法的时间复杂度为O(n e)，较传统的算法效率更高。     

一种求解关键路径的新算法

通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法。该算法扩充图的邻接表的存储结构,使图的存储与算法求解过程共享同一存储空间。从图的源节点开始,用加权取极大运算规则,广度优先递归对图中所有节点进行编码。编码图生成后,利用反向搜索求出从源点到汇点的所有关键路径及长度。该算法比现有算法更简单直观,所需的存储空间更小,算法时间复杂度降低到O(n+e),优于现有算法的O(n2)。     

基于图的建筑施工工期求解探讨

该文介绍图在建筑施工过程中的应用,重点介绍建筑施工图的建立、关键路径的求取、应用拓扑排序讨论建筑施工工期的计算及算法分析。     

关键路径的稀疏矩阵求解算法

求解AOE网的关键路径算法一般基于拓扑排序,虽然具有较好的时间复杂度(O(n+e)),但由于必须进行拓扑排序,同时还要进行拓扑逆序扫描,使得算法本身比较复杂。针对这个问题提出了一个算法,算法采用了稀疏矩阵作为数据的存储结构,为防止关键路径丢失,采用队列方式进行操作。同经典算法相比,该算法简单,时间复杂度相近(O(n+e/n))。     

求解关键路径的新算法

关键路径通常是在拓扑排序的基础上求得的.本文算法中设计了一些独特的数据结构,在算法运行的整个过程中,求发点(源点)到收点(终点)的关键路径的过程(入栈、出栈等操作)实际只进行一遍,不需要进行拓扑排序,算法的时间复杂度为O(n e),较传统的算法效率更高.     

一种新的关键路径求解算法

关键路径通常是在拓扑排序的基础上求得的,本文提出了一种新的求关键路径的算法,该算法数据结构形式简单直观,且易于实现。用C语言设计了相应的程序验证了此算法的有效性。     

一个带环检测的深度优先搜索拓扑排序算法

提出了一种带环检测功能的深度优先搜索拓扑排序算法,详细介绍了几种基本拓扑排序算法,分析了带环检测功能的深度优先搜索拓扑排序算法的意义和作用,并证明了该算法的完备性和正确性,给出了该算法的用C++编写的实现代码。     

PLC梯形图的广义表转换

提出了利用串并联归并算法以实现PLC梯形图到指令表的转换方法。该算法将梯形图转化为有向无环图，对图中的串并联关系进行分类归并，将串并联结构按层次存储在广义表中，根据广义表生成指令表。该算法克服了传统拓扑排序算法在梯形图结构复杂时产生误判的缺陷，增加了检查逻辑错误的功能。在最佳情况下，该算法的时间复杂度为O(n)，最差情况下为O(n2)，与拓扑排序算法基本一致，有时略优于拓扑排序算法。     

贪婪算法之拓扑排序的实现

拓扑排序是图的应用领域中一种重要运算,可以根据拓扑序列串行地安排活动。本文给出了拓扑排序的贪婪算法．讨论了算法中用到的数据结构．本文采用邻接袁和栈以C＋＋语言进行仿真．给出了仿真结果。     

一种新的基于邻接矩阵的拓扑排序算法

为了降低基于邻接矩阵的拓扑排序算法的复杂性，将单顶点算法框架扩展成集合算法框架，给出一些便于进行拓扑排序的有向无环图的性质。在此基础上，定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算，给出了有向弧邻接矩阵的存储方案，最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。     

结合时空拓扑特征和稀疏表达的人体行为识别算法

基于视觉的行为分析是图像处理、模式识别等领域重要研究内容之一,在公共安全和军事上有广泛前景。在固定单摄像机下,针对单特征描述力欠缺、运动遮挡、空洞和阴影等问题,提出一种结合时空拓扑特征和稀疏表达的行为识别算法。该算法利用随机投影融合拓扑结构、几何不变特征和时空Poisson信息构造强内聚高区分低维的时空拓扑特征,结合模拟人脑解决问题的加噪稀疏机制,识别近景人体行为。实验结果表明时空拓扑特征比单特征的识别率高12.79%,在噪声情况下识别率仅降低6.15%,多行为识别率达到87.78%;该算法具有较强的时空特征描述力、噪声鲁棒性和识别高效性。     

引入序列信息的残基相互作用网络比对算法

残基相互作用网络比对,对于研究蛋白质结构与功能的关系具有重要意义.在基于网络拓扑信息进行网络比对的MAGNA算法基础上,将蛋白质的序列信息（即残基匹配度）引入到其优化函数中,确定拓扑信息和序列信息对比对的影响程度,提出适合于残基相互作用网络比对的SI-MAGNA算法.实验结果表明,SI-MAGNA算法比现有的基于网络拓扑信息的经典比对方法（GRAAL、MI-GRAAL、MAGNA和CytoGEDEVO）具有更高的边正确性（edge correctness,简称EC）.最后,使用SI-MAGNA算法对来自不同耐热温度的生物的同源蛋白质进行网络比对和分析,探索蛋白质结构对其热稳定性的影响.     

拓扑排序算法的拓展研究

拓扑排序是有向图的一种重要运算,可以根据拓扑序列串行地安排活动。为增加活动安排的并行性,文章提出并实现了分阶段拓扑排序算法。为求出最佳拓扑序列,还提出了一种全拓扑排序的实现算法。     

基于拓扑序列和量子遗传算法的贝叶斯网结构学习

贝叶斯网是处理不确定性问题知识表示和推理的最重要的理论模型之一,其结构学习是目前研究的一个热点。提出了一种基于拓扑序列和量子遗传算法的贝叶斯网结构学习算法,新算法首先利用量子信息的丰富性和量子计算的并行性,设计出基于量子染色体的拓扑序列生成策略提高了搜索效率,并为K2算法学得高质量的贝叶斯网结构提供了保障;然后采用带上下界的自适应量子变异策略,增强了种群的多样性,提高了算法的搜索能力。实验结果表明,与已有的一些算法相比,新算法不仅能获得较高质量的解,而且还有着较快的收敛速度。     

AOV网中全拓扑排序算法的设计及应用

以顶点表示活动的网络(AOV网)可用来表示整个工程中各个子工程的先后次序制约关系,利用拓扑排序算法能求得子工程的线性序列———拓扑序列。按此序列安排各子工程,能保证整个工程的顺利完成。传统的拓扑排序算法基于栈结构实现,只能求得实际存在的多个拓扑序列中的一种,削弱了算法的实用价值。文中为了弥补这一缺陷,设计全拓扑排序算法求出了AOV网中实际存在的全部拓扑序列。给出了AOV网的定义及拓扑排序算法思想,分析了传统拓扑算法的不足,提出了一个全拓扑排序求解算法。并讨论了算法中用到的数据结构,以及算法的伪代码实现,通过一个应用实例验证了全拓扑排序算法的实用性和正确性。     

加权迭代节点匹配算法及其在语言网络中的应用

复杂网络间节点匹配在很多领域中均具有重要现实意义。然而,传统的节点匹配算法通常只利用网络的局部拓扑信息,在对拥有高对称性的真实网络作用时往往会失效。为了克服这一缺点,我们近期利用网络拓扑信息和连边权重信息,提出了一种新型的同时来计算不同网络间节点相似度的方法,并在此基础上设计了一种加权迭代节点匹配算法。将该算法在高度拓扑对称仿真网络对和真实中英文语言网络对上分别进行了测试,结果表明加权迭代节点匹配算法在此类网络上优于纯拓扑迭代节点匹配算法。     

Topological model for 3D image representation: Definition and incremental extraction algorithm

In this paper, we define the three-dimensional topological map, a model which represents both the topological and geometrical information of a three-dimensional labeled image. Since this model describes the image’s topology in a minimal way, we can use it to define efficient image processing algorithms. The topological map is the last level of map hierarchy. Each level represents the region boundaries of the image and is defined from the previous level in the hierarchy, thus giving a simple constructive definition. This model is an extension of the similar model defined for 2D images. Progressive definition based on successive map levels allows us to extend this model to higher dimension. Moreover, with progressive definition, we can study each level separately. This simplifies the study of disconnection cases and the proofs of topological map properties. Finally, we provide an incremental extraction algorithm which extracts any map of the hierarchy in a single image scan. Moreover, we show that this algorithm is very efficient by giving the results of our experiments made on artificial images.     

卫星时变拓扑网络最短路径算法研究

在提出卫星时变拓扑网络模型的基础上,首先证明了传统网络中的最短路径算法（如Dijkstra算法）在卫星时变拓扑网络中使用存在局限性,给出了一种可适用于卫星时变拓扑网络的最短路径算法并利用卫星节点间邻居关系的相对规律性,对算法进行了优化．相关仿真表明该算法比目前常用的卫星网络路由算法（如DVTR）更适合于切换频繁的卫星网络．     

Real-time building of a thinning-based topological map

An accurate and compact map is essential to an autonomous mobile robot system. A topological map, one of the most popular map types, can be used to represent the environment in terms of discrete nodes with edges connecting them. It is usually constructed by Voronoi-like graphs, but in this paper the topological map is incrementally built based on the local grid map by using a thinning algorithm. This algorithm, when combined with the application of the C-obstacle, can easily extract only the meaningful topological information in real-time and is robust to environment change, because this map is extracted from a local grid map generated based on the Bayesian update formula. In this paper, position probability is defined to evaluate the quantitative reliability of the end node extracted by the thinning process. Since the thinning process builds only local topological maps, a global topological map should be constructed by merging local topological maps according to nodes with high position probability. For real and complex environments, experiments showed that the proposed map building method based on the thinning process can accurately build a local topological map in real-time, with which an accurate global topological map can be incrementally constructed.