合取范式3可满足问题的局部搜索近似算法

The Local Search Algorithms for Maximum 3-Satisfiablility Problem

合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.

Maximum satisfiability problem is the central problem in theoretical computer science. Maximum 3-satisfiability problem（Max-（3）-Sat） is one of the most important sub problem of the maximum satisfiablity problem. Local search has been testified to be very effective for solving this problem by many times of real computation. However, there is no related results for analy- zing the performance of the local search method to solve the problem. This paper approaches the local search method to solve the maximum satisfiablity problems and analyzes the performance of the method. The central issue of the paper is to discuss the local search algorithm to solve the Max-（3）-Sat. The authors show that the one-bit-flip local search algorithm can achieve the per- formance ratio 4/3 for solving the Max-（3）-Sat; and the algorithm of one-bit-flip local search fol- lowing the conditionally all-bits-flip can achieve the performance ratio 5/4 for solving Max-（3）- Sat. And the authors design a new local search algorithm to solve the Max-（3）-Sat problem using the one-bit-flip local search following the all-bits-flip, and show the new algorithm have the performance ratio 8/7. The 8/7-approximation algorithm can be extended to solve the Max-（k）-Sat problem with performance ratio （2k2r-2）/（2k＋1） for k≥4. Finally the authors give the two-bits- flip local search algorithm to solve the Max-（k） Sat problem, and prove the algorithm can have the performance ratio 1＋1/2k＋1＋k（k-1）/（n-k）for k≥4.Repeatedly running the local search algorithm can further improve the performance of the solution. The results of the paper demonstrate the inevitability for local search to have high performances in solving the maximum satisifiablity problems.