最大公共子图的约束符号求解方法

【目的】探索求解两个图最大公共子图的方法。【方法】建立最大公共导出子图的软约束满足问题(Soft CSP)模型,提出代数决策图(ADD)的符号求解算法。首先,分别对两个图中的变量和值域进行编码,完成两个图的ADD表示;其次,基于深度优先分支定界算法的思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解。【结果】算例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,从而提高问题的求解效率。

Symbolic Algorithm of Constraint Problem for Maximum Common Sub Graph Problem

Objective]To explore the methods to solving the maximum common sub graph of two graphs.Methods]A soft CSP model for the maximum common induced sub graph is constructed,and the symbolic ADD algorithm is proposed.Firstly,the variables and domains of the two graphs are encoded,respectively,and then the two graphs are expressed by ADD.Secondly,based on the depth first branch and bound algorithm,the related operations of symbolic ADD technology are used,and then the maximum common induced sub graph is solved.Results]The result shows that the method is accurate and feasible.Conclusion]This approach can reduce the search space effectively, thus improving the efficiency of solving the problem.