基于邻居信息聚合的子图同构匹配算法

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题（CSP）模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。     

求解图同构的判定算法

图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件：在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。     

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。     

改进的基于分解的子图同构算法

分析了Messmer提出的基于分解的子图同构算法，指出了该算法存在的问题。从分解和组合两个方面对该算法进行了改进。改进的算法不仅解决了原有的问题，而且其性能有所提高。实验结果证明了算法的有效性。     

子图同构验证算法OES

提出一种新的子图同构验证算法OES,采用逐条边验证的方法寻找子图同构映射,以确定查询图是否为某个数据图的子图,通过调整边的验证顺序,提高算法的执行效率。给出一种为查询图的边打分的方法,每条边的得分越低,表明其剪枝效率越高,按照分数由低到高的边序验证可以取得较好的验证效率。     

不确定属性图的子图同构及其判定算法

在分析了复杂网络(社会网络)结构的基础上,针对不确定属性图的特征,首先定义了不确定属性图的期望子图同构;由于其只用一个阈值作为限制条件,虽然方法简单,但计算量大,故接着给出了不确定属性图的α-β子图同构的定义,并对其语义进行了解释说明;第三,设计并实现了子图同构算法;最后,通过实验证明α-β子图同构优于期望子图同构,同时分析了不同阈值情况下α-β子图同构的变化规律.α-β子图同构算法的研究为不确定属性图的子图查询和社区挖掘工作奠定了基础.     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图.在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义.不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量.文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法.     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。     

基于子图同构的三维CAD模型局部匹配

针对整体相似性检索算法无法实施精确的局部结构匹配的问题,提出一种基于子图同构的三维CAD模型局部结构匹配算法.该算法通过提取CAD模型的B-Rep信息,将其表示为以面作为节点的属性邻接图.在局部匹配过程中,用户输入的局部结构被表示成"子图".待匹配的整体CAD模型被表示成"大图";则在整体CAD模型中.检索局部结构的问题就被转换成在"大图"中寻找同构"子图"的问题.子图同构是NP完全问题,通过利用CAD模型的面特征将图顶点有效细分,并利用已匹配顶点之间的邻接关系动态裁剪搜索空间,实现了快速的同构匹配.实验结果表明,该算法能实现精确的局部结构匹配,并且检索效率能满足实际应用要求.     

A hough transform technique for subgraph isomorphism

The Generalized Hough Transform is an established technique for geometric shape matching. An analogous technique is presented here for approximate solution of subgraph isomorphism problems. Its chief advantages are that it can also be used to find partial isomorphisms and that it can be readily implemented in parallel on a network of simple processors.     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

A matching algorithm between precursory 3D process model and 2D working procedure drawing based on subgraph isomorphism

To meet the urgent requirement of enterprises for three-dimensional (3D) process models, an approach based on subgraph isomorphism is proposed to solve the matching problem between precursory 3D process model and 2D working procedure drawings. First, the projection drawings of the precursory 3D process model are obtained, then the primitives are extracted and the attributed adjacency graph (AAG) is constructed. Finally, by taking the 2D working procedure drawing as the AAG, and the projection drawing as the...     

A parametric filtering algorithm for the graph isomorphism problem

We introduce a new filtering algorithm, called IDL(d)-filtering, for a global constraint dedicated to the graph isomorphism problem—the goal of which is to decide if two given graphs have an identical structure. The basic idea of IDL(d)-filtering is to label every vertex with respect to its relationships with other vertices around it in the graph, and to use these labels to filter domains by removing values that have different labels. IDL(d)-filtering is parameterized by a positive integer value d which gives a limit on the distance between a vertex to be labelled and the set of vertices considered to build its label. We experimentally compare different instantiations of IDL(d)-filtering with state-of-the-art dedicated algorithms and show that IDL(d)-filtering is more efficient on regular sparse graphs and competitive on other kinds of graphs.     

基于动态约束网络的约束优化分解

约束网络通过对较大规模的任务和问题的分解,传递了并行工程产品开发过程中的各多功能小组之间必然存在的相互制约、相互依赖的关系。在任务和问题简单分解的过程中,由于所得到的子问题之间通常是不能完全独立的,因而只能在有限程度上降低难度、简化问题。在分析了约束求解的研究现状和不足的基础上,提出了一种基于动态约束的约束优化分解方法,使得各个子任务、子问题间的关系得到进一步的分解,从而在满足原要求的基础上,得到优化的结果。     

求解入库堆垛问题的改进约束满足算法

入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长（重）的货物置于较短（轻）的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

基于关联约束非二元弧一致性的约束满足问题求解

弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP).本文提出了处理NCSP的关联约束非二元弧一致性算法.通过随机NCSP生成器产生问题实例,分别采用关联约束非二元弧一致性算法和非二元弧一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解.对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元弧一致性算法可以有效地剔除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性.