基于动态规划思想求解关键路径的算法

关键路径通常是在拓扑排序的基础上求得的。提出了一种利用图的广度优先搜索与动态规划算法相结合求解关键路径的新算法,该算法采用图的邻接表结构形式,不需要进行拓扑排序,较传统的算法具有较高的效率，同时具有较高的健壮性。     

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

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

求解关键路径的新算法

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

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

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

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

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

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

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

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

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

PLC梯形图的广义表转换

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

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

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

一种有向图并行性全拓扑排序算法设计与实现

讨论了AOV网的一种并行性全拓扑排序的算法及实现,解决了传统拓扑排序算法的单一性问题,说明了并行全拓扑排序有重要的实用价值。     

非结构化环境中基于拓扑约束的地面无人驾驶路径规划算法

针对非结构化环境地面无人驾驶路径规划过程中路径避障以及多车路径冲突的难题,通过同调以及de Rham上同调对环境中障碍物拓扑信息的精确描述,提出一种拓扑约束下基于A*算法且用时更短的路径规划算法.该算法可实现非结构化环境中多无人车全局路径的拓扑分类,从而为多车的协同规划提供一种新的研究思路.此外,结合C-空间动态广义Voronoi图(GVD)的路径拓扑分离特性,提出一种拓扑约束下可用于多无人车全局路径规划的高效算法-----C-空间-GVD-${h_S     

Reeb graph path dissimilarity for 3D object matching and retrieval

We introduce a skeletal graph for topological 3D shape representation using Morse theory. The proposed skeletonization algorithm encodes a 3D shape into a topological Reeb graph using a normalized mixture distance function. We also propose a novel graph matching algorithm by comparing the relative shortest paths between the skeleton endpoints. Experimental results demonstrate the feasibility of the proposed topological Reeb graph as a shape signature for 3D object matching and retrieval.     

拓扑梯度耦合多重最小修补路径的连续边缘图像修复算法

当前的图像修复算法都是利用非连续边缘的已知块信息来完成损坏区域的填充,造成图像模糊与视觉不连通;且修复路径都是随机确定,使其成本较高.对此,提出了拓扑梯度耦合多重最小路径快速行军的连续轮廓图像修复优化算法.引入拓扑梯度,检测出缺失区域的边缘轮廓;定义关键点择取规则,提取图像损坏区域的关键点,嵌入权重因子,建立权重距离函数,计算最小修补路径成本,并设计多重最小路径快速行军机制,提取出连续边缘,完成损坏区域填充.仿真结果显示,与其他图像修复算法相比,本文算法可检测出损坏区域的连续边缘轮廓;且该算法具有更好的修复视觉与效率.     

Robust omnidirectional mobile robot topological navigation system using omnidirectional vision

Robust topological navigation strategy for omnidirectional mobile robot using an omnidirectional camera is described. The navigation system is composed of on-line and off-line stages. During the off-line learning stage, the robot performs paths based on motion model about omnidirectional motion structure and records a set of ordered key images from omnidirectional camera. From this sequence a topological map is built based on the probabilistic technique and the loop closure detection algorithm, which can deal with the perceptual aliasing problem in mapping process. Each topological node provides a set of omnidirectional images characterized by geometrical affine and scale invariant keypoints combined with GPU implementation. Given a topological node as a target, the robot navigation mission is a concatenation of topological node subsets. In the on-line navigation stage, the robot hierarchical localizes itself to the most likely node through the robust probability distribution global localization algorithm, and estimates the relative robot pose in topological node with an effective solution to the classical five-point relative pose estimation algorithm. Then the robot is controlled by a vision based control law adapted to omnidirectional cameras to follow the visual path. Experiment results carried out with a real robot in an indoor environment show the performance of the proposed method.     

VANET环境下基于历史行为的消息路由方案

通过分析车用自组织网络(VANET)在道路交通领域中的应用现状,根据VANET的特点及其消息传输过程中面临的挑战,针对以往算法较难准确进行空间建模并较少考虑社会行为的规律性特征的问题,提出了一种基于车辆历史行为统计的消息路由方案——HBSR,具体分为计算车辆之间的连通性的节点连通算法,计算源节点和目的节点间可达时段数的拓扑重叠算法,选择消息转发路径的路径选择算法和丢包策略四部分。通过在ONE仿真平台上将其和一些典型的路由算法进行比较,实验证明HBSR方案能够更有效地在VANET中找到消息转发路径,在送达时延明显降低的同时交付率有显著提高,并且表现相对稳定。     

3D hexagonal network: modeling, topological properties, addressing scheme, and optimal routing algorithm

The 2D hexagonal mesh, based on triangle plane tessellation, is considered as a multiprocessor interconnection network. The 3D hexagonal mesh is presented as a natural extension of the hexagonal mesh. Although the topological properties of the 2D hexagonal mesh are well known, existing addressing schemes are not suitable to be extended to 3D hexagonal mesh. Then, we present, in this paper, a new addressing scheme and an optimal routing algorithm for 2D hexagonal network based on the distance formula and using shortest paths. We propose also a 3D hexagonal network that can be built with 2D hexagonal meshes as a natural generalization. We also present some topological properties, an efficient addressing scheme, and an optimal routing algorithm based on our 2D routing algorithm.     

三角网格模型的基本群分割

提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明,该分割方法可以快速、有效地实现网格的分割。     

一种新的P2P流媒体负载均衡路由算法

构建和维持一个高带宽路由结构是P2P流媒体中的一个重要问题。针对节点频繁地加入和退出覆盖会话的现状,本文设计了基于链路可用带宽的负载均衡路由算法LBR,利用已知的物理拓扑知识,在多条路由路径中选择一条对网络可用带宽影响最小的路由路径,得到轻负载的覆盖边。该算法能够动态维护高带宽的多播树,平衡覆盖会话中节点间的负载和链路间的流量。仿真实验表明,在动态环境下算法能够缓解路由上的拥塞问题,达到负载均衡的效果。