基于对称破坏的子图同构约束求解算法

Constraint satisfaction algorithm for subgraph isomorphism with symmetry breaking

为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解。实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率。

To avoid the generation of repeated solutions and improve the efficiency of constraint solving in subgraph isomorphism problem,a constraint solving algorithm for solving subgraph isomorphism based on symmetric breaking was proposed.Based on the symmetry breaking method,the automorphism detection process was improved and a CSP model of the subgraph isomorphism problem was constructed by symmetry breaking lexicographic order constraint which was generated by the permutation group operation,and it was solved using CSP backtracking algorithm.Experimental results show that the proposed algorithm effectively reduces the search for repeated solutions and significantly improves the search efficiency compared with the traditional algorithms.