基于冲突的NP难问题完备算法的研究

目录

声明

1 绪 论

1.1 课题来源与研究目的

1.2 选题背景和研究意义

1.3 研究对象的国内外研究现状

1.3.1 最大可满足性问题的国内外研究现状

1.3.2 最大团问题的国内外研究现状

1.3.3 最大公共子图问题的国内外研究现状

1.4 算法的评价标准和测试集的选择

1.5 本文的研究内容

1.6 内容组织结构

1.7 本章小结

2 NP难问题的可转换性和冲突技术

2.1 问题的定义和符号

2.2 研究对象的相互转换

2.2.1 最大团问题编码为最大可满足性问题求解

2.2.2 最大公共子图问题编码为最大团问题、最大可满足性问题

2.3 基于冲突改进算法的预估值

2.3.1 冲突改进最大可满足性问题的下界预估

2.3.2 冲突改进最大团算法的上界预估

2.3.3 冲突改进最大公共子图算法的上界预估

2.4 本章小结

3 基于优化冲突集的最大可满足性问题求解

3.1 最大可满足性问题

3.2 最大可满足性问题的相关定义

3.3 分支限界最大可满足性问题的算法框架

3.3.1 MaxSAT算法的分支策略

3.3.2 MaxSAT算法的预估下界的方法

3.4 基于优化冲突集提高最大可满足性算法下界

3.4.1 推理规则优先

3.4.2 单子句排序

3.4.3 进一步失败文字检测

3.5 优化冲突集策略的实验结果与分析

3.5.1 对比算法和测试集

3.5.2 实验结果

3.5.3 实验分析

3.6 环式展开推理规则提高最大可满足性算法下界

3.6.1 一般环式结构

3.6.2 利用环式展开规则计算下界

3.6.3 环式展开规则的复杂度分析

3.7 环式展开规则的实验结果与分析

3.7.1 对比算法和算例集

3.7.2 实验结果

3.7.3 实验分析

3.8 本章小结

4 基于权重覆盖的最大加权团问题求解

4.1 最大团问题

4.2 最大团问题的相关定义

4.3 分支限界最大团算法

4.3.1 分支限界最大团算法框架

4.3.2 最大加权团算法的上界预估方法

4.4 权重覆盖：计算最大加权团上界的新方法

4.5 基于权重覆盖的新算法WC-MWC

4.5.1 最大团问题的分支限界搜索算法

4.5.2 利用权重覆盖最小化分支

4.5.3 权重覆盖方法的复杂度分析

4.5.4 WC-MWC：基于权重覆盖的新WMCP算法

4.6 WC-MWC算法的实验结果与分析

4.6.1 对比算法和算例集

4.6.2 实验结果

4.6.3 实验分析

4.7 本章小结

5 基于冲突学习的最大公共子图问题求解

5.1 最大公共子图问题

5.2 最大公共子图问题的相关定义

5.3 分支限界最大公共子图算法

5.3.1 定界的方法

5.3.2 分支策略

5.4 基于奖励的分支学习

5.4.1 基于强化学习的分支策略

5.4.2 McSplit+RL算法的复杂度分析

5.4.3 McSplit+RL算法求解有向图和标签图及其变种

5.5 强化学习分支策略的实验结果与分析

5.5.1 对比算法和算例集

5.5.2 实验结果

5.5.3 实验分析

5.6 本章小结

6 总结与展望

6.1 主要工作总结

6.2 研究展望

致谢

参考文献

附录1 攻读博士学位期间发表的主要论文

附录2 攻读博士学位期间申请的专利和其他成果

附录3 攻读博士学位期间参与的课题项目