用于求解正则(3,4)-SAT实例集的修正警示传播算法

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。     

警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播（warning propagation,简称WP）算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明：当子句与变元的比值α<1.8时,该判定条件有效.     

基于结构熵的警示传播算法收敛性分析

收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。     

随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.     

最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland(DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).     

基于树宽的警示传播算法收敛性分析

警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。     

基于警示传播与DPLL算法的启发式极性决策算法

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RI3实例集上的测试实验表明,该方法是有效的。     

基于K维结构熵的调查传播算法收敛性分析

信息传播算法在可满足性（SAT）问题上性能表现优越,其收敛性却依赖于因子图的结构复杂程度,至今缺少系统的理论解释。调查传播算法（SP）是解决SAT问题效果最好的信息传播算法。为有效分析SP算法的收敛性,借助因子图转换技术和鲁汶算法划分因子图社区,基于K维结构熵理论,提出了SAT实例的K维结构熵度量模型,得出了随机SAT实例的K维结构熵。分析了SP算法收敛性与K维结构熵之间的关系,给出了SP算法收敛性的K维结构熵阈值。实验证明该方法有效。     

一个正则NP-完全问题及其不可近似性

通过一个适当的归约变换,可以将一个CNF (conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性.带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性.极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足.借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换.这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4.因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题.     

一种求解3-SAT问题的新方法

可满足性问题(SatisfiabilityProblem,SAT)是计算科学的典型问题之一,目前有DP算法、SAT1.3算法和遗传算法等多种求解方法。文章根据Kennedy和Eberhart提出的二进制粒子群优化算法(BinaryParticleSwarmOptimizers),基于局部随机搜索策略,给出了一种求解3-SAT问题的新方法:基于局部随机搜索的改进二进制粒子群优化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticsearch,简称MBPSO)。数值实验表明,对于随机产生的3-SAT问题测试实例,该算法是一种高效实用的新方法。     

求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。     

Improving configuration checking for satisfiable random <Emphasis Type="Italic">k</Emphasis>-SAT instances

Local search algorithms based on the Configuration Checking (CC) strategy have been shown to be efficient in solving satisfiable random k-SAT instances. The purpose of the CC strategy is to avoid the cycling problem, which corresponds to revisiting already flipped variables too soon. It is done by considering the neighborhood of the formula variables. In this paper, we propose to improve the CC strategy on the basis of an empirical study of a powerful algorithm using this strategy. The first improvement introduces a new and simple criterion, which refines the selection of the variables to flip for the 3-SAT instances. The second improvement is achieved by using the powerful local search algorithm Novelty with the adaptive noise setting. This algorithm enhances the efficiency of the intensification and diversification phases when solving k-SAT instances with k ≥ 4. We name the resulting local search algorithm Ncca+ and show its effectiveness when treating satisfiable random k-SAT instances issued from the SAT Challenge 2012. Ncca+ won the bronze medal of the random SAT track of the SAT Competition 2013.     

A comparative runtime analysis of heuristic algorithms for satisfiability problems

The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (k?3) is O(n(k−1)), and presents a k-SAT instance that has Θ(n(k−1)) expected runtime bound.     

置信传播和模拟退火相结合求解约束满足问题

约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明：该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。     

Quantum cooperative search algorithm for 3-SAT

Grover's search algorithm, one of the most popular quantum algorithms, provides a good solution to solve NP complexity problems, but requires a large number of quantum bits (qubits) for its functionality. In this paper, a novel algorithm called quantum cooperative search is proposed to make Grover's search algorithm work on 3-SAT problems with a small number of qubits. The proposed algorithm replaces some qubits with classical bits and finds assignments to these classical bits using the traditional 3-SAT algorithms including evolutionary algorithms and heuristic local search algorithms. In addition, the optimal configuration of the proposed algorithm is suggested by mathematical analysis. The experimental results show that the quantum cooperative search algorithm composed by Grover's search and heuristic local search performs better than other pure traditional 3-SAT algorithms in most cases. The mathematical analysis of the appropriate number of qubits is also verified by the experiments.     

Approximating MIN 2-SAT and MIN 3-SAT

We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAX k-SAT problem. We also obtain some hardness of approximation results.     

基于信任度传播的体视算法

针对信任度传播算法计算量大及误匹配率高的问题,提出一种高效的计算稠密视差图的全局优化算法。首先,根据像素匹配代价的特点、视差不连续亮度变化的特征,定义具有适应性的数据约束和平滑约束,并对平滑约束进行分层调节后执行消息的传输。其次,讨论消息传输迭代过程中的冗余计算问题,通过检测消息的收敛性减少运行时间。最后,分析信任度传播算法中的误匹配问题,通过匹配的对称性检测遮挡,并提出重建数据项后,利用贪婪迭代法优化所得视差图,将图像中可靠像素的视差向不可靠像素扩散。实验结果表明,该算法能以较快的速度计算出更理想的视差图。     

A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2−2/k)ⁿ up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.).We describe a deterministic local search algorithm for k-SAT running in time (2−2/(k+1))ⁿ up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481ⁿ up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.