sat问题发展情况概要.pptx

Sat;;时间复杂度;P问题;NP困难问题和NP完全问题（npc）;SAT问题及其研究进展;问题应用和编码方面。加强实例和工业应用研究，将生产实际中更多ＮＰ难题转化为ＳＡＴ问题进行求解，研究问题规约和表示，并研究特定领域的问题求解算法。为不同问题类型设计不同的算法是求解ＳＡＴ问题的有效途径。 预处理方面。进一步研究应用预处理技术降低ＳＡＴ的问题规模和求解空间，并将有效的预处理技术融入其他求解算法。 求解算法。 当前难解问题方面。针对目前多数求解器无能为力的难满足实例、大规模问题实例等，加强问题内部逻辑结构的研究，将一些应用的特定知识作为启发式信息，提高解决实际问题的效率。 求解器实现方面。研究求解算法的设计与实现，降低求解时间和空间代价。 理论研究方面。研究各类典型ＳＡＴ求解算法的证明系统、证明复杂性及算法分析等。 ;sat求解算??;完备求解算法;DPLL算法;Cdcl算法;ＬＡ算法;不完备求解算法;ＳＬＳ算法;ＭＰ算法;EA算法;组合求解算法;几种典型ＳＡＴ求解算法比较;