求有向图必经结点的一个有效算法

本文给出在任意有向图中求必经结点的一个算法,以及对应的BASIC语言写的程序。算法使用了深度优先搜索、脱机最小值算法、不相交集的合并算法,以及能体现优先队列功能的2—3树算法,从而使算法的时间复杂性最多为O(nlogn e),空间复杂性最多为O(e),n,e分别为图的结点数和边数。当e≥nlogn时,本算法时间复杂性为O(e),它在一个常数范围内是最优的。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

基于方向优先和对向搜索的改进Dijkstra算法

传统Dijkstra算法在搜索最短路径时需要逐一遍历网络图中所有顶点,计算量大,占用存储空间大,搜索效率很低。因此,针对交通网络的空间特性和传统算法的不足,改进存储结构,采用“方向优先+对向搜索”相结合的搜索方法,以减少存储空间,缩小搜索范围,从而加快搜索速度,提高算法的搜索效率。实验数据表明：与传统算法相比,改进的算法能够更有效地搜索交通网络中的最短路径,具有更好的实用价值。     

基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

一种求解二部图最大匹配问题新算法及其应用

提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。     

异构图形数据的近似语义匹配技术研究

以流程工厂协同设计应用为背景,提出基于允许误差的最大语义图匹配（MSMGE）算法的异构图形数据近似语义匹配模型。利用类无向图来描述2D和3D异构图形数据的工程属性和拓扑关系,消除了图形信息的异构性,并建立各种类实体的属性标签词典来消除2D和3D属性信息的异构性,用语义表达式来表示类无向图顶点和边的语义关系,将异构图形匹配转化为近似语义图匹配。通过基于工程语义对类无向图进行语义分割和基于最大公共序列算法的语义表达式比较、语义规整和语义裁剪等方法,降低了匹配搜索空间,提高了近似语义图匹配效率,实现了近似语义图匹配判断。该研究已经在流程工厂设计软件中得到较好地应用。     

基于改进的3维ICP匹配的单目视觉里程计

针对目前流行的单目视觉里程计当移动机器人做“近似纯旋转运动”时鲁棒性不强的问题,从理论上分析了其定位鲁棒性不高的原因,提出了一种基于改进的3维迭代最近点（ICP）匹配的单目视觉里程计算法．该算法首先初始化图像的边特征点对应的深度值,之后利用改进的3维ICP算法迭代求解2帧图像之间对应的3维坐标点集的6维位姿,最后结合边特征的几何约束关系利用扩展卡尔曼深度滤波器更新深度值．改进的ICP算法利用反深度不确定度加权、边特征梯度搜索与匹配等方法,提高了传统ICP算法迭代求解的实时性和准确性．并且将轮子里程计数据作为迭代初始值,能够进一步提高定位算法的精度和针对“近似纯旋转运动”问题的鲁棒性．本文采用3个公开数据集进行算法验证,该算法在不损失定位精度的前提下,能够有效提高针对近似纯旋转运动、大场景下的鲁棒性．单目移动机器人利用本文算法可在一定程度上校正里程计漂移的问题．     

不可达顶点剪枝算法及其在最短路径中的应用

[k]步可达性查询用于回答图[G]中从顶点[u]到达顶点[v]最多[k]步是否存在路径,但其多用于无权图的可达性研究。针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模。运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为[O(n+e)]和[O(n)],这里[n]和[e]分别为图中顶点的数目和边的数目。该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能。最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性。     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

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

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

基于索引数组与集合枚举树的最大频繁项集挖掘算法

由于其内在的计算复杂性，挖掘密集型数据集的全部频繁项集非常困难，解决方案之一是挖掘最大频繁项集。集合枚举树是最大频繁项集挖掘算法中常用的数据结构，最大频繁项集的挖掘过程也可以看作是集合枚举树的搜索过程。为缩小集合枚举树的搜索空间，采用宽度优先和深度优先相结合的混合搜索策略，提出了一种新的最大频繁项集的挖掘算法Index-MaxMiner。该算法首先设计了索引数组这种新的数据结构，并给出了一个基于二进制位图技术的索引数组的计算方法。通过为每个频繁项增加包含索引，Index-MaxMiner利用一次宽度优先搜索得到了候选最大频繁项集，使集合枚举树的第一层结点个数大幅度减少。然后在候选最大频繁项集中通过深度优先搜索，得到全部最大频繁项集，从而实现了集合枚举树的跳跃式搜索，大大缩小了搜索空间。实验结果表明，该算法可有效提高最大频繁项集的挖掘效率。     

图数据流上时间尊重图模式匹配算法研究

现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果.针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率.对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销.     

Theoretical comparisons of search strategies in branch-and-bound algorithms

Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.     

Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O(M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O(m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure.     

基于分层法的通风网络图绘制算法研究

最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径,采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中;且采用几何相交方法判断分支交叉,效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层,求解整数规划问题优化节点分层减少长边;采用模拟退火遗传算法优化节点排序,从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程,采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。