ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.398-400



м㣺SATЧʵЧ
˳
ժҪ˼Solar㷨һSATĿ㷨.ʵ۷,Solar㷨ײл.Solar㷨лɴȵSATЧ.
ؼʡȡʽ,,﷨,˷,м.
ͼšTP301
Parallel Computing:An Effective Method for Improving the Efficiency of Solving SAT Problems
JIN Ren-chao
(School of Computer Science and Technology Huazhong University of Science and TechnologyWuhan430074)
HUANG Wen-qi
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing100080)
AbstractBased on the thought of quasiphysical and quasisociological,the Solar algorithm is an efficient algorithm for solving SAT problems.It is proved by the theoretical analysis and experimental results that the algorithm is naturally suitable for parallel computing.The efficiency of solving SAT problems can be greatly improved by taking a simple method that parallelizes the Solar algorithm.
Key wordsCNF (conjunctive normal formula),satisfiability,quasiphysical,quasisociological,parallel computing.
Solar㷨һ˼SATĿ㷨1.ף1ʾSolar㷨3-SATBellʵҵBart Selman1994깫GSAT+w㷨2.̽Solar㷨ײл,֤лȷʵЧSolar㷨Ч.ڼӲ۸͵ʵʱ,ʵ.
1SAT
1.ԪV=x1,x2,...,xm,VһԪԪķ,Ӿֵȡ,ȡʽconjunctive normal formula,CNFӾĺȡ.
2.ԪV=x1,x2,...,xm,Ԫx1,x2,...,xmһȡֵΪһֵָ,ΪX.1ʾ,0ʾ,Xʣ0,1m.һֵָĳCNFӾ䣩ָCNFӾ䣩һֵָΪ.
3.ȡʽԣSATָCNF,ǷһCNFֵָ.3-SAT޶CNFÿӾǡ3ֵSAT.
4.ѡԪV=x1,x2,...,xm,ÿشVѡ3ͬԪ,50ĸʾÿԪǷȡ,õ3һӾ.ظl,õlӾһCNF.˷CNFΪһΪlmԪ3-SAT.l/m4.3ʱ,Ϊ3-SAT3.
SAT3-SATⶼNPȫģ4,ĿǰĶʽʱ㷨.3-SATĿǰѧձõĲSAT㷨Ŀ.
2Solar㷨ʱķֲ
Solar㷨һ㷨.ͬһ,شӶܵļ㶯ѡȡһִ.Ϊھ㷨ʱ临Ӷȵǰ㷨.̰ķ,пʹ޷Զֲŵġ塱,¼㷢һѭÿ·ķ,ʹʱָ.Ŀǰûиõѡ·ĲԵ,ȡѡķǺģ5.
Solar㷨еԵͬһÿμвͬļʱ.ͨʵǷ,Ծ3-SAT,Solar㷨ͬһĶμļʱ֮Ĳ൱ɹ.
ͼ1ʾSolar㷨һ1 000Ԫ3-SAT500μļʱֲ.ͼ1ÿĿ2s,ʾһʱΣĸ߶ȱʾʱڸʱڵļĴ.ͼпԿ,500μƽʱΪ35s,ʱֲķֵt0=68sһʱ.ڴʱ֮,ʱķֲʵݼ.

Fig.1
ͼ1
3л
Ϊ,ͼ2ʾĸܶȺͼ1еĸʷֲ.
ɿ֪,,,һμʱ䲻tĸΪ


Fig.2
ͼ2
kμʱ䲻tĸΪ,kμʱtķֲܶȺΪ,kμʱtֵΪ,y=a-t,

k=1ʱ,һμʱֵ.ˣk̨мļٱΪ

ЧΪ
ɴ˿ɼ,ǵĽģ,òмԴﵽԼ,ٶȵ߱μӼļ̨,ǲ㷨ܴﵽ뾳.ļٶʵ,Ҫʵʼʱֲķֵһ0t0λ,t0a˵ǳС.,ǫ̈ʱٵt0ʱ,һٵЧʻ½.ڴ֮ǰ,ЧӦǺõ.
10̨΢ͬʱɵ3-SAT,ÿ10ͳƼʱ.1ͱ2.õ΢Ϊܱ586Intel MMX pentium,Ƶ166MHz,ڴ32M,ϵͳΪLinux,Cʵ.ʵӽǵģ.
Table 1 
1
No.variables:1000; No.clauses:4250ڡTime unit:s

Problems12345678910Average
Average computing times 2.09.727.954.730.12.914.71.412.43.3
Minimal computing times Tmin0.71.81.75.43.30.94.50.83.20.5
Accelerate rates S=/Tmin2.95.416.410.19.13.23.31.83.96.66.3
Parallel efficiency E=S/100.290.541.641.010.910.320.330.180.390.660.63

Ԫ1000,Ӿ4250,ۼʱλ,,ƽ,ƽʱT,
̼ʱTmin,ٱS=/Tmin,ᲢЧE=S/10.
Table 2
2
No.variables:2000; No.clauses:8500ڡTime unit:s

Problems12345678910Average
Average computing times 294.047.9534.0226.2105.5174.0194.275.3218.3387.1
Minimal computing times Tmin18.75.0107.521.714.264.736.015.038.6113.3
Accelerate rates S=/Tmin15.79.65.010.47.42.75.45.05.73.47.0
Parallel efficiency E=S/101.570.960.501.040.740.270.540.500.570.340.70

Ԫ2000,Ӿ8500,ۼʱλ,,ƽ,ƽʱT,
̼ʱTmin,ٱS=/Tmin,ᲢЧE=S/10.
ĵĽǣ(1) Solar㷨ļʱķֲʹȻʺϲм㣻(2) ۷,мʹSolar㷨õԼ;3 ʵ֤,ڹģΪ1 0002 000Ԫɵ3-SAT,10̨ɽƽٶ67,ʹЧʴﵽ0.60.7.,Solar㷨вмSATЧ.
оõȻѧ(No.19331050)863߿ƼĿ(No.863- 306-05-03-1)ҡ塱ʵǼƻ𡢸ߵѧУʿѧλרл(No.960 48703)йѧԺоѧоʵ ҿ.߽˳,1965,ʿ,ҪоΪ 㸴ۣ㷨.,1938,,ʿʦ,Ҫ Ϊ㸴ۣNPѶ㷨.
ͨѶϵ:˳,人 430074,ѧѧ뼼ѧԺ
ߵλ:˳(ѧѧ뼼ѧԺ人430074)
(йѧԺоѧоʵҡ100080)
ο
1Huang Wen-qi,Jin Ren-chao.The quasiphysical and quasisociological algorithm solar for solving SAT problem.Science in China (Series E),1997,27(2):179186
(,˳.SAT㷨Solar.йѧ(E),1997,27(2):179186)
2Selman B,Kautz H A,Cohen B.Noise strategies for improving local search.In:Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94).Seattle,Washington,D C:AAAI Press,1994.337343
3Mitchell D,Selman B,Levesque H J.Hard and easy distributions of SAT problems.In:Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92).San Jose,CA:AAAI Press,1992.459465
4Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.New York:W.H.Freeman and Company,1979
5Motwani R,Raghavan P.Random Algorithms.London:Cambridge University Press,1995.127129
1998-06-22յԭ,1999-04-13յ޸ĸ
