max-sat解中的有哪些信誉好的足球投注网站和推理.pdf

M拇SAT求解中的有哪些信誉好的足球投注网站和推理 专 业： 计算机软件与理论 博士生：林瀚 指导老师： 苏开乐教授 摘要 命题逻辑的可满足性问题(SAT)是计算机科学中的核心问题．最大可满 足问题(M措SAT)是SAT问题的一个自然的扩展．对于给定的CNF公式，M册 SAT问题的目标是找到一个赋值使其满足最多的子句．M孵SAT是一个重要 的NP一难优化问题．由于人工智能、电路自动设计、统计物理、生物信息学等领 域的许多问题都可以转化为M抒SAT问题，所以近十年来，M觚_SAT问题引起 越来越多的兴趣和关注。 求解M错SAT的算法可以分为完备算法和不完备算法．就不完备算法而 言，M觚-SAT和SAT并无很实质的区别，所以当前对Max—SAT算法的研究主要 集中在完备算法．设计高效完备算法的关键在于如何进行快速的有哪些信誉好的足球投注网站和有效的 推理．本文的工作正集中于这两方面． 在推理方面，本文提出一个比前人更一般的MaX—SAT逻辑框架，给出 了MaX—SAT推理中等价、蕴含以及A一等价等概念的形式化定义．在这一基础 上，本文进一步给出若干A一等价规则的例子，扩充了求解MaX—SAT的推理规 则．作为运用推理规则的例子，本文利用已有的推理规则改进了前人给出的一 个不可满足子句数目的下界． 在有哪些信誉好的足球投注网站方面，当前的完备算法多数采用分支定界的有哪些信誉好的足球投注网站机制．提高分支定 界算法效率的关键在于求得紧的下界．本文分析了前人计算下界方法的不足， 提出了基于学习的计算方法．具体而言，学习分成两方面．一方面，有哪些信誉好的足球投注网站树中除 根结点外的每个结点都向自己的父结点学习不相交的矛盾子句集。另一方面， literal 一种被称之为失败文字检测(faileddetection，FLD)的方法被之前的一 些Max—SAT求解工具用于计算下界；在本文的算法中，有哪些信誉好的足球投注网站树中的每个结点都 向过去有哪些信誉好的足球投注网站过的结点学习FLD的有效性，并根据之前的效果来决定在当前结点 MAx-SAT求解中的有哪些信誉好的足球投注网站和推理 是否运用FLD．这种基于学习的计算方法，既避免了不必要的计算，又保证了下 界的单调性． 带权重的M噼SAT问题是MaX—SAT问题的扩展，它们具有更强的描述问 题的能力和更广泛的应用．本文将上述方法进一步扩展到带权重的问题，并 开发了一系列的求解工具．实验结果表明，这些新的方法，无论是在随机实 例还是在由实际问题转换而来的结构化实例，都提高了已有求解工具的性能． 值得一提地，其中一个工具LB—SAT在2007年的国际Ma珏SAT求解评比中，解 决了最多的带权实例．而在2008年的M册SAT求解评比中，我们开发的新求解 除了设计和实现实用的求解工具以外，本文也从理论上关注MaX—SAT算法 复杂度的改进．本文定义了和前人不同的非标准复杂性度量，对M擗2一SAT和 问题，给出了D。(2K／5625)的算法，其中K是公式的子句数．用类似的方法，本文 还得到MaX—CUT问题0+(2／5‘625)的算法，其中M足图中所有边的权重之和． 关键词：SAT，Ma治SAT，分支定界算法，下界的计算，MaX．CUT Searchand InferenceinMaX—SAT Solving Major： So危wareand Computer Theory Ph．D．Candidate： HanLin Professor Supervisor： KaileSu Abstract ‘IIhe propositional a sat