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

Constraint satisfaction algorithm for subgraph isomorphism with symmetry breaking

作　　者：徐周波[1] 梁轩瑜 刘华东[1,2] 戴瑀君 XU Zhou-bo;LIANG Xuan-yu;LIU Hua-dong;DAI Yu-jun(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China;School of Mechanical and Electrical Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

机构地区：[1]桂林电子科技大学广西可信软件重点实验室,广西桂林541004 [2]桂林电子科技大学机电工程学院,广西桂林541004

出　　处：《计算机工程与设计》2020年第2期397-401,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目（61762027、U1501252）;广西自然科学基金项目（2017GXNSFAA198172）

摘　　要：为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(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.

关 键 词：子图同构 约束满足问题 对称性破坏 自同构 置换群 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]