| 引用本文： |
-
刘桂珍,徐周波,唐浩.最大公共子图的约束符号求解方法[J].广西科学院学报,2017,33(1):25-31. [点击复制]
- LIU Guizhen,XU Zhoubo,TANG Hao.Symbolic Algorithm of Constraint Problem for Maximum Common Sub Graph Problem[J].Journal of Guangxi Academy of Sciences,2017,33(1):25-31. [点击复制]
|
|
| 摘要: |
| [目的]探索求解两个图最大公共子图的方法。[方法]建立最大公共导出子图的软约束满足问题(Soft CSP)模型,提出代数决策图(ADD)的符号求解算法。首先,分别对两个图中的变量和值域进行编码,完成两个图的ADD表示;其次,基于深度优先分支定界算法的思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解。[结果]算例结果表明,该方法准确可行。[结论]该方法能有效缩减搜索空间,从而提高问题的求解效率。 |
| 关键词: 最大公共子图 软约束满足问题 全局约束 ADD |
| DOI：10.13657/j.cnki.gxkxyxb.20170220.001 |
| 投稿时间：2017-01-10 |
| 基金项目:广西自然科学基金项目(2015GXNSFAA139285,2014GXNSFAA118354)和桂林电子科技大学研究生创新项目(2016YJCX62)资助。 |
|
| Symbolic Algorithm of Constraint Problem for Maximum Common Sub Graph Problem |
|
LIU Guizhen, XU Zhoubo, TANG Hao
|
| (Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi, 541004, China) |
| Abstract: |
| [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. |
| Key words: maximum common induced sub graph soft constraint satisfaction problem global constraint ADD |
