基于符号OBDD的子图同构约束求解算法

论文摘要

针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法（OBDD-SI）。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术对不满足约束的值进行过滤,从而得到子图同构的所有解。实验结果表明,本算法具有良好的求解性能。

论文目录

1 相关基础知识

1.1 子图同构

1.2 约束满足问题

1.3 有序二叉决策图

1.4 弧一致性技术

2 基于OBDD的子图同构约束求解算法

2.1 子图同构问题的CSP模型

2.2 CSP模型的符号OBDD描述

1)度约束c1。

2)边约束c2。

3)相邻约束c3。

2.3 符号求解算法

3 实验分析

1)实验1采用M4Dr-n、Scalefree、AIDS三种数据集进行测试。

2)本组实验采用一类由图像分割生成的中型规模的数据集Images-PR15进行测试,实验2运行时间对比如表4所示。

3)本组实验采用生物化学领域中规模较大的PDBSv1、PDBSv3、PPI三种数据集进行算法验证。

4 结束语

文章来源

类型: 期刊论文

作者: 刘桂珍,徐周波

关键词: 子图同构,约束满足问题,有序二叉决策图,弧一致性

来源: 桂林电子科技大学学报 2019年05期

年度: 2019

分类: 信息科技,基础科学

专业: 数学

单位: 桂林电子科技大学计算机与信息安全学院

基金: 国家自然科学基金(61762027),广西自然科学基金(2017GXNSFAA198172),桂林电子科技大学研究生教育创新计划(2017YJCX54,2017YJCX08)

分类号: O157.5

DOI: 10.16725/j.cnki.cn45-1351/tn.2019.05.003

页码: 357-362

总页数: 6

文件大小: 654K

下载量: 25

基于符号OBDD的子图同构约束求解算法

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢