| 基于对称破坏的子图同构约束求解算法 |
| |
| 引用本文： | 徐周波,梁轩瑜,刘华东,戴瑀君.基于对称破坏的子图同构约束求解算法[J].计算机工程与设计,2020,41(2):397-401. |
| |
| 作者姓名： | 徐周波 梁轩瑜 刘华东 戴瑀君 |
| |
| 作者单位： | 桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004;桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004;桂林电子科技大学 机电工程学院,广西 桂林 541004 |
| |
| 基金项目： | 广西自然科学基金;国家自然科学基金 |
| |
| 摘 要： | 为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解。实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率。
|
| 关 键 词： | 子图同构 约束满足问题 对称性破坏 自同构 置换群 |
Constraint satisfaction algorithm for subgraph isomorphism with symmetry breaking |
| |
| Affiliation: | (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) |
| |
| Abstract: | 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. |
| |
| Keywords: | subgraph isomorphism constraint satisfaction problem symmetry breaking automorphism permutation group |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
