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

发布时间：2024-01-24 11:54

　　最大可满足性(Maximum Satisfiability,MaxSAT)问题、最大团(Maximum Clique,MC)问题、最大公共子图(Maximum Common induced Subgraph,MCS)问题是计算机科学中经典的NP难问题,也是人工智能、运筹学等领域的经典组合优化问题。三个问题是解决实际问题的有效模型,其高效的完备算法的设计具有重要的理论意义和实践意义。MaxSAT、MC和MCS的优化目标不同,但是都可归约为如何解决冲突问题。冲突是指不存在合理的方案满足给定的约束条件。MaxSAT的冲突是指在任何真值指派下均存在不满足子句;MC的冲突是不相邻的顶点不能同时构建团;MCS的冲突是顶点匹配不满足边约束条件,构成公共子图的顶点匹配数降低。MaxSAT子句冲突检测的技术可以发现MC、MCS问题中顶点之间隐藏的冲突关系。找到的冲突越多,分支限界算法的界的质量越高,搜索分支越少。基于找到更多冲突、有效改进界的思路,深入研究了以上三个代表性的NP难问题,设计了基于分支限界的高效完备算法。(1)对MaxSAT问题,提出了三个优化冲突集的策略,有效地改进了MaxSAT算法的下...

【文章页数】：150 页

【学位级别】：博士

图2.1含有6个顶点的简单无向图

图2.2一个简单的加权无向图

图2.4关联图的生成实例

图4.2一个简单的非完美图

本文编号：3883769