ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



һ֪ʶĸ㷨
ܺ ѩ
ժҪ֪ʶĸ⼴֪ʶ֪ʶͬʱΪάԶɾ֪ʶ.е֪ʶ·ͨ¶ѽ.ĴĽṹһֵ֪ʶӦԼͼΪʱĶʽʱ㷨.ԼͼУ㷨ͨһԵϵḶ́õº֪ʶ.
ؼʡ˹ܣ֪ʶ£㷨ԣԼͼԼ.
ͼšTP182
A Tree-like Knowledge Base Revision Algorithm
MA Shao-han TAO Xue-hong
(Department of Computer Science Shandong University Ji'nan 250100)
Abstract Knowledge base revision is to add new knowledge into the knowledge base, and to delete old knowledge if it is necessary for preserving consistency. The recently proposed knowledge base revision methods are all intractable in general case. By restricting the structure of the knowledge base, a polynomial revision algorithm is given in this paper when the corresponding constraint graph of the knowledge base is a tree. In the constraint tree, the authors use a bottom-up process to get the revision knowledge base.
Key wordsArtificial intelligence, knowledge base revision, algorithmic complexity, constraint graph, constraint satisfiability problem.
֪ʶ˹оռҪλ.Ginsberg˽˶֪ʶ·һǻģ͵ķһǻڹʽķЩͨ¶ѽ(intractable)1.Իģ͵ķף1ָ֪ʶHornʽļϣ֪ʶHornʽҳһϽʱڶʽʱ㷨Իڹʽķף24и˼µĶʽʱ㷨.
1 
߼ķΧ֪ʶĸ.Tʾ֪ʶ⣬֪ʶ⹫ʽ޼pʾҪ֪ʶ.֪ʶT͹ʽpTpʾ֪ʶTм֪ʶpº֪ʶ.Ϊ²±ʾõĸ·.÷šʾ.
11. Ginsberg·.Tǿ֪ʶ⣬pǿ֪ʶ

W(p,T)Tpݵļ⹫ʽļ.
TGp={T{p}|TW(p,T)}.
T={a,b,abc},p=c,



2.1 WIDTIO(when in doubt throw it out)·.

ַ,,Tейʽ.еTpTwidp={c}.
ĽصWIDTIO·.
2 㷨
ṹ⸴.ֱϿ֪ʶи֪ʶ֮ϵԽУ֪ʶʱжϺìܾԽ.ΪѰҿɽ㷨ǽ֪ʶϵ.Rina Dechter˶Լ(constraint satisfiability problem)ֵά(truth maintenence)оУĽṹΪͣõЧ㷨5,6.ǽ˼֪ʶ£֪ʶṹΪͣҵһʽʱ㷨.
2.1 Լͼ
ͼ֪ʶйʽĹϵÿʽʾΪͼеһ㣬ʽһͼӦһߣù.ǳͼΪԼͼ,ԼеĶżԼͼ(dual constraint graph)7.
磺T={a,b,abc}ӦԼͼͼ1ʾ.

ͼ1
һ֪ʶԼͼΪļϣΪ֪ʶ.֪ʶУʽ1ʽͬһ.ɼ֪ʶʽϵϼ.Ľ֪ʶԼͼΪ͵ļ.
2.2 㷨˼
3. ɾ.ԹʽTҵһݼU(һݼSTUS)ǽT-UСɾ.ּСɾжTмСɾĲTɾ.
ӹʽTȥɾʹʽݣʱʽеĹʽΪмݼеĹʽ.Twidp㷨ɾ.
㷨ȹT{p}ԼͼԼͼж֧ͨpļpķ֧ڵĹʽìܣ֧Ӱ죬,ֻ迼ǰpķ֧.÷֧Ϊɲ㷨.ΪpһҪڸº֪ʶ⣬ǽpΪ⴦.
pΪһ.ΪʽRͨC1,C2,...,Ck(ͼ2ʾ).

ͼ2
ÿCiΪ01ʱTiɾ֪.ԭ֪ʶǿģһTiCi=0Ci=1һTi㣬ɾΪ.Ciȡ01Ti㣬˵ԭ֪ʶⲻ.
C1,C2,...,CkһȷֵԿR,T1,T2,...,TkK+1.T1,T2,...,Tkɾ֪RɾҲ֪(ֵ˵,RΪ棬ɾΪգΪ{R}).K+1ɾĲΪC1,C2,...,CkΪֵʱɾ.C1,C2,...,Ckֵɵضֵʱɾ.ЩϵļС󲢼õɾ.ˣɾɵɾ.㷨˼Ƶ.
㷨pΪУԵ(֤ĳʱӽ)ɾһֱе㣬ˣõɾõTwidp.
2.3 㷨
㷨УԼͼÿ㱣һֵṹ1.Pʾ븸Ĺ(޴);C1,C2,...,CkʾkӽĹ(Ҷ޴);Vʾʽֵ.
1

PC1C2...CkV
000...00
..................
111...11

ֵеÿһгһ.һ㣬븸㡢ӽĹ⣬ΪY1,Y2,...,Yj,Щֵ.PC1,C2,...,Ckһֵ˵Y1,Y2,...,YjһֵʹʽΪ棬ֵVֵΪ1()Ϊ0().˵,ڹһʱڲӰʽʱʹùʽΪ.رԭ֪ʶˡС޸ġԭ.
ÿлһS,S0ݼ¼P(븸Ĺ)Ϊ0ʱԸýΪɾ,S1ݼ¼PΪ1ʱԸýΪɾ.Ϊ,NODE.SʾNODES.
WIDTIOиµ㷨.
㷨. REVISION1.
: ǿҿ֪ʶT={f1,f2,...,fn}֪ʶp
: Twid p
Step1.
(1.1) T{p}Լͼ.
(1.2) pΪͼһĽ㣬 Twidp=T{p},㷨.
(1.3) pڷ֧,㷨޷¡,㷨.
(1.4) pΪУֵ.
Step2.
pΪУԵ(֤ĳʱӽѴ)ÿNODE:
(2.1) NODEΪҶ:
P=0ʱV=0S0={NODE}S1=;
P=1ʱV=0S1={NODE}S0=.
(2.2) NODEΪм(ӽֱCHILD1CHILD2...CHILDkNODECHILDiĹCi)
NODEֵP=0ÿһjC1C2...CkȡֱֵΪu1,u2,...,uk,
ӦDj=CHILD1.Su1ݡCHILD2.Su2ݡ...CHILDk.Suk,
V=0,Dj=Dj{NODE},
ЩP=0ӦļϵļСϣЩСϵĲNODE.S0.
P=1ÿһͬĲNODE.S1.
(2.3) NODEΪ: /* (֪ʶp)һҪΪ棬ˣֻV=1. */
V=1ÿһjC1,C2,...,CkȡֱֵΪu1,u2,...,uk
ӦDj=CHILD1.Su1ݡCHILD2.Su2ݡ...CHILDk.Suk,
ЩϵļСϣЩСϵĲU.
Step3.
Twidp=(T-U){p}(TɾUйʽ,ټp).
(2.2)УֵÿһjӦһDjDjǸNODEڸȡֵʱɾĲ.ɾS0ݺS11ǿգNODEɾΪջΪ{NODE}DjʵѡNODEǿɾĲ.ǣֵÿһӦŶԷǿɾһѡ.ˣ󼯺ϵļС󲢼ɼΪѡļС.ǿk+1άW¼ѡW1ݡWkݶӦCHILDi.Sui=,Wi=0,Wi=1Wk+1ݶӦNODEV=1Wk+1=0,Wk+1=1.,Ϊ1˵ѡNODEķǿɾΪ0ʾûѡ.磬NODEֵ(C1C2C3V)=(1010)һ㷨
D=CHILD1.Su1ݡCHILD2.Su2ݡCHILD3.Su3ݡ{NODE},
CHILD1.Su1ݣ,CHILD2.Su2ݣ,CHILD3.Su3=,DʵCHILD1CHILD2NODEǿɾĲ.¼ѡ,W=(1101).ʹֵÿһӦһ飬ǽЩӦӦɾ.ǽݴ˶㷨м.
ֵͨ޸,ʹW.޸ǰ,ֵйC1,C2,...,Ck,Vһ(u1,u2,...,uk,v)ʾC1,C2,...,CkֵΪu1,u2,...,ukʱʽֵΪv޸ĺ󣬱ΪӦ飬¼Էǿɾһѡ.⣬ÿk+1άW¼޸ĺֵս.ÿ㻹kάFlag,CHILDi.S1<>Flagi=1,Flagi=0.֪ѡCHILDiķǿɾFlagiжϸ÷ǿɾS0ݻS1.
ǽREVISION1(2.2)(2.3)иĽõ㷨.
㷨. REVISION2.
: ǿҿ֪ʶT={f1,f2,...,fn}֪ʶp
: Twidp
Step1.
(1.1) T{p}Լͼ.
(1.2) pΪͼеһĽ㣬 Twidp=T{p},㷨.
(1.3) pڷ֧,㷨޷¡,㷨.
(1.4) pΪУֵ.
Step2.
pΪУԵ(֤ĳʱӽѴ)ÿNODE:
(2.1) NODEΪҶ:
P=0ʱV=0S0={NODE}S1=;
P=1ʱV=0S1={NODE}S0=.
(2.2) NODEΪм㣺
(2.2.1) /*޸ֵ*/
NODEֵиVֵȡ(1001).
NODEӵÿӽ(ӽֱCHILD1CHILD2...CHILDkNODECHILDiĹCi)
CHILDi.S0=CHILDi.S1=,/* 㣬ɾ */
NODEֵиCiֵȫ0
Flagi=0;
ֻCHILDi.S0<>,/* CiΪ0ʱзǿɾ */
NODEֵиCiֵȡ(10,01)
Flagi=0;
ֻCHILDi.S1<>,/* CiΪ1ʱзǿɾ */
Flagi=1.
(2.2.2) /* ɾ */
NODEP=0:
/*  Сϣ 󲢼 ɾ */
 ֻҪڹC1,C2,...,Ck,V,,ҦĦ=,򽫦ɾ,СΪλ.
 ʣλ,K+1ά,W.
 NODE.S0=
i=1k/* W1ݡWkݶӦɾ */
Wi=1NODE.S0=NODE.S0ݡCHILIi.SFlayiݣ
Wk+1=1/* Wk+1ݶӦNODEɾ */
NODE.S0=NODE.S0ݡ{NODE}
P=1ͬĲ,ɵNODE.S1.
(2.3) NODEΪ:
(2.3.1) ͬ(2.2.1)
(2.3.2) ɾNODEV=1ʣ,
/* ɾֵ޸ǰV=0֤(֪ʶp)Ϊ */
 ֻҪڹC1,C2,...,Ck,V,,ҦĦ=,򽫦ɾ,СΪλ.
 ʣλ,K+1ά,W.
 U=
i=1k/* W1ݡWkݶӦɾ */
Wi=1,  U=UCHILDi.SFlagiݣ.
Step3.
Twidp=(T-U){p}(TɾUйʽ,ټp).
T{p}ɱʾΪνṹ,pΪУӽ˳޹صģ˸Ψһȷ.㷨ԵϵḶ́Ҷ㿪ʼɾõɾ.Ҷɾɸݹʽֱжϣɾɾʱ,˹ȡֵɾڣһҵ.ˣpΪУһȷҵɾõTwidp.㷨ȷԼɴ˵õ֤.
2.4 㷨
ǷREVISION2ʱ临.TnʽTеĹʽpĳгϽr.
ҳʽĹO(r2)ʱ䣬(1.1)ҪҳʽĹȷͼıߣO(n2r2)ʱ䣻(1.2)O(1)ʱ䣻(1.3)жǷȦ㷨eߵͼΪO(e)8.˴ʽrߣͼn(n+1)r/2ߣ,(1.3)O(n2r)ʱ䣻ڹʽгϽ磬ԼһֵʱгϽ磬(1.4)O(n)ʱ.,Step1O(n2)ʱ.
(2.1)O(1)ʱ.ڹʽгϽ磬ֵСгϽ磬(2.2.1)Ҫ޸ֵO(1)ʱ䣻(2.2.2)Ģٺ͢ҲǶֵĴO(1)ʱ䣻(2.2.2)Ģ۲NODE.Sм빫ʽNODE.Snʽ,,(2.2.2)ĢO(n)ʱ.(2.2)O(n)ʱ.ͬ(2.3)ҲO(n)ʱ.ˣStep2ѭO(n)ʱ䣬ѭn+1ιO(n2)ʱ.
T-UҪnԪصļмȥnԪأO(n2)ʱ,ټpO(1)ʱ䣬,Step3O(n2)ʱ.
㷨REVISION2ʱ临ΪO(n2).ǣɵõ¶.
. Կ֪ʶTͿ֪ʶpT{p}ԼͼΪͣйʽȾгϽʱO(n2)ʱTwidp.
3 
ĸһ֪ʶĶʽʱ㷨.㷨֪ʶṹйأʺ֪ʶ֪ʶϵɢ·ͻģ͵ҽϵͳ6.㷨һּµ㷨֪ʶµĸ֪ʶĽṹأΪ̽⸴ԴһѰʵѽṩ.⣬ף7нͽṹΪͽṹļ֧£㷨ҵ㷺Ӧ.
ĿоõȻѧ͹863߿ƼĿ.
߼飺ܺ,1938,ڣʿʦ,ҪоΪ㷨,˹.
ѩ,Ů1969,ʿ,ʦ,ҪоΪ֪ʶ.
ߵλɽѧѧϵ  250100
E-mail: xuehongtao@hotmail.com
ͨѶϵ:ܺ250100,ɽѧѧϵ
ο
1 Eiter T, Gottlob G. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, 1992,57(23):227270
2 ܺѩ.֪ʶµо.ѧ1995,21(3):3236
(Ma Shao-han, Tao Xue-hong. Research on knowledge base revision. Computer Science, 1995,21(3):3236)
3 ܺѩ죬ΰ.һ֪ʶĸ㷨.о뷢չ,199633(2):127131
(Ma Shao-han, Tao Xue-hong, Sun Wei. A knowledge base revision algorithm. Computer Research and Development, 1996,33(2):127131)
4 ѩ,ΰܺ.֪ʶµ㷨临.ѧ19967(5):300305
(Tao Xue-hong, Sun Wei, Ma Shao-han.Knowledge base revision algorithm and complexity. Journal of Software, 1996,7(5):300305)
5 Dechter Rina, Pearl Judea. Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 1988,34(1):138
6 Dechter Rina, Dechter Avi. Structure-driven algorithms for truth maintenance. Artificial Intelligence, 1996,82(1):120
7 Dechter Rina, Pearl Judea. Tree clustering for constraint networks. Artificial Intelligence, 1989,38(3):353366
8 ܺ.ͼ㷨.磬1988
(Ma Shao-han. Graph Algorithms. Guiyang: Guizhou People's Press, 1988)
1998-05-12յԭ,1998-12-14յ޸ĸ
