基于多重序列所有公共子序列的启发式算法度量多图的相似度

Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity

提出了启发式A*算法度量任意多个图的相似度方法,该算法将多图表示多重序列,在多重序列的匹配点上计算多重序列的所有公共子序列数,得到的所有公共子序列数用来度量多图的相似度。该算法避免了在非匹配点上的冗余计算,最大化后缀序列的所有公共子序列数的启发函数值,将访问的节点限制在两个序列匹配的子集,减少了计算节点的个数。与现有度量图的相似度方法相比,该算法不仅可以度量任意多个图的相似度,而且计算过程简单,通过启发信息的引导能够快速地度量多图的相似度。

A heuristic algorithm A＊for measuring the similarity of multiple graphs is proposed.In this algorithm,the multiple graphs are represented as multiple sequences,then the number of all common subsequences in the matches of the multiple graphs is calculated,and this number is used to measure the similarity of the multiple graphs.This algorithm avoids the redundant calculations in non-matches of multiple graphs,maximizes the heuristic function value of all common subsequences of the suffixes sequences,limits the search nodes to the subset of matches between two sequences,thus reducing the number of the calculation nodes.Compared with the existing graph similarity methods,the proposed algorithm can not only measure the similarity of multiple graphs,but also simplify the calculation process.The similarity of multiple graphs can be quickly measured using this algorithm with the boot of the heuristic information.