ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



㷨߼*
ƽ
ժҪ㷨ĳʼռ䡢ԡ̿һ,㷨߼ɳʼ״̬ռȷ.ζ̵߼н,ʼ״̬ĳ޷.
ؼʡ㷨,һ߼,ģ.
ͼšTP18
The Logical Analysis of Search Algorithms 
ZHANG Yu-ping 
Abstract The state space, search heuristics, and move generator in searching solutions to a given problem are characterized by first order language, which implies that the logical properties of a search algorithm are determined by its state space, that is, the logic describing the searching process has compactness and the class of initial states has finite close property.
Key wordsSearch algorithm, first order logic, model.
㷨ʱõķ.ѡʼ״̬,ӦһЩԡ㷨,һʱ,õʺĽ.,ѡȡʼ״̬֮,Ӧòµ״̬,ܹжĳǷ.Ǽѧʵϰģʽ1,ѡԵĻ,˺ܶٵʵ㷨.о㷨ģ,ָĳʼռ֮߼ϵ.ȷ߼߼ϵ֮ϵ,ָʵһ߼е3:Ƶϵϵģ.ڴ˻,ʼռ֮߼ϵ.ڼѧӦʱ,Ը߼ƳЧ㷨,ĵĿڷ̵߼.
㷨,жĳ״̬Ƿĳ൱жĳģǷ()һ,Ϊڹģ͡ʼ״̬ıʱ,Ҫһ.ʵ,㷨Ĺвõļö,ĶԭֿתΪһLһЩ.תΪж״̬ģǷһּ,ʱĳʼ״̬ΪLģ,ϣͨ⼴L.
ʵ,ͨĹ൱һϵ*.ѡʼ״̬,ʹԿԽA,ζŦ*A.µϵ*ͬھ߼еϵ,ǵ⾭ʵ任֮,*Aͬڦ()(A),Цʽתͬʱһ߼ģͱʾʼ״̬.ʼ״̬,w,ƦԵw,wΪʼ״̬ĽԦΪʼ״̬Ҳ.Ǵ˹ϵΪ*w.ֱµвᵼ».ҰÿҪܵж̵һʾ.ʱ,ÿ䶼й̶·,תӳ,Aʱ·.롰ҡûпɽ,(AB)(A)Ħ(B)֮һûбȻϵ,ζABʱ·ֱAB·һûϵ.ڵ1 GSAT(greedy satifiability)2Ϊ˵ιתӳ,Ϊҵṩ֤.Ӹĳʼ״̬ʼ,ʹ,óĳԵж.ѡһʼ״̬,̵ʾ(*)﷨ϵ*,*AζŶеÿģͦ,()(A).**֮ϵھ߼Ь֮ϵ.Ļʵ,˿̻*ʵĶ,ʵ̵ֶ߼.
ʩ㷨ʱĳʼ״̬һ㰴һģʽѡ,GSAT㷨2,жʱĳʼ״̬ѡ,ʹõĳʼ״̬һĸֵ.һ֡еĲ,ͬʱ߼ƵҲƵ.ת߼Ƶһ,ڴ˻,İ̵ͬƵ,㷨߼.Ϊʼ״̬Ǹģͼ,Ǹ3,伯T,ʹTģ͵ļ,ʱA,*AҽT(A).óĽ۵ͬһ߼óĽ,Ƶϵ*н.ζŵһĿĿ꼯϶ĳʼ״̬õʱ,Ŀһʼ״̬õ.ʱ,вõĲʵ϶ûбҪ.,ΪʵĿ,Ҫʹõĳʼ״̬಻һTģ͵ļ,ʺһĹ.,Ҫʲôһʼ״̬һĳʼ״̬,ǱĽҪʵֵĿ.
(ʼ״̬ĳ). ǳʼ״̬һ,TL.һT,:(a) *,w,w*ʱ,ԡ.(b) Tģ͵ļ.vCҽT().ʱ,Ҳһ.
ڲʱ,T()ΪT.Գʼ״̬ϷԵԼζ:϶۵ĳʼ״̬ʱ,ٽ۵ĳʼ״̬Ҳ.֮ԲԼ,ΪȻʼ״̬໥Ƶ,ΪLģͲһȵȼۣ3,
*w,w*ʱ,һ¦ԡw.ĳ߼гƹ.߼,ҪԳȵȼۼ.(a)(b)ΪʵͬĿ.
(ʼ״̬޷). ʼ״̬һT.ĳʼ״̬,Դ˲òó޽ۼ϶еĳʼ״̬õ,Ա.
жʼ״̬һ,ָһ۶Գʼ״̬ϵĿ̻.ϵ*ͬڹϵʱ,һ߼Ҳ.ʵ,߼гǿĽ,ֻҪĽۡ,Ҫ޵ĽۼϡǰͿԵõͬĽ,һ߼йģ͵ĳĿ̻.֤ƹ˾߼йڴ˽۵֤,⽫ڵ2и.
1 㷨߼
ĿжһЩǷ.ԵжЧ:Եѡʼ״̬趨.趨һʼ״̬֮,൱ڶǷһж,жǿɲ.һ,㷨޵ʱڸһȷеĴ.㷨Լ߼жԡ㡱ϵ()Ķ.߼,ÿ䶼һЩ﷨ɷ֡߼ʵɵ.ĿΪ˱ʾһʵ,ʵǸַ.Ϊ˽ɻ﷨ɷֹɵַĺ,Ҫģĸ.ģ,һЩ﷨ɷֵõ˽,Ⲣζ˺.Ϊ˸ĺ,Ҫָһ֡жٵ㷨.߼,Եж()һȷķʽ,Թʽȹɵļ.ַ,ȷظÿ丳ֵ.˷ںܶ߼б,ⲢһָЧ㷨.߼,ʵֶԵж,ķָʱĸӶ.
ڶ֮,Ҫо﷨֮ϵ:һж﷨ʵܷͨ﷨ʽõ.νģж﷨ʵ.ʽ,Gentzen֤᷽ۡȶΪʵĿ.ȱ:һ,桢ٵжǲж.,ûһЧĲж.Ϊ,Ҫʽ㷨,ʵֶԵıȽЧж.㷨ΪʵĿ,Դﵽ߼Ƶķ޷ٵõĽ,*ͬ,ʵֶԺ桢ٵЧж.ǰۿ֪,ͬϵǷȡѡĳʼ״̬.
Կ㷨GSAT2ݵۿԸȷʵ.GSAT㷨ָµ㷨,(SAT)һָЧ㷨.
Input:һСġ-׼͵AȻͦ
for i:=1 to 
:=ɵĸֵ
for j:=1 to 
if A then return 
:=ԣp. /*n(ԣp)=max{n(ԣp):pAгֵԪ}.ԣpǸıԶԪpĸֵõ¸ֵ.wһֵ,nwwAӾ.*/
end for
end for
return δҵAĸֵ
GSAT߼.Ϊ,һЩɵһL={t,f,ci:iw} ϵT={x(x=tx=f),x(x=tx=f)}.
Tȡֵʵ:ÿģͽͬԪ,Ƿֱǳt,fĽ,ĳʾֵͼֵ,ciڱʾԪpiȡֵ.TζÿԪȡֵȡֵ.ڴ˶Ļ,ԽGSAT㷨漰ĸֱֵʾΪTģͼL.Ϊ,תӳ.
(GSATʼ״̬תӳ).
(1.1) ={i:0in}GSAT㷨еһֵ,Tģͦ():i=1,ci=t,i=0,ci=f.
(2.1) (pi)ci=t,
(2.2) (pi)(ci=t),
(2.3) (AB)Ԧ(A)Ŧ(B),
(2.4) (AB)Ԧ(A)Ħ(B).
һ,p1,...,pnnԪ,ٶ(pi)Ԫ(ci=t),(pi)(ci=t),ԶƵתӳ,Ϊp1,...,pn(.),1in.
,ĸֵԼA,Aҽ()(A),ԣp1,...,pnAҽ()p1,...,pn(A).Ħԣp1,...,pnݵĶGSATе,ʾͬʱı丳ֵԶԪp1,...,pnȡֵ֮õĸֵ.,Խֵ䡰תĿԱʾΪһģͶһĿ.潫 GSATжÿĹL.Ϊ,LʾGSAT㷨еn(ԣp)=max{n(ԣp):pAгֵԪ}.AʽC1...Cn,µ(A,p)p1,...,pn(A,p)ʾʵ:
(1) i1,...,ik(p(Ci1)...Ħp(Cik)ġik+1,q(q(Ci1)...Ħq(Cik+1))),1i1,...,ik+1nͬ.qAг.
(2) κεıԪp1,...,pn,p1,...,pn(A,p)Ķ巽ʽ(A,p),ֻҪúp1,...,pn溯.
A,ѡȡһֵ.ʩGSATʱ,õaĸֵҪ´εĲ.
(a) жǷA.
(b) һεõĸֵԲA,ıԶĳһԪȡֵ.
ʩ´,ܵõĸֵ,϶Aǿ.ʩĵ2ֲʱ,ϰϸһЩѡֵ,ʵָЧ.
ΪGSAT,ȶʽʵ.GSAT,ϰϽǾСġ-׼ÿ-֦3.Ϊ㷨вĵȼ,,ʵʲпһЩȼ۵,ǵ﷨ʽͬ.ʽ֮Ĳһ߼һ㲢Ӱ,SAT㷨,ȴʹ㷨óͬĽ.,ܴڵȼ۵AB,һβAжΪ,ͬһβпܵòBĿ.Ϊ˱ʾʽͬµì,µмٶ䶼Ӧڸʽġġ-׼,߽Ǿֱ׼͵.
תӳҾGSAT㷨ĵ1:һֵ,жǷһ.=1ʱ,GSATĿܹ.һ,ΪGSATȫ,ҪһЩ.ΪGSATġ-׼͵Ľṹ,ҪӦöԻضһ.,LһЩν,ͨ(Godel)ķĽṹ.˼Ӱ쵽ȵ.,L1GSATȫ,һתӳ,Ƶ:*Aҽ()(A).ӵĶζʱȽȻ,Ҫٶȷ.֮ĲͨĽṹɶ,ṹ.Ϊ˶תӳ,ȶӳi,0iܦ,ĦGSAT㷨еĲ.
(GSAT̵תӳ). 
ٶp1,...,pnǳAеԪ.
0(A)=(A).
1(A)=ipi(A).
2(A)=i,jͬ(pi,pj(A)(A,pj)).
3(A)=i,j,kͬ(pi,pj,pk(A)(A,pj)pj(A,pk)).
...
(A)=i¦i(A).
Ļ,GSAT,Ѿ*,*ȷеĺ.æ,ӿԹǰ˵תӳ.ʹ*֮ĹϵñȽȷ.ȻԦΪֵܹABĿ㸳ֵ,Ǹֱ̲ӵعABĿ㸳ֵ.һ,ȻֵͬĽ,ǲֵܱ֤ȫͬ(ģͽṹͬ).ϸµĹ۲Է,GSATתӳ߼乹.Ϊڹ,ʱ,ûõһLе.صļƹ㵽һ߼ĿΪģ۵ļ֤ĵĶ.
㷨ʵϲͬ߼Ƶ,*,Ա֤㷨ȷʵܹõ߼Ľ.о߼ϵͳʱ,˺ܶпɿԡȫԵ߼,ǶӦһģͼ.ȷĽܹ߼ķõ.ģͼϵķʽ,ģͦ伯,Եõʵ,ɴ˻µƵϵ,Ӷһ߼.ͨѡģͼԵõбھ߼ļ,ֱ߼ģ̬߼ʱ̬߼ֵ߼ǵ߼б.,ģͼϾ߼۵,һ̶Ҳ㷨.
߼,ٶTģ͵ļ,䶼Tĳģʱ,ģvʵѾTģ.,ʱӵģͲܸĽģȷƵ.ھ߼,һģǷѱһģͼ,ԸǷܱģͼеĳģȷ.߼жԳʵ3,ƹӦļ3,֤Ķ.Ϊϵ*߱ԡҡĽ,ڶҪ޵Ľۼϡ,Ҫǵ2ڵ֤Ҫ.㷨,ϣͨѡ㷺ĳʼ״̬ԵõĽ.Ҫ֤:ѡĳʼ״̬һĳʼ״̬.ѡĳʼ״̬һʼ״̬,ͬʱֿһʱ,㷨õĽʵϵͬһ߼óĽ.ĵĶ̻˳ʼ״̬һĳʼ״̬֮Ĺϵ.
2 ֤
Ϊ֤ĵĶ,Ҫģйس˺ͳĽ.3ݼUϵһuUһЩӼļ,ü:u;xu,yu,xyu;xu,xyU,yu;xUʱ,xuxu.һϵĳ˵ĴԲȻ,Ǽۣ3еĶ:vUӼϵһϡռҶԡɷ,x,yvʱ,xyv,ڳuv3.
Uϵĳu,ģͼ{xxU}.uxҲһģ,:A,uxAҽ{xUxA}u.ģеĳ3.ģͼеÿģͶAʱ,ĳҲ.öеԼ,ģеʵ֤ĵĶ.
SɦԿн۵ļ,ASҽ()(A).ݶ㷨һԼ,ٶSǿ.ݶǰ֪,޼sS,w,ʹws,Tw.UʾS޼ɵļ.sU,塴sUаs޼ϵļ,v={s:sU}.
SǷǿյ,vҲǷǿյ.ͬʱ,vԡɷ,Ϊs,tU,ʽsɡt=st.vUϵһu.ݶеԼ֪,xU(xS,ɦһ޽ۼ),ڳʼ״̬x,ʹæ(x)(x).õǼеԼ,(x)(x)ĺǶκεAx,(x)(A).ģеĳ,w=xuxTģ.ΪÿxT.ʱ,w*,ΪA,Ӧ*A֪()(A).Ϊ(A)L,ģͼ{x:xU}(A)ģ͵ıxļڳu.Ϊ{x:x*A,xU}{A}.ģеĳ֤(w)(A),Ӷw*A,w*.ݳʼ״̬϶*ķԿ֪,ԡ,ǶҪ֤.
3  
һ߼㷨Ĺ,GSAT2Ϊ˵ļ߼.̵ĿԾ㷨߼ɳʼ״̬ռ,߼Ƶ֮ĲΪʼ״̬ģͼϵĲ.һ,߼֮ϵ۵ģͼ,Ϊǵ﷨Ƶϵпɿȫ,߼ǿɶ.,̵߼ʱ,עڳʼ״̬,Ķ̻˳ʼ״̬һ״̬֮Ĺϵ.㷨пܵĳʼ״̬һһ߼̻,̾н.Ľһһĳʼ״̬ķ.
㷨оƸЧ㷨Ѱҿٵ;㷨ϰɵģ,۲㷨ģϵı.ЩGSATоме.2ݱ߼о㷨߼,㷨ν߼֮ϵ.㷨һ֡еĲ,һʼ״̬Ľۼǵݹ,гʼ״̬ĽۼҲǵݹ.,תӳĴȻ.,㷨÷ǵݹĳʼ״̬ռʱ,ۼϵĵݹǷȻ.,ĵбڶ㷨ĵݹʵ,ʵ,ɵݹۼõתӳ䲻*߼,ΪҪȻ̱.
㷨жһ״̬ǷжȻرʾΪϵ().İϵ*ʾ.һʼ״̬,aͨõжĽ,*AʾԦΪʼ״̬ԵõA.羭߼ϵ,㷨߼Ҳڶ*.ϵ*뾭߼ϵ()Ƶ.ϵ֮ĲԱ:(1)*A*Bʱ,*ABǷһ.(2) *w,w*ʱ,wĽṹ֮ǷбȻϵ.Ȼ*ͬ,ģ۵ļԲʧΪ*ʵù.ģۼ˳ʼ״̬֮ϵ,֤˳ʼ״̬ĳ޷.߽ڽһĹ㷨.
оõȻѧͺոߵԺУѡп.
߽ܣƽ,1966,ʿ,,ҪоΪӦڼѧ߼.
ͨѶϵ:ƽ 100083,պѧѧ빤ϵ
ߵλƽպѧѧ빤ϵ100083
ο
1½.˹.:ѧ,1996(Lu Ru-qian. Artificial Intelligence. Beijing: Science Press, 1996)
2Selman B, Kautz H. An empirical study of greedy local search for satisfiability problem. In: Proceedings of the 11th National Conference on Artificial Intelligence. Cambridge, MA: MIT Press, 1993. 4651
3Chang C C, Keisler H J. Model Theory. Amsterdam: North-Holland Publishing Company, 1973
1997-11-10յԭ,1998-03-09յ޸ĸ
