Luận án Xây dựng hệ tính toán thông minh xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động

16 CHUaNG 2 M~NG SUY DIEN- TINH TOAN 2.1DANN~P MQttrongnhungva'nd€ hi~nnaydangduQcquailtamcua"Tri Tu~Nhan Tq.o"la nghienCUllcacphuongphapbi€u di~nvaxii'ly tri thuc.Trencos6d6 c6th€ tq.oranhungchuangtrlnh"thongminh" 6 mQtmucdQnaGd6.C6 nhi€u phuongphapbi€u di~ntri thucdil duQcd€ c~pde'nva dil duQCap dl,lllg.Trang chuangfiftychungtaxet de'nmQttruanghQpcuabi€u di~nva xii'ly tri thuctheo ffiq.ngngunghla:"Mq.ngsuydi~nva tinhtoan". Cac ke'tquanghienCUllv€ mo hlnhnaydilduQCtrlnhbaytrongcacbai baa [57],[63],[65]va [67]. Trongnhi~ullnh vlfc lingd1;lngta thuangg~pnhungva'nd~d~tra duoid~ng nhusau:Chungtaphai thlfchi~nnhungtinh loan haysuydi~nra nhungye'uto' dn thie'tnaGd6 tu mOtso'ye'ut6dil duQcbie'ttruoc.D€ giai quye'tva'nd€ nguai taphai v~nd1;lngmQtso'hi€u bie't(tri thuc)naGd6 v~nhunglien h~giUacac' ye'uto'dangduQcxemxet.Nhunglien h~chopheptac6 th€ suyra duQcmQtso' ye'ut6tu giii thie'tdil bie'tmQtso'ye'uto'khac. Duoi day Ia mQtso'vi d1;lminh hQa. Vi du2.1:Giasatadangquailtamde'nmQtso'ye'uto'trongmQtamgiac,ch~ng hq.n: 3cq.nha,b, c;3 g6ctuonglingvoi 3 cq.nh: a, ~,y;3 duangcaDtuong ling:ha,hb,hc;di~ntichS cuatamgiac;naachuvip cuatamgiac;bankinh duangtronnQitie'pr cuatamgiac.Giua 12ye'uto'trenc6 caccongthucth€ hi~nnhungm6i quailh~giupchungtac6 th€ giiii quye'tduQcmQtsO'va'nd~ tinhloand~tfa. Trangtamgiac c6 th€ k€ ra mQtsO'quailh~duoidq.ngcong thucsailday: . Lienh~giua3g6c: a+~+y=1t (radian). <' 17 . Dinh 1ycosin: a2=b2+C2 - 2.b.c.cosa;b2=a2+C2 - 2.a.c.cos~; 2 2 2 C =a +b - 2.a.b.cosy a b c ~. ~=~ . Dinh 1ySin: sina =sinfJ; SillY =sinfJ' sina SillY . Lienh~giuantl'achuviva3q.nh: 2.p=a +b +c . C6ngthlictinhdi~nrichtheo3 c<;tnh(congthlicHeron): S =.Jp(p - a)(p- b)(p- c) . MQts6c6ngthlictinhdi~nrich: S=a.hal2;S =b.hJ2; S =c.hc/2;S=p.r D6i voi bai roangiclitamgiacvoi 12ye'ut6ducjcxemxet,ne'uxetcacd~tinh di~nrichtamgiacvoi 3 ye'ut6duQcchotruocthl s6bai roanC1J.th€ 1ende'n: c:z =220;do1achuak€ de'nnhungyelldu tinhroancacye'ut6khacnua,va nhuthe's6bai roantinhrasera'tIOn.Ne'unhulingvoi m6ibai roantacaid~t mQtthu~tgiai d€ giai quye'tthl khongth€ cha'pnh~nduQc.Tuy nhien co th€ tha'yding m~cdli co quanhi~ubai roanct,lth€ khacnhaunhungd€ giai quye't. chungtachi c~nap d1J.ngmQts6congthucnaGdotrongs6 cacc6ngthucth€ hi~nnhungquailh~giuacacye'ut6dangducjcxemxet.Ne'uchungtacocach d€ bi€u di€n va xii'1ycacye'ut6 va cacquailh~giua cac ye'ut6 thl co th€ tim mQts6thu~tgiai cai d~tduQcd€ giai cacbai toanmQtcachhi~uqua. Vi du 2.2:MQtv~tth€ co kh6i1uQngmchuy€n dQngth£ngvoi giat6ckhong thayd6i1aa trongmQtkhoangthaigiantinhtuthaidi€m tl de'nthaidi€m t2. V~nt6cband~ucuav~tth€ la VI, v~nt6c (] thai di€m cu6i 1aVb va v~nt6c trungbinh1av. Khoangcachgiuadi€m d~uva di€m cu6i1a~s.Ltfc tacdQng cuachuy€ndQng1af. DQbie'nthienv~nt6cgiua2 thaidi€m Ia ~v,vadQ bie'nthienthai gian1a~t.Ngoaira con co mQts6 ye'ut6 khacnuacua chuy€n dQngv~tth€ co th€ duQcquailtam.Tudngttfnhutrongvi d1J.2.1,d€ 18 giainhungbaitmlnv€ ehuy€ndQngfiftychungtaphaisad\lngmQts6e6ng thlielienh~giuacacy€u t6euaehuy€ndQng,eh£ngh~nnhu': f =m * a; I1v=a*l1t; I1s =v*I1t; 2*v =VI +Vz; I1v=Vz- VI; I1t=tz-t]; Vi du 2.3:TranghoahQcchungtathu'ongphai sa d\lngcaephanlinghoahQed€ di€u che'caecha'tfiftytli'caecha'tkhac. Lo~i va'nd€ fiftyeiingehota mQt d~ngtu'dngtl;inhu'trang2 vi d\l tren : Cho tnrocmQts6 eha'thoahQe,haytlm cachdi€u eh€ ra mQthaymQts6cha'tnaGdo. Noi toml~i,co nhi€u va'nd€ trangcaelInhvl;ielingd\lngkhaenhaud~tra du'oid~ngmQt"m~ng"caey€u t6,trongdo cacye'ut6 co nhungm6ilienh~ (hayquailh~)ehopheptaco th€ suyra du'ejemQts6y€u t6 fiftytumQts6ye'ut6 khae.M6 hlnhm~ngsuydi~nva tinhtoanla mQtsl;ikhai quatehomQtd~ngtri thliedungehovi~ebi€u di~ntri thlieva thi€t k€ caeehu'dngtrlnhgiaitoantlf dQng,ch£ngh~nnhu'chu'dngtrlnhgiaicaelOpbai toantu'dngtl;inhu'trongcaevi d\ltren. :;:;: , , ,,' JI: ? 2.2M~NGSUY DIEN VA CAC VAN DE CO BAN Trangm\lefiftychungtaxetmQtm~ngsuydi~ng6mmQtt~phQpcaebie'n eungvoimQt?Pcaequailh~suydi~ngiuacacbi€n. Tranglingdl;lllge1,lth€ m6i bi€n va giatrieuano thu'onga:nli€n voimQtkhaini~me\lth€ v~slfv~t,m6i quailh~th€ hi~nmQtsl;itrithliev€ sl;iv~t. 2.2.1 Quanh~valu~tsuydi~n ChoM ={XI,XZ,...,xm}1a Qtt~phejpcaebi€n co th€ la'ygiatri trongcae mi€n xacdinhtu'dnglingD].Dz,...,Dm.D6i vdi m6iquanh~R c D]xDzx...xDm trencae t~phQpDl,Dz,...,Dmta noi r~ngquail h~fifty lien ke'tcaebi€n x],xz,...,Xm,vaky hi~u1aR(x],xz,...,xm)hayva:ndt la R(Xl.(kyhi~ux dungd€ 19 chibQbie'n<XhX2,...,Xm». Ta sexetcaequailh~R(x)xacdinhmQt(haymQt s6)anhx~: fR,u,v: Du~ Dv, trangdoU,vla caebQbie'nvau c x, vc x; Duva Dvla tichcuacacmi~nxac dinhtu'dngling cuacacbie'ntrangu vatrangv. Quanh~nhu'the'duQcgQila quanhf suyddn. Co th€ tha'yr~ngquailh~suydi€n R(x) co th€ du'Qcbi€u di€n bdimQt(haymQts6) anhx~fR,u,voi u u v =x, va ta vie't fR,u,v:u ~ v, hay vantatIa f: u~ v. Cachky hi~utrenbaahamy nghlanhula mQtIUtJtsuyddn: tacoth€ xacdinh haysuyraduQccacbie'nthuQcvkhibie'tduQccacbie'nthuQcu.Trangph~nsail taxetcacquailh~xacdinhcaclu~tsuydi€n co d~ng: f:u~v, trangdoun v =0 (t~pding).Ngoaifa,trongtruonghQpc~nnoira tavie'tu(f) thaychou, v(t)thaychov. Ta gQimQtquailh~la quanhf d6'ixungco h~ng (rank)b~ngmQts6nguyendudngk khiquailh~do giupta co th€ tinhduQcK bie'nba'tky tum-kbie'nkia(ddayx la bQg6mm bie'n<XhX2,"',Xm». 86i voi ::acquailh~khongph:iiIa d6ixungcoh~ngk, khonglamma'tinht6ngquat,ta ::0th€ giasaquailh~xacdinhduynha'tmQtlu~tf voit~pbie'nvaGla u(f)vat~p~ Jie'nra la vet);tagQilo~iquailh~n~ylaquailh~khongd6ixungxacdinhmQt u~td§:n,haygQivantatla quanhf kh6ngd6'ixung. ~h~nxet: MQtquailh~khongd6ixungh~ngk co th€ duQcvie'tthanhk quailh~ chongd6ixungco h~ng1.Ne'ubi€u di€n mQtquailh~d6i xungco h~ngk hanhcacquailh~d6ixungcoh~ngla I thls6quailh~coh~ngI b~ng: C m-k C km =mm m Du'oidayla mQtvai vi dl,lv~cacquailh~suydi€n. " 20 Vi du 2.4:quailh<%f giua3 goeA, B, C trongtamgiaeABC ehobdih<%thue: A+B+C=180 (donvt:dQ) Quanh<%f giua 3 goetrongmQttamgiae lIen day 1ftmQtquailh<%d6i xungco h~ng1.Quanh<%ngybaahftm3 lu~tsuydi~n: A, B =>C A, C =>B C, B =>A Vi du 2.5:quailh<%f giuamh ehuvi p voi caedQdftieila3 e~nha,b, e: 2*p=a+b +e Vi du 2.6: quail h<%f giua n bittn Xl, X2,..., Xn duQeehoduoi d~ngmQth<%phuong trlnh tuyttntinh co nghi<%m.Trong truong hQp ngy f 1ftmQtquail h<%co h~ngk b~ngh~ngeuamatr~nh<%so'eilah<%phuongtrinh. 2.2.2 M~ngsuydi~n Tli SvtrlnhbftylIentacoth~neulendtnhnghiahlnhthueehom~ngsuydi~n nhusau: - Dinh nghia2.1:Ta gQimQtmc;mgsuydiln, vitttt~t1ftMSD, 1ftmQtea'utrue (M,F) g6m2 t~phQP: (1) M ={xj,xi,...,xn},1ftt~phQpcaethuQctinhhaycaeyttut61a'ygia tIt trong caemi~nxaedtnhnftodo. (2)F ={f1,f2,...,fm},1ftt~phQpcaelu~tsuydi~ncod~ng: f :u(f)~ v(f) trongdou(f) vftv(f) 1ftcaet~phQpconkhaer6ngeilaM saGeho u(f)n v(f)=0. B6i voi m6i f E F, taky hi<%uM(f) 1ftt~pcae bittnco lien h<%trongquailh<%f, nghia1ftM(f) =u(f)u v(f). " 21 Nh~nxetdng mQtm~ng(M,R) voi R la mQtt~pcacquailht%suy di@nclingco th€ duqcxemnhuffiQtffi~ngsuydi@nbangcachthayt~pR boi t~pF g6mta'tca caclu~tsuydi@nxac dinhboi cacquailht%suydi@n. Vi du2.7: Trangvi d\l2.40 tren,taco M(t) ={A,B,C}. Trangvid\l2.50tren,taco M(t)={a,b,c,p}. Trongvi d\l 2.60 tIeD,taco M(t) ={XI,Xz,...,xn}' Vi du 2.8: M~ngsuy di@nchomQthlnhchii'nh~t.Vit%ctinhtoaDtIeDffiQthlnh chii'nh~tlienquailde'nffiQts6ye'ut6cuahlnhchii'nh~tnhusail : bI, bz:haic~nhcuahlnhchii'nh~t; d : duongcheocuahlnhchITnh~t; S : dit%ntichcuahlnhchITnh~t; p :chuvi cuahlnhchii'nh~t; trongdo m6ibie'nd~uco gia tq thuQct~pcac s6 thvcduong.Giii'acac bie'n ta dabie'tcocacquailht%tinhtoaDsailday: V~ mi;itsuylu~n,cac quailht%n:iy d~uco th€ xemla cac quailht%suydi@nd6i xlingco h~ngla 1.Nhu v~yt~pbie'nva t~pquailht%cuaffi~ngn:iy la : M ={bI,bz,d, s,p}, R= {fI.fz,f3}. M~ng(M,R) n:iytuongling vOimqngsuydi@n(M, F) voi F la t~pcaclu~tsuy di@nsailday: bI. bz~ S S,bz~ bI " fl: S =bI * bz; fz: p =2 * (bl +bz); f3: dz z b Z.=bI + Z,. 22 S, bl =>b2 bJ, b2=>P p, b2=>bl p, bl =>b2 b), b2=>d d, b2=>bI d, bI =>b2 2.2.3 Caeva'nd~edbantrenm~ngsuydi~n ChoffiQtffi'.lngsuydi€n (M,F)voiM lat~pcacthuQctinh(haycacbie'n)vaF la t~pcacquailh~suydi€n haycaclu~tsuydi€n. Gia su c6 ffiQtt~pbie'nA eM dfi duQcxac dinh(tucla t~pg6fficacbie'ndfi bie'ttruoc),va B Ia ffiQtt~pbie'n bit ky trongM. . Va-nd~1:C6 th€ xacdinhduQc(haysuyfa) t~pB tut~pA nhocacquailh~ trongF haykh6ng?N6i cachkhac,tac6 th€ tinh duQcgia tri cua cac bie'n thuQcB voi giii thie'tdfibie'tgia tri cuacacbie'nthuQcA haykh6ng? . Va-nd~2:Ne'ucoth€ suyraduQcB tuA thlquatrlnhsuydi€n nhuthe'naG? TrangtruonghQpconhi~ucachsuydi€n khacnhauthlcachsuydi€n naGla t6tnha-t? . Va-nd~3: Trong truonghQpkh6ngth€ xac dinh duQcB, thl dn cho them di~uki~ngi d€ c6th€ xacdinhduQcB. Bai roanxacdinhB tuA trenffi'.lngsuydi€n (M,F) duQcvie'tduoi d'.lng: A~B trongd6 A duQcgQila giii thie't,B duQcgQila ffi\lCtieu(hayt~pbie'ncftnxac dinh)cuabairoan.TruonghQpt~pB chig6mco ffiQtphftntu b,tavie'tviintiit bairoantrenla:A ~ b. " 23 Vi<$ctlmWi giiii chobeiiloanleitlmramQtdayquailh<$guydi~nd€ co th€ ap d1;1ngguyra duQcB tu A. f)i~unffyclingco nghla leitlm ra duQcmQtquatrlnh Hnhloan hay guydi~nd€ giiii beiiloan. Trang vi<$ctlm Wi giiii cho beiiloan chungta cffnxet ffiQtday cac quailh<$suy di~nhay cac lu~tguydi~nneiodo xemco th€ suyra duQccacbie'ntumQtt~pbie'nchotrUDCnhodayquailh<$guy di~nnffyhaykh6ng.Tit dochungtaco d!nhnghlasauday. - Dinhnghia2.2:Giii sa(M,F)la mQtm(;lnguydi~nveiA leimQt~pconcua M. MQtlu?tguydi~nu~ v duQcduQcgQileiapd1;1ngduQctrenA khiucA. MQt quailh<$guydi~nduQcgQila ap d1;1ngduQctrenA khi no xac d!nhmQt lu?t guydi~napd\lngcluQctrenA. ChoD = {f\, f2, ..., fd leimQtday cac quailh<$guydi~n(haylu~tguydi~n)cuaffi(;lngguydi~n(M,F), tanoi dayD leicipdlringdU:(Jctrent?PA khi veichi khi ta co th€ lffnluQtapd\lngduQccac quailh<$f" f2,..., fkxua'tphattitgiii thie'tA. Trang d!nhnghlatren, d?t : Ao =A, Al =Ao U M(fI), . . . , Ak =Ak-I U M(fk), vei ky hi<$uAk leiD(A). TrangtruonghQpD leimQtday lu?t guydi~ntuyytav§nky. hi<$uD(A) leit?P bie'nd(;ltduQckhi lffn luQtap d\lngcac quailh<$trongday D (ne'uduQc).Co th€ n6i dingD(A) leisl,l'mdrQngcuat?PA nhoapd\lngdayquail h<$D. ~ ThuattmintinhD(A) : Nhap:M(;lng uydi~n(M,F), A eM, daycac quailh<$guydi~nD ={ft.f1,...,fm}. Xua't: D(A). Thuatloan: 1.A' f- A; 2. for i=l to m do 24 if fj apdt,lilgduQctrenA' then A' +- A' U M(fj); 3. D(A) +- A' - Dinhnghia2.3:Ta noir~ngmQtdaycacquailh~suydi~nD ={fl, f2,...,fd c F IamQt[O'igidi cuab~litminA --+ B ne"unhutaIftnluQtap dl,lilgcacquail h~fj (i=l,...,k)xua'tphattugiathie"tA thlsesuyraduQccacbie"nthuQcB. NoicachkhacD lamQtWigiaicuabaitoankhiD(A)::)B.BaitoanA --+B duQcgQiIa gidi dl1r;fckhi nocomQtWi giai. Loi giai {fI, f2, ...,fd duQcgQila [iJi gidi t6'tne"ukhongthSbo botmQtsf) buocHnhtoantrongquatrlnhgiai,tilcla khongthSbobotmQtsf)quailh~ trongloi giai.Loi giaiduQcgQila mQt[O'igidingdnnh6tkhi noco sf)buoc suydi~ntha'pnha't,tilc la sf)quailh~suydi~napdt;lilgtrangsuydi~nla it nha't. , , ? 2.3TIM LaI GIAI Xetbai toanA --+ B trenm~lllgsuydi~n(M,F).Trangmt,lcfiftychungtase trlnhbaycachgiai quye"tcacva'nd~cdbansailday: - KhaosatHnhgiaiduQCcuabaitoansuydi~n. - TimmQtlOigiiiit6tchobaitoansuydi~nvaphantfchquatrlnhsuydi~n. 2.3.1Tinhgiaidu'Q'cuabaitoaD Trangmt,lcfiftychungtaneuleu mQtkhaini~mco lienquailde"nHnhgiai duQcuabaitoan:baadongcuamQt~phQpbie"ntrenmQtm<;lngsuydi~n. - Dinhnghla2.4:Chom<;lngsuydi~n(M,F),vaA la mQtt~pconcuaM. Co thStha'ydug co duynha'tmQt~phQpB IOnnha'tc M saochobaitoanA--+B la giaiduQc,va~phQpB fiftyduQcgQila baadongcuaA trenm<;lng(M,F). MQtcachtIVcquail,cothSnoibaadongcuaA la st;!'mdrgngt6idacuaA" 25 trenrnZlngsuydi~n(M,F). K1'hi~ubaadongcua A 1aA, taco th€ k.i€m tra d~dangcactinhcha'tlienquandSnbaadongtrongrn~nhd~du'oiday. I Menhd~2.1.ChoA vaB 1ahai~pconcuaM. Ta c6: I I I I I I (1) A -::J A. ~ - (2) A =A. (3) AcB=>AcB - -- (4) AIIB c AIIB - -- (5) AuB~AuB D5i vOi tinhgi,Hdu'<Jccuabaitoan,taco th€ d~dangk.i€rnchungrn~nhd~sail: Menh d~2.2. (1) Bai toan A -+ B 1aghii du'<Jckhi va chI khi cac bai toanA -+ b 1agiai du'<Jcvoi mQib E B. (2) NSu A -+ B va B -+ C 1acac bai toan giai du'<Jcthl bai toan A -+ C cling giai du'<Jc.Hdn mIa,nSu {fJ, f2,..., fm}va {gJ, gz, ..., gp}1ftn1u'<Jt1aWi giaicuabaitoanA -+B va bai toanB -+ C thl {fJ, fz, ..., fm,gl, gz,...,gp, }1am<)tWi giai cuabai toanA -+C. (3) NSu bai toanA -+ B 1agiai du'QCva B' 1arn<)tt~pcon cuaB thl A -+B' cling1arn<)Jbai toangiai du'<Jc.HdnmIa,nSu {fJ,fz, ...,fm}1arn<)tWi giai cuabai toanA -+B thldocling1am<)tWi giai cuabai toanA -+B'. , Tli khaini~mbaadongdanoid trentaclingco cacdinh11'sail: Dinh Iv 2.1Tren rn<)trnZlngsuydi~n(M,F), bai toanA -+ B 1agiai du'<Jckhi va chIkhi B cA. Tli dinh11'fifty,ta co th€ k.i€m ITatinhgiai du'<Jcuabai toanA -+ B bang eachtlmbaadongcuat~pA r6i xetxemB co baa hamtrongA haykh6ng. Menh d~2.3: Chorn..., fd c F, A c M. D~t: " 26 Ao = A, Al = Ao U M(fl), ..., Ak = Ak-I U M(fk). Ta c6 cacdi~usauday1a tu'angduang: (1)DayD apduQctrenA. (2)Voi ffiQii=l, ...,k taco: Card(M(fi) \ Ai-I) ~ r(fi) ne'u fi Ia quailht%d6i xung, M(fi) \ Ai-I C veri) ne'u fj 1aquail ht%kh6ng d6i xung. (ky hit%uCard(X) chi so'phftntacuat~pX). Ghi chu: D1.;(avao ffit%nhd~2.3 ta c6 ffiQtthu~tloan d~ki~ffitfa tinhap d\lng duqc cua ffiQtday quail ht%D tIeD ffiQtt~pbie'nA. Dinh If 2.2Tren ffiQtffi?ngsuydi€n (M,F), gia sa A, B la hait~pconcuaM. Ta co cacdi~usauday1awangQuang: (1) BcA. (2) C6 ffiQtday quail ht%D ={fI, f2,...,fd c F thoacacdi€u kit%n: (a)D apd\lngduQctfenA. (b)D(A) ::)B. Chungffiinh: Gia sa c6 (1),tuc 1aB cA. Khi d6 bai loan A ~ B 1agiai duQc. Do d6 c6 ffiQtdayquailht%{fI, f2,..., fd c F saochokhi ta1ftn1uQtapd\lngcac quailht%fj (i=I,...,k)xua'tphattir gia thie'tA thl se tinhduQccacbie'nthuQcB. D€ dangtha'yf~ngday {fbf2,...,fd fiftythoa cacdi€u kit%n(2). Dao l?i, gia sac6 (2).Voi cacdi€u kit%nc6 duQcbdi (2)tatha'y{fj}1aWi giai cuava'nd~Ai-I ~ Ai, voi ffiQi i =1,2,...,k. Tir ffit%nhd~3.2suyfa bai loan Ao~ Ak 1agiai duQc.Do d6bai loanA ~ B cling giai duQc,suyfa B c A theo dinhly 2.1. Nhanxet : - dayquailht%{ft.f2,...,fd trongdinh1ytren1affiQtWi giai cuabai loanA ~ B trenffi?ng(M,F). " 27 - TrangWigiiii {it.f2,...,fd tacoth€ be)botnhungfi naomaM(fDc Di-I(A), voi Di-I={it.f2,...,ii-d. Dudidayla thu~troanrhophepxacdinhbaodongcuat~phejpA c M. Trang thu~troann~ychungtathii'apd\lllgcacquanht%f E F d€ timd~nnhungbiEn thuQcM co th€ suyra duejctirA; cu6irungseduejcbaodongcuaA. Thuattmin2.1 timbaodongcuat~pA eM: Nhap: Xua't:A M,;mgtinhroan(M,F),.A eM. Thuatroan: 1. B *- A; 2. Repeat B1*- B; for f E F do if (f d6ixung and Card(M(f) \ B) ::;;r(f)) or ( f khongd6ixung and M(f) \ B c v(f)) then begin " B ~ B u M(t); F ~ F \ {f}; II lo~if khoi leinxemxetsau end; Until B =Bl; 3.A *- B; Gillchti : Trendaytad8:neutend?ctru'ngrho tinhgiiiiduejc uabai roantren ffiQtm?ngsuydi6nvachIrathu~troand€ ki€m ITakhinaobairoanla giiiiduejc. Ngoaira chungtase conneutencachd€ ki€m dinhgiii thi€t cuabai roand€ trongtru'onghejpbai roanchuadugiiithiEtcoth€ b6sungthemnEuduejc. " 28 t3.2 LOighHcuabftitmin (j trentadaneulen cachxacdinhtinhgiaidu'Qcuabai to<ln.Tie'pthea,ta ;etrlnhbaycach!lmraWigiiiichobaitoanA -+B trenm<;lngsuydi~n(M, F). [ru'oche'ttu nhc1inxet saDdinh ly 2.2 ta co m<%nhd6 saDday: vH~nhd~2.4:Day quail h<%suy di~nD la mN Wi giai cua bai to<lnA -+ B khi va chi khiD apdvngdu'QctrenA vaD(A) :J B. )0 m<%nhd6 tren, d€ t1mmQtloi giai ta co th€ lam nhu'saD:Xua'tphattu gia hie'tA, ta full' ap dvngcacquailh<%d€ ma rQngd~ntc1ipcac bie'ndu'Qcxac dinh du'Qcbie't);va qua trlnhn~yt<;lOra mQtSvIan truy6ntinhxac dinh trentc1ipcac ,ie'nchode'nkhi d<;ltde'ntc1ipbie'nB. Du'oiday la thuc1ittoan!lmmQtWi giai cho ,ai toanA -+B trenm<;lng(M,F). rhuat tmin2.2 TIm mQtWi giai chob?titoanA -+B : Nhap :M<;lngsuydi~n(M, F), tc1ip gia thie'tA c M, tc1ipbie'nc~ntinhB eM. Xua't: loi giai chobai toan A -+B Thuat toan : 1. Solution+-empty;II Solutionfadaycaequanh~seapd~ng~ 2. if B c A then begin Solution_found+-true; II bienSolution_found=true II khibai to<lnla giai du'Qc gotobu'oc4; end else 29 Solution_foundf- false; 3. Repeat Aold f- A; Ch9n ra ffiQt f E F chlia xeffi xet; while not Solution_foundand (ch9nduQcf) do begin if (f c16ixung and 0 <Card (M(f) \ A) ~ r(f)) or (f khongd6ixung and 0::j:.M(f) \ A c v(f)) then begin A f- A u M(f); Solutionf- Solutionu {f}; end; if B c A then Solution_foundf- true; Ch9nraffiQtf E F chliaxemxet; end; {while} Until Solution_foundor (A =Aold); 4. if not Solution_foundthen Bfii tminkhongcoWi giai; else Solutionla ffiQtloi giai; Ghichu: 1.V~sau,khi c~ntrlnhbayquatrlnhgiai (haybfii gi::li)taco th€ xua'tphattu .. Wi giai tlmduQcdlioid~ngmQtdaycacquanht%d€ xay d1;I'ngbaigiai. 30 2.Loi giiii (ne'uco)timdu'Qctrongthu~troantIenchu'achacEi mQtWi giiii t6t.Ta co th@b6 sungthemchothu~troan(j tIenmQtthu~troand@tim mQtWi giiii t6t titmQtloi giiii da bie'tnhu'ngchu'achac1ftt6t.Thu~troan sed1,iatrendinh19du'Qctrinhbftytie'ptheoday. DiDhIf 2.3ChoD={fI,f2,...,fm}1ftmQtWi gi.:licuabftiroanA ~ B. ling voi m6i i=I,...,m d~tDi = {fI. f2, ..., fd, Do = 0. Ta xay d1,ingmQthQcac day con SID'SID-I...,S2,SI cuadayD nhu'sau: Sm=0 ne'uDm-Ia mQtWi giiii, ne'uDm-Ikhong1ftmQtWi giiii,Sm= {rID} Si= Si+I ne'uDi-I U Si+I1ftmQtWi giiii, ne'uDi-I U Si+Ikhong 1ftmQtWi giiii,Si= {fduSi+1 voimQii =ill-I, m-2,...,2,1. Khi dotaco : (1) SmC Sm-IC ...C S2 C SI. (2) Di-I u Si 1ftmQtloi giiiicuabftiroanA ~ B voimQi=m,...,2,1. (3) Ne'uS'i 1ftmQtdayconth~ts1,icuaSi thiDi-IuS' i khongphiii1ftmQt Wi giiii cuabftiroanA ~ B voi mQii. (4) SIlft mQtWi giiii t6tcuabftiroanA -+ B. ~ ' Tit dinh19trentacomQthu~troantimWi giiii t6ttitmQtWi giiii dabie'tsau day: Thuat toaD2.3 TIm mQtWi giiii t6ttitmQtWi giiii dabie't. Nhap:M,;lllgsuydi~n(M,F), Wi giiii {fI.f2,...,fm}cuabftiroanA~ B. Xua't: loi giai t5tchobai roan A ~ B Thuatroan: 1. D +- {fI. f2,...,fm}; " 31 2. for i=rn downto 1 do if D \ {fdla rnQtloi giai then D~D\{fd; 3. D la rnQtWi gi£lit6t. I Trongthu~tmln2.3co sad\lngvi~cki~rntrarnQtdayquailh~co ph£lila Wi I giaihaykhong.Vi~cki~rnITan~yco th~duQctht!chi~nnhothu~tminsailday: .Thuattoan ki~mtra 1mgiai chobai toan : Nhap :M(,mgsuydi€n (M,F), bai toanA~ B, ,. daycacquailh~{fJ, f2,...,fm}. Xua't: thongtinchobie't{fJ,f2,...,fm}coph£lila loi giai cuabaitoanA->B haykhong. Thuat toan: 1. for i=l to rn do if (fj d6i Kung and Card(M(fj) \ A):::;r(fj)) or ( fj khongd6iKung and M(fj) \ A C v(fj)) then A~Au M(fi); 2. if A 0 B then {fJ, f2,...,fm}la Wi giai else {fJ, f2,...,fm}khongla loi giai; dtrentadacornQtthu~toant6ngquatd~funloi gi£lit6tchobai toankhida bie'truckrnQtWi gi£li.Th~tfa, taco th~apd\lngrnQtthu~toankhacd€ tirnrnQt loi gi£lit6ttUrnQtloi gi£libie'ttrudcvdi mucdQtinhtoanit bon.Theo thu~toan n~y,ta l~nhtQtxernxetcacquailh~trongt~ploi giaidabie'tva chQnra cac 32 quailht$d€ du'av~lOmQtWi giai moi saGehotrongWi giai moi n§y khongth€ botra bfftky mQtquailht$naG. Vi du2.9:Bay giOtaxet mQtvi dl,lel,lth€ d€ minhhQaehocaethu~tOaDtren. Cho tamgiaeABC co qnh a va2 goek@la ~,y du'<jcehotru'oe. Hayxaedinh(haysuyfa)Seuatamgiae. D€ HmraWigiaiehobaitOaDtru'oehe'taxetm(;ingsuydi6neuatamgiae. M(;ingsuydi6nn§y g6m: 1.T~pbie'nM ={a,b, e,a, ~,y,ha,hb,he,S, p, R, r, ...}, trongd6 a,b,ela 3 e(;inh;a, ~,y la 3 goetu'dngling voi 3C(;inh;ha,hb,hela 3 du'ongeao;S la dit$ntichtamgiae;p la mYaehuvi; R la bankinh du'ongtrOll ngo(;iitie'ptamgiae;rIa bankinhdu'ongtrOllnQitie'ptamgiae,V.v... 2.Cae quailht$suydi€n th€ hit$nboi caee6ngthliesauday: f1 : f2 : f3 : f4 : f5: f6 : f7 : f8 : f9 : flO : ill : f12 : a +~+y =180 a b--- sina sinfJ c b--- SillY sinfJ a c--- sma smy ,. p=(a+b+e)/2 S =a.ha/ 2 S =b.hb/ 2 S =e.he/ 2 S =a.b.siny/2 S =b.e.sina/ 2 S =c.a.sin~/ 2 S =.Jp(p- a)(p- b)(p- c) " 33 V.V... I Ml,lclieucuabailoanIa suyraS (di~ntichcuatamgiac). I Theod€ bai tacogiii thie'tla:A ={a,p,y},va t~pbie'nc~nxacdinhla B = {S}. r Ap dl,lngthu~tloanrimWi giiii (thu~tloan2.2)se du<;1cmQtloi giiii chobai loan I Ila dayquailh~suydiSnsail: I . {ft.f2,f3,fs,f9}. I Xua'tphattUt~pbie'nA, l~nlu<;1tapdl,lngcacquailh~trangloi giiii taco t~pcac I bie'ndu<;1cxacdinhmarQngd~nde'nkhi S duQcxac dinh: . {a,p,y} fl) {a, p-,-y,a} f2) {a,p,y,a,b} f3) {a,p,y,a,b,c} fs) {a,p,y,a,b,c,p} f9) {a,p,y,a,b,c,p,S}. Co th~nh~ntha'ydng Wi giiii n~ykhongphiii la Wi giiii t6tVIcobuocsuydieD I thua,ch~ngh(;lnla fs.Thu~tloan2.3se lQcra tU Wi giiii trenmQtWi giiii t6tla {ft.f2, f9}: {a,p,y} f'~{a,p,y,a} f2 ~{a,p, I, a, b} f9 ~ {a,p, y, a, b, S}. TheoWi giiii n~y,taco quatrlnhsuydiSnnhusail : r 2.3.3DinhIyv~sriphantfchquatrinhgiai I Xet bai loanA -+ B trenm(;lngsuydieD(M.F). Trangcacml,lctrenda trlnh baymQtsO'phuongphapd~xac dinhtinhgiiii c1U<;1ceuabai loan,timfa mQtWi giiii t6tehobai loan.Trongml,len~ytaneulen ffiQteachxfiyd1,1'ngquatrlnhgiiii tUmQtloi giiii dabie't.B6i voi mQtWi giiii, ra'tco khii DangmQtquailh~naodo d~ntoi vi~etinhloanmQtsO'bie'nthua,tacla caebie'ntinhfa makhongcosa " buoc1: Xac dinh a (apdl,lngf1). buoc2: '( Xac dinh b (apdl,lngf2). buGC3: Xac dinh S (apdl,lngf9). 34 d1;1ngchocacbud'ctinh phia sau.Do do, chungtadn xemxet quatrlnhapd1;1ng cacquailht$trongloi giiii va chitinhroancacbi€n th~t sv cftnthi€t choquatrlnh giiii theoWi giiii. Dinh ly saudaychotamQtsv phanricht~pcac bi€n duQcxac dinhtheoloi giiii va tren cd sd do co th~xay dvngqua trlnh suy diSn d~giiii quy€t bai roan. Dinh If 2.4Cho {fl. f2, ..., fm}la mQtWi giiii t6tchobai roanA --+ B trenmQt mc;tngsuydiSn(M, F). D~t: Ao =A, Ai ={fJ, f2, ..., fd(A), vd'imQi i=l,...,m. Khi docomQtday {Bo,Br. ...,Bm-r.Bm},thoacacdiSukit$nsauday: (1) Bm=B. (2) Bi C Ai , vd'imQi i=O,l,...,m. (3) Vd'imQii=l,...,m,{fdla Wi giiii cuabairoan Bi-I--+Bi nhung kh6ngphiiila WigiiiicuabairoanG --+Bi , trongdo G la mQtt~p can th~tsv myy cuaBi-I. Chungminh:Taxaydvngday {Bo,Br....,Bm-hBm}bangcachd~t:Bm=B, valingvd'im6ii <m, d~t: Bi=(Bi+1 n Ai) u A/ , vd'iAi' la t~pcoit p~ftntli'nha'trongAi \ Bi"!"1saochofi+1apdl:mgduQctrent~p hQp(Bi+1n Ai) u Ai'. Th~tfa,A/ coduQCxacdinhnhusau: A/ =u(fi+l) \ Bi+1 n€u fi+1kh6ng d6i xung, van€u fi+1d6ixungthl Ai' =mQtt~pcang6mmax(O,tDphftnill'cuat~phQp(M(fi+d\Bi+l)n Ai trongdoti=card(M(fi+I»-r(fi+l)- card( M(fi+d n Bi+1 n AD. Voi cachxay dvngnftyta co th~ki€m ITaduQcrangday {Bo,Br. ..., Bm-r.Bm} tboamancacdiSukit$nghitrongdinhly. Ghichu: " 35 (1)Tit dint ly trentacoquatrlnhsuydi~nvaxacdintcacbie'nd~giiiib~iitoan A -+B nhusau: buck 1:tint cacbie'ntrongt~pBI \ Bo (ap dlJngfl). buck2: tint cacbie'ntrongt~pB2\ BI (apdlJngf2). V.v... buckm:tint cacbie'ntrongt~pBm\ Bm-I (apdlJngfm). (2)Tit chungmint cuadint1ytren,tacoth~ghiramQthu~toand~xayd1,1'ng daycact~pbie'n{BI', ...,Bm-I"Bm'}roi nhaudn 1~n1uQtduQcxacdint (hayduQcsuyfa) trongquatrlnhgiiiibaitoan(Bj' =Bi \ Bi-I) g6mcacbuck chinhnhusau: . xacdint cact~pAo,AJ, ...,Am. . xacdint cact~pBm,Bm-],...,BI' Bo. . xacdint cact~pBI', B2',...,Bm'. Vi du2.10:Giii sa taco day{fJ,f2,f3}1amQtWi giiii t6tchobai toanA -+B, trongdo: A ={a],b], b2}, B ={b3}, fI, f2la cacquq.nht$d6ixungcoh,;mg2, f3la quailht$d6i xungco h~ng1,va M(fl) ={ai, bI, CJ,dd, M(f2) ={aJ, CI,bz,d2,e2}, M(f3) ={b],e2,b3}. Dt;1'atheos1,1'phantkh quatrlnhgiiii trongdint ly trentaco : Ao=A, Al ={aJ,bI,b2,CJ,dd, A2= {a],b],bz,CI,dJ, d2,ez}, A3= {aJ,bJ, bz,CJ,dl, d2,ez,b3}, " 36 B3= B, B2= {bI.ez}, B I = {bI.ai, CI.bz}, Bo= {aI.bl, bz}, vacact~pbie'ncgnIgnluqttinhtoantrangb~ligiaichobaitoanla : BI'= {cd, B2'= {e2}, B3'= {b3}. Tudotacoquatrlnhsuydi~ntheoWigiaitrennhusau: :;:::, ,,' " ? ,,' 2.4MANG SUY DIEN CO TRQNG SOVA LO! GIAI TOI u'u Va'nd~taquailtamtrongphgnngy la vit$cfun mQtWi giai t6tnha't(hayWi giait6i u'u).Quannit$mv~Wi giai t6tnha'tphl,lthuQcvao vit$ctaquailtamde'n. ffi\lCtieut6i u'unaod6i voi loi giai.Trongdinhnghia2.3,taquailHimde'nnhung Wigiai voi so'buGCsuydi~nit nha'tmatagQila Wi giai ngftnnha't.Dotinhthutv t6tcuat~phqps6,.t\i'nhientacoth€ tha'yding:ne'ubaitoanA ~ B lagiaiduqc thlse t6nt'.limQtWi giai ngftnnha'tchobai toan.Tuy nhien,trongnhi~utruong hqpapd\lngC\lth€ nhuht$suydi~ntinhtoanhay ht$suydi~ntrencacphanling hoahQc,m6i lu~tsuydi~nco mQtthamso'tudngling d'.lidit$nchodQphuct'.lP cualu~tsuydi~nhaychiphi.Nhungthamso'n~ydongvai traquailtrQngtrong tinhhit$uquacualoi giai.Vi d\l,ne'usosanh2 c6ngthuctinhtoan (1) a +b + C=2*p,va (2)az=b2+CZ-2*b*c*cos(A) Xac dinhCI (apdt,mg[I), Xac dinhez (apdt,mg[2), Xac dinhb3 (apdt,mg[3). 37 d~ehQneongthueehovi~ethlfehi~ntinhroan a thl eongthue(1) t5t hdnVI trongeongthue(1) tachi sa dl,mgcaepheptinh+,- va*; trong khi a eong thue (2)taphaitinhgiatrihamh1qngiaevatinhdin b~ehai.Trangph~nn~ytase xemxetcaem~ngsuydi€n co trQngs5,trongdoungvoim6ilu~tsuydi€n co ffiQtrQngs5 dl1dngtl1dngung,va loi giai t5i l1use dl1qed~e~p de'nrheanghla Iat6ngtrQngs5tha'pnha't.Loi giai ngilnnha'tehinhla Wi giai t5i l1utrongtrl1ong hQptrQngs5euacaclu~td~nd~ula 1.Thu~tgiaiA* la cdsad~tlmramOtloi giait5il1utrongtrl1onghqpbairoanla giaidl1qc. 2.4.1Dinhnghiavakyhi~u - Dinh nghla 2.5: Ta gQi mOtmt;lngsuydiln co trQngso'la mOtmo hlnh (A, D, w)baag6m: (1)mOt~phqpcaethuOctinhA, (2)mOtt~phqpcaclu~tsuydi€n D, va (3)mOthamtrQngs5dl1dngw: D -)- R+ M6i lu~td~nr thuOcD cod~ngr: u~ v,voi uvav lacaet~phqpconkhae r6ngvaroi nhaueuaA. Ta gQiu la ph~ngia thie'teualu~tr va ky hi~ula hypothesis(r).T~pv dl1qegQila ph~nke'tlu~ncualu~tr va ky hi~ula goal(r).T~phqp attr(r) =hypothesis(r)u goal(r) duqegQi Ia t~phqp cac thuOctinhtronglu~tr. M~ngsuydi€n co trQngs5 sedl1qcvie'ttiltla MSDT. Ghitho: . T~phqpD caclu~tsuydi€n co th~vie'tdu'oid~ngmOt~phqpcaequanh~ suydi€n mam6iquanh~suydi€n xacdinhcaclu~tsuydi€n co trQngs5 b~ngnhau. . TrangmOtMSDT (A,D, w)taco(A,D) lamOtMSD. 38 Vi du 2.11:GQi A la t~ph<Jpg6m3 e<;lnheuamQttamgiae (a, b, va c), 3 goe trong(A, B, va C), nth ehuvi p, di«%ntichS, 3 du'ongcaD(ha,hb,va he),va caeye'uto'khaeeuatamgiae: A ={A,B, C, a,b,e,p, S, ha,hb,he,...}. Giii'acaethuQetinhtreneuamQttamgiaetaco caelu~tsuydi€n du'<Jexae dinhboi caequailh«%suydi€n th€ hi«%nboi caeeongthlieli«%tke trongt~p h<Jpsail day: D= { fI: A +B +C = 180; B: b/sin(B)=e/sin(C); f2:a/sin(A)=b/sin(B); f4: a/sin(A)=e/sin(C); fS: 2*p =a +b + e; f6:S=a*ha/2; f8:S=c*hcl2;f7: S =b * hb12; f9:S=sqrt(p*(p-a)*(p-b)*(p-c)); fI1: hb=a*sin(C); fIO: ha=b*sin(C); fI2: he=b*sin(A) }. Giii sacaepheptoan+,-, * va1du'<Jed~tchotrQngs6la 1,pheptinhdin b~e 2 co trQngs6la mQth~ngso'du'ongc1,va caetfnhtoanham1u'<Jnggiaeco trQngs6la mQth~ngso'du'ongc2;trongdocl » 1vac2» 1(el vae21On ,. bon 1nhi~u).Nhu'the'caequailh«%suydi€n co trQngso'tu'onglingnhu'sau: w(fI) =2; w(fS)=3; w(f2) =wen)=w(f4)=2*c2+2; w(f6) =w(f7) =w(f8) =2; w(f9)=el +6; w(fIO)=w(n!) =w(fI2) =e2+ 1; v.v.. . Khi do taco (A, D, w) Ia mQtm'.ingsuydi€n eo trQngso'. - Dinhnghia2.6:Giii sa(A,D, w)la mQtMSDT. ChoS={f"...,fdlamQtday caelu~tsuydi€n va Ala mQtt~ph<Jpde thuQetfnh.B~t ., 39 S leA) =A u goal(fl) =A ne'uhypothesis(fl)c A, ne'unguQc1?i. Si(A) =Si-I(A) u goal(fi) ne'uhypothesis(fD c S i-I(A), =Si-I (A) ne'unguQcl?i. (voi mQi i =2,...,k). S (A) =Sk(A), w(S) =t6ngcuacacw(f),voif ch?ytrenS =w(fl) +w(f2)+ ...+w(fk). Ta gQiw(S)la trQngs6cuaS. ChomQtbairoanA ~ B.Daycaclu~tsuydi€n SduQcgQila mQtWigi:iit6i u'ucuabai roankhi n6thoamancacdi€u ki~nsauday: (1)S la mQtWi giai cuabai roanA ~ B. (2)TrQngs6cuaS nhobonho~cbAngtrQngs6cuaba'tky mQtWi giainao khaccuabai roan.N6i mQtcachkhac la: w(S)=mill{w(S')IS' la mQtlai giaicuabai roanA ~ B } Nhanxet:TrangtruanghQphamtrQngs6la hamhAngthimQtWigiait6iu'u chfnhla mQtlai giai voi s6buocsuydi€n tha'pnha't,tucla lai giainga:nha't. rungc6th€ tha'yrAnglai giait6iu'ukh6ngnha'thie'tla duynha't.N6imQtcach .. ' khac,bai roanc6 th€ c6nhi€u Wi giai t6i u'ukhacnhau.Tuy nhien,chungta thuangchidn rimramQtWigiait6iu'umathai. 2.4.2LOigiiHvadQphuct~pcuaquatrinhfun lOigiai XetbairoanH ~ G trenmQtMSDT (A,D, w),voiH vaG la caet~pconcua t~pthuQctfnhA. Bay cungla mQtbai roantren m?ngsuydi€n (A, D). Tli nhii'ng ke'tquaduQCtrinhbaytrongcacml,lctruoctaco th€ t6mta:tquatrinhrimmQtWi giaitheophudngphapsuydi€n tie'nquathu~tgiai duoiday: 40 ThuattoaD2.4 Bu'oc1:TIm mQtWi giai. Khi G chuabaa hamtrongH ta thvchi<$nqua trlnh l~pcho cacbuoc duoi day: Buoc1.1:TIm lu~trED co th§ ap d1;lngduQcd§ suyra caethuQCtinhmOi, tlicla hypothesis(r)baahamtrongH nhunggoal(r)kh6ngbaahamtrong H. Buoc 1.2:N€u vi<$ctlmki€m d buoc 1.1tha'tb'.li(kh6ngHmduQclu~tr nhu mongmu6n)thlk€t thucvoi k€t quala: bai roankh6ngco Wi giai. Buoc1.3:NguQcl'.lithlb6 sungthemgoal(r)vaoH va ghinh~nr vaodanh sachcaclu~tdffduQcapd1;lng. Bu'oc2:RutgQnWi giai. Gia saS ={rj,..., rp}la mQtWi giai (n€u co) tlmduQctrongbuoc 1.Ta thve hi<$ncaebuoesauday: Buoe2.1:G' +- G\H; Buoe2.2:for k:=pdownto1 do if (goal(rk)~G')then Lo'.lirkrakhoi danhsachS \. else G' +-(G' \ goal(rk))u (hypothesis(rk)\ H) Menh d~ 2.5 Thu~t roan 2.4 eho Wi giai la dung va co dQ phue t'.lP la O(lAl.lDl.min(lAI,IDI) ). Trangcaeeaid?t e1;lth§ taco th§ sa d1;lngthemcaequi tcleheuristicsd§ tang themhi<$uquaehovi<$etImloi gi:H. 2.4.3 TIm 1mgiai t6i du " 41 Trongm1,lcnilytasexemxetva'nd~timWi giait6iu'uchobftiroanH ~ G trenmN MSDT (A, D, w). Cachtie"pc~nde giai quye"tva'nd~nily 1ftdl;latren thu~tgiaiA*.De co theapd1,lngthu~tgiainilychungtacilnco mQtbi€u di~n thichhQpchokhonggiantr<;lngthaicuabftiroanclingnhu'choyell cffucuabfti roan. - }(hong iantrangthaicuabftiroan:XetbftiroanH ~ G tren mQtMSDT (A, D,w).Voim6ilu~tr mfttacoth€ apd1,lngtrenH desuyranhungthuQctinh moi(nghIaIa hypothesis(r)baohftmtrongH nhu'ngoal(r)thlkhongbaahftm trongH) sed~ntoimQtt~pthuQctinhmoiH' =H u goal(r).Ta noirangr Ia mQtet;mhn6i tit dlnhH de"ndlnhH'. Nhu'the",t~phQpg6mta'tca cact~pcon (haydlnh)H' cuaA saochoco mQtdayS g6mcac lu~t(hay c<;lnh)thoaman di~uki~nH' =S(H),clingvoicacc<;lnhtrongcacdaySse chotamQtkhong giantr<;lngthai cua bfti loanco d<;lngd6 tN. Han nua d6 thi nily co trQngso' du'Qcdinhnghlabdi: trQngso'cuac<;lnhr (tuc1ftmQtlu~tsuydi~n)1ftw(r).D6 thico trQngso'nily se du'Qcky hi~u1ftGraph(H~G). Tll'cachxay dl;lngd6thi cuabftiloantaco m~nhd~sailday: Menh d~2.6: (1)MQtdayS g6mcac lu~t1ftmQtloi giaicuabfli loanH ~ G khi vftchikhiSift" , mQtlQtrinhtrend6 thiGraph(H-+G)n6ititH de"nS(H) vftS(H) ~ G. (2)DQdfticuamQtlQ trlnhS trend6 thiGraph(H-+G)1ftw(S), trQngso'cuadanh sachlu~tS trenMSDT (A,D, w). Tll'm~nhd~nily,vi~ctlmWi giai t6i u'uchobfli roanH-+G tu'angdu'angvoi vi~c tlmmQtdu'ongdi ng~nnha'trend6thiGraph(H-+G)tll'H de"nmQtdlnhm1,lclieu H' thoadi~uki~nH' chuaG. D6i voi m6idlnhN trend6thi,di.it heN)=mill {w(r)Ihypothesis(r)eN} 42 tuchl heN)la trQngs6nhanh[{tcuacaclu~tapd\lngdu'QctrenN. GiatriheN) nilyco th€ xemla mQtu'oclu'QngcholQtrlnhtuN de"nffiQtdInhm\lctieu.Tli do chungtaco th€ vie"tthu~tgiaitlmWi giai t6iuuchobai toaDnhu'sail: Thuat toaD2.5 Bu'6c1:Khdi t(;lOtr(;lngthaixu[{tphat. Open~ {H}; II danhsachdInhmdbandiluchIcodInhxu[{tphat Close~ {};II danhsachdInhdong g(R) ~ 0; II dQdai lQtrlnhde"nH la 0 f(R) ~ h(R);11dQdailQtrlnhu'octinhtUH de"nm1;lctieu la h(R) found~ false; II bie"nki€m traquatrlnhHmWi giai Bu'6c2:Th1;l'chi<$nquatrlnhl~p d€ tlmWi giai t6i uu. While (Open:1={})do Begin Bu'oc2.1: ChQnffiQtdInh N trongOpen voi u'octinh du'ongdi f nha nh[{t. Bu'oc2.2:Chuy€n N tudanhsachOpensangdanhsachClose. Bu'oc2.3:if (N la ffiQtm\lctieu)then ,. Begin Found~ true; Break; II Ke"tthucquatrlnhl~p End Bu'oc2.4:else II N kh6ngla ffiQtm1;lctieu Begin Duy<$tquacacdinhke"S cuaN (Wc la co clingr n6i N va S) ma S ~Close,lingvoim6iS taxetcactru'onghQpsail: 1. S ~Open:Tinh g(S)=g(N)+w(r); f(S)=g(S)+h(S); " 43 B6sungS vaoOpen; 2. S E Open: If g(N) +WeT)<g(S)then Begin g(S)+-g(N) +WeT);f(S) +- g(S)+h(S); C~pnh~tthongtinv~dinhke'tntoccuaS tren19tdnh; end End End II Ke'tthucvongl~pwhile Bu'oc3:Ki§m ITake'tquavi~ctlmkie'm. If Found then Ke'tquala tlmduQCWi giai t6i u'uva thie'tl~ploi giai Else Ke'tqualabaitmlnkhongcoWigiai. Menh d~2.7 Thu~ttmln2.5 cho loi giai la dungva co d9 phuct~p O(1A12.IDI2). Vi du 2.12:Gia sa taco m~ngsuydi€n co trQngsO'(A,D, w) nhusail: A ={A,B, C,a,b,c,p,S,ha,hb,hc}. D ={fl: A +B +C =180; B: b/sin(B)=c/sin(C); ~ f2: a/sin(A)=b/sin(B); f4: a/sin(A)=c/sin(C); f5: 2*p =a +b +c; f6:S=a*ha/2; f8:S=c*hc/2;n: S=b* hb/2; f9: S =sqrt(p*(p-a)*(p-b)*(p-c)); fl1: hb=a*sin(C); flO: ha=b*sin(C); fl2: hc =b*sin(A). }. w(fl) =2; w(f5)=3; w(f2)=wen)=w(f4)=2*c2 + 2; w(f6) =wen) =w(f8) =2; w(f9)=c1+6; w(flO) =w(fl1) =w(fl2)=c2+1. '" 44 Trangdoc1vac2lacach~ngs6dudngvoic1» 1vac2» 1. Xet bai roanH -+G voiH ={a,b,B}va G ={S}.Tren m~ngsuydi€n (A, D), n€u apd\lngthu~troan2.4taco th@tlmduQcmQtWi giai 5 ={f2,fl, n, f5, f9}. Tren m~ngsuydi€n co trQngs6 (A, D, w) Wi giai 5 co trQngs61a w(S)=4*c2+c1+ 15.Ap d\lngthu~troan2.5d@tlmWi giai trenm~ng(A, D, w) taco th@tlmduQcmQtWi giiii t6i u'u5' ={f2,fl, flO, f6}vdi trQngs6 law(5')=3*c2+7. ,.. , ,.. '" '" ?,..~ 2.5T~PH<)PSINH VA VI~C KIEM DfNH, BO SUNGGIA THIET Trongml,lcn~ysexemxetv6svthuahaythi€u d6ivdigiathi€t cuabairoan H -+G trenmQtm~ngsuydi€n (A,D) vatrongtruonghQpc~nthi€t thltlmcach di6uchinhgia thi€t H. Trudch€t tadn xet xembai roanco giai duQchay khong.TruonghQpbairoangiaiduQcthlgiathi€t la duoTuynhiencoth@xayra tlnhtr~ngthuagia thi€t. f)@bi€t duQcbai roanco th~tsv thuagia thi€t hay khong,tacoth@dvavaothu~troantlmffiQtsvthugQngiathi€t sailday: Thuattoan: TImmQtsVthugQngiathie'tcuabairoan. Nhap:M~ngsuydi€n (A,D), Bai roanH-+ G giaiduQc, Xua't: t~pgia thi€t ffidiH' c H t6i ti@uIDeothli tv C. ~ ' Thuat roan: Repeat H'+-H; for x E H do if H - {x}-+G giaiduQcthen H +-H - {x}; Until H =H'; 45 Trangthu~to(lntrenne'ut~pgia thie'tmoiH' th~tst;tbaahamtfongH thlbai roanbi thitagia thie'tva taco th§ bot ra tit gia thie'tH t~phQpcacbie'nkh6ng thuQcH' , coi nhuIa gia thie'tchothita. TruonghQpbairoanH ~ G lakh6nggiaiduQcthltanoigiathie'tH thie'u. Khidocoth§di€u chinhbairoanb~ngnhi€u cachkhacnhaud§ chobairoanla giaiduQc.Ch~ngh~ntacoth€ sadl:lngmQts6phuongansailday: phu'dngan 1: TImmQtA' c M \ (A u B) t6i ti§usaGchobaadongcuat~p hQpA'u A chliaB. phu'dngan2 :Khi phuongan1kh6ngth§tht;tchi~nduQcthltakh6ngth§chI di€u chinhgiathie'tel§chobairoanla giaiduQc.Trangtinthu6ngn~y,ta phaibo botke'tlu~nho~cchuy€n botmQtph~nke'tlu~nsanggiathie'td§ xemxetl~ibairoanrheaphuongan1. Khai ni~mt~phQpsinhvaphuongphapHmmQtt~phQpsinhtrenmQtm~ngsuy di~nla co sd chovi~cphattri§n cac thu~troangiai quye'tva'nd€ ki§m dint gia thie'tcuabairoansuydi~n.HonlllIavi~ckhaosatv€ t~phQpsinhclingIa n1Qt va'nd€ duQcd~tramQteachtt;tnhientrenm~ngsuydi~nnh~mtimfa mQt~p hQpt6i thi§ucacthuQctint va caclu~tsuydi~nsinhfa ta'tca caethuQctint khac. 'I 2.5.1 Khai ni~mt~phQ'psinh - Dinh nghla2.7:Cho (A,D) la mQtm~ngsuy di~n.MQt t~pthuQctint SeA duQcgQila mQttqpht;Jpsinhcuam~ngsuydi~nkhi taco baadongcuaS tren m~nglaA,nghiala S =A. Vi du2.13:Xetm~ngsuydi~n(A,D) voiA ={a,b, c,A, B, C, R, p, S}g6mcac bie'ns6tht;tcduongvaD la t~phQpcaclu~tsuy di~ntuonglingcuacacquail h~suydi~nth§hi~nbdicacc6ngthlicsailday: '" 46 f1:A+B+C=n f2: a/sin(A)=2*R f4: c/sin(C)=2*R0: b/sin(B)=2*R f5: a +b +c =2*p f7: b2=a2 +C2 - 2*a*c*cos(B) f6: a2=b2+C2- 2*b*c*cos(A) f8: C2=b2 + a2- 2*b*a*cos(C) f9:S=sqrt(p*(p-a)*(p-b)*(p-c» M(;mgsuydi~nnfiyco mQtt~phqpsinhla T ={a,A, B}vatuT tasuyraduqcD nhocaclu~tsuydi~nsail: A, a ::::>R; A, B ::::>C; R, C ::::>c; R, B ::::>b; a, b, c ::::>p; a, b, c, p ::::>S Tli dinhnghlav~t~phqpsinh(j trentacocactinhchitsail: (1)Ne'uS IamQtt~phqpsinhtrongmQtm~ngsuydi~nvaSeT thiT cfingla mQt~phqpsinh. (2)Ne'uS Ia mQtt~ph<;1psinhtrongm~ngsuydi~n(A, D) vaD' la mQtt~p hqpmC1rQngcuaD, nghlala D cD', thi taclingcoS la mQtt~ph<;1psinh cuam?ngsuydi~n(A, D'). Hi6nnhienlam6im~ngsuydi~nd~ucot~ph<;1psinh.Vin d~machungtaseo . khaosatIii timmQtt~phqpsinh. 2.5.2 TIm t~P hQ'psinh Trongmt,lcnfi¥se trinhbaycachtimmQt~p hqpsinhkh6ngtfimthuongvoi s6phfintUcangit cangt6tcuam~ngsuydi~n.Truoche't,taco th6timmQtt~p hqpsinhb~ngphuongphapthtl'dfinduqcth6hi~nbC1ithu~toansailday: Thudt tmin2.6:TIm mQtt~phqpsinhStrong m?ngsuydi~n(A,D). Buoc1:S +- {} II B~tchoSband~ula r6ng Bu'oc2:Tinh baadongClosure(S)cua~p h<;1pS. Bu'oc3:Ki6m ITasosanhClosure(S)vaA. If Closure(S)=A then Ke'tthuc .. 47 Else Begin ChQnffiQtphffntiYx E A-S; S +- S u {x}; QuayI?i Bu'ac2; End Thu?t tmin nffy se cho ta mQt t?P hejp sinh vOi dQ phuc t?P O(1A12.IDl.min(lAI,IDI)),dodQphuct?P cuapheploant?PhejplIen cact?Phejp thuQctinhcuaA la O(IAI)vadQphuct?Peuathu?tloantimbaodongeuamQt t~phejptrenm?ngsuydi€n (A,D) la O(lAI.IDl.min(lAI,IDI)). Ta co th€ xay d1;1'ngmQtthu?tloant6thonthu?tloan lIen b~ngeachthie'tI?p ffiQt"bi€u d6 (hay d6 thi)phanea'p"euamQtm?ngsuy di~n.Kh6ng lam ma't tinht6ngquattaco th€ giasll'caelu?t suydi~ncophffnke'tlu?n g6mI phffntit - Dinhnghla2.8:ChomQtm~lllgsuydi€n (A,D) mam6ilu?tsuydi~ncophffn ke'tlu?n g6m I phffntll'.Ta xay d1;1'ngmQtd6 thidinhhuangGraph(A,D) nhu' sail: (1)T?phejpdlnhg6mta'teacaethuQetinhvata'teacaelu?t suydi~n,tuela AuD. (2)Ung vai m6i lu?t r : hypothesis(r)-+ goal(r)ta thie'tI?p mQtt?P hejp ~ ' edges(r)g6m ta'teelcae cling dinh huang (x, r) va (r, y) thoa x E hypothesis(r)va y E goal(r)mQteachtudngling.T?p hejpcaee?nheuad6 thiGraph(A,D) la hejpta'teelcaet?Phejpedges(r)vai r eh?ytrongt?PD. Trangtru'onghejplIen d6thiGraph(A,D) ta co degin(x):::;1vai mQix E A, thl taco th€ hi€u ngffmcaedlnhthuQcD va xetmQtd6 thithugQnGraphD(A) g6m: (1)T?p hejpdlnhla t?PhejpcaethuQetinhA. " 48 (2)T~phQpc~nhg6mta"tcacaccling(x,y)thoamandi~uki~n:Co(duy nha"t)mQtlu~tr saGchogoal(r)=y va x E hypotheis(r). Vi du 2.14:M~ngsuydi~n(A, D) vaiA ={a,b, c, A, B, C, R, p, S} vaD la t?P caelu~tsuydi~nsail: rl: A, a=>R; r2:A, B =>C; r3:R, C =>c; r4:R, B =>b; r5:a,b,c =>p; r6:a,b,c,p ~ S se eo d6thiGraph(A,D) co t~phQpdlnh13 Au D ={a,b, c, A, B, C, R, p, S, rl, r2, r3, r4, r5, r6} vat?PhQpcacclingla {(A,rl), (a,rl), (rl,R), (A,r2), (B,r2),(r2,C), (R,r3),(C,r3),(r3,c),(R,r4),(B,r4),(r4,b), (a,r5),(b,r5),(c,r5),(r5,p), (a,r6),(b,r6),(c,r6),(p,r6),(r6,S)} Trend6thiGraph(A,D)m6ix EA codungmOtclinghuangtai,vad6thithu gQnGraphD(A)cot~pdlnhla A ={a,b, c, A, B, C, R, p, S } va t~P hQpc~nh13 {(A,R),(a,R),(A,C), (B,C), (R,e),(C,c), (R,b), (B,b), (a,p),(b,p),(c,p), (a,S),(b,S),(c,S),(p,S)} ~ . - Dinhnghla2.9:Ta gQimQtd6thidinhhuangddngiankhongcochutrlnhla mOtbiiu d6phancap(haymOtd6thiphanea'p).Blnhx cuad6thimakhong co eunghuangtai seduQcgQila dlnhmuc0, va tavie'tlevel(x)=O.D6ivai caedlnhxkhac,tadinhnghlamOteachquin?pmuccuanovamuccuadlnh nftyco th€ duQcchobdi level(x)=max {level(a)I co clingn6i a vai x} + 1 49 Nhu'the't~ph<Jpdlnheuabi6ud6phanea'pdu'<Jesilpxe'pthanheaeroue,voi mue0 euabi6ud6 la t~ph<Jpta'tea eaedlnhmue0, mue 1 euabi6ud6 la t~p h<Jpta'teaeaedlnhmue1,V.v... Vi du 2.15:D6 thi GraphD(A)trongvi d\12.14,du'<Jeve tronghlnh 2.1, la mQt bi6ud6phanea'pvoi 5 muela: Level0={a,A, B}, nghla13level(a)=level(A) =level(B) =O. Levell ={R, C}, nghla 13leveleR)=level(C) =1. Leveh={e,b},nghlala level(e)=level(b)=2. Leveh={p},nghlala level(p)=3. Leve14={S},nghlala level(S)=4. level4 level3 level2 level1 IDnh 2.1 MQtbi6ud6phanea'pg6m5 roue. Tu caedinhn&hlatrentae6th6d€ dangchungminhcaemt$nhd€ sailday: Menh d~2.8:Cho m~ngsuydi€n (A,D). Gia sa d6 thiGraph(A,D) e6d6thi thu gQnGraphD(A).Khi a'y,ne'uGraphD(A)la mQtd6 thiphanea'pthlt~ph<JpS = Levelog6mta'teacaedlnhmue0 seehotamQtt~ph<Jpsinheuam~ngsuy di€n. Honnii'atrongtru'ongh<Jpn~ytacon e6: (1)S la t~ph<Jpsinhnhanha'trenm~ngsuydi€n. (2)T~pD 13t~ph<Jplu~tt6i thi6ud6Level0sinhraA. N6i mQteachkhae, ne'uD' 13mQtt~ph<Jpconth~tsl!euaD thlS kh6ngphaila t~ph<Jpsinh trenm~ngsuydi€n (A,D'). .. 50 Dinh If 2.5:Cho m~ngsuydi~n(A,D). taco: (1)SeA Ia mQtt~ph<;1psinhtrenm~ngsuy di~nkhi va chi khi co mQtt~p Iu~tD' c D saDchoGraph(A,D') Ia mQtd6th!phanca'pva S chilat~p h<;1pcacdinhmilc0cua06th!ngy. (2)T6n t~imQtt~pIu~tD' cD saDchoGraph(A,D') Ia mQtd6 th!phanca'p. Tli o!nhIy tren ta co th€ tim mQtt~phQpsinhtrenm~ngsuydi~n(A, D) b~ng eachxaydl;fngmQtthu~troantimmQtt~pIu~tD' saDehoGraph(A,D') Ia mQt 06thiphanca'p,va Ia'ycacoinh(jmilc0cuad6th!ngy.Cachlamngyseou'Qc apdvngtrongvi<$etim mQtsl;fb6 sunggiathie'tehobai roansuydi~nmQtMSD trongtrliongh<;1pbai roanthie'ugia thie't.Chungta cling co mQtthu~troannhu' sau: Ihnat tmin 2.7:TIm mQtt~ph<;1psinhS trongm~ngsuy di~n(A, D) b~ngcach xay dl;fngmQtm~ngcon (A', D') voi A' =A va coGraph(A',D') Ia mQtbi€u 06phanea'p. Bu'oe1: A' ~ {}; D' ~ {}; S ~ {}; Bu'oe2:For rED do If not (attr(r)c A') then Thl;fehi<$nvi<$e~pnh~tA', D' va S rhea2 tru'ongh<;1pnhu'sau:, ' . Tru'ongh<;1p1:goaI(r) ~A' S ~ Su (hypothesis(r)-A'); . Tru'ongh<;1p2: goaI(r) E A' Lo~ir' (ne'uco)trongD' ma goal(r')=goal(r); Lo~i mQts6 Iu~tsuyfa cae x E hypothesis(r)o€ baa dam tinhphanea'peuabi€u 06va e~pnh~tS. A' ~A' uattr(r); D' ~D' u {I}; Blioe 3: S ~ S u (A - A'); A' ~ A <i 51 ;Ghichu: . Nh~mhu'ongtoivi~cxacdinhmQt~ph<Jpsinhvois6phfintitnhovavoidQ phuct~pthffptaco th~sud~ngthemcacquitifcheuristicb6sungthemcho quatrmhxaydvngmQtm~ngsuydi€n conmad6thi cuano co d~ngmQt biSud6phanca'p. . Tit phu'ongphaptlmmQtt~phQpsinhtrangmQtm~ngsuydi€n dffdu'Qctrlnh bay(j trentaco thSphattriSnmQtthu~tloantu'ongtv <istlmmQtt~phQp sinhchU'amQt~ph<JpthuQctinhchotru'oc. 2.5.3 B6 sunggiathie"tchobftitoaDsuydi~n Trongm~cnfiytasexemxetvi~cb6sunggiathie'tchobai loanH ~ G tren mQtm~ngsuydi€n (A, D) trongtru'onghQpbai loan kh6ng giai du'<JC.Y tu'dng chinhd day1atie'nhanhmQtquatrlnhxay dt;r'ngmQtbiSu d6 phancffpvoi t~p hQp<iinhchU'aG va u'ulien chovi~cd~tcacphfintit cuaH d mU'cO.Thu~tloan cobandu'oidaychotamQteachd~tlmmQtt~pthuQctinhH' saGchoH n H' = 0 va bai loan (H u H') ~ G 1agiai du'<Jctrenm~ngsuydi€n. ThuattoaD2.8:Chom~ngsuydi€n (A,D) va bai loanH ~ G kh6nggiai du'QC (kh6ngcoWigiai).TImH' saGchoH n H' =0 va bailoan (Hu H') ~ G 1agiai du'<Jc. Bu'oc1:A'+-H; D'~{}; G+-G\A'; Bu'oc2:while (G 7: {}andD 7: {})do 2.1:Lffy ramQtr tuD vac~pnh~tD. 2.2:if hypothesis(r)n G 7:{}orattr(r)c A' then Bo quar 2.3:else Them r VaGD' va b6 sungattr(r) VaGA'va trangtru'onghQp goa1(r)E A' thl1o~ira r' titD' (ne'uco) thoagoal(r')=goal(r)va ... 52 lO(;limQts6 lu~tsuy ra cac x E hypothesis(r)d€ bao dam tinh phanca'pcuabi€u d6. 2.4:G ~ G - A' Bu'oc3: if G * {}thenKe't thucvoi ke'tlu~n:Va'nd€ b6 sunggia thie'tla khonggiiii quye'tdu'qc Bu'oc4: else (Trangtru'onghqpn~yGraph(A',D')co bi€u d6 phanca'p tu'onglinghI GraphD.A')GQiLalamuc0cuabi€u d6GraphD.A'.f)~t: H' ~La-H. Menhd~2.9: Thu~tloan2.8d€ timstfb6 sunggiathie'tchobaisuydi~nla dungva codQphuct(;lp la O(IAI./DI). Ghi chu: Ta co th€ sii'dlJng themcac qui lac heuristictrongbuoc2 cua thu~t loantrennh~mgiiim thi€u s6 thuQctinh(j muc0 va/hayd€ u'ulien chQnItfa cacthuQctinhdu'qcu'ulien chovit$cdungb6 sunggiii thie'tcuabai loan. 2.6M~NG SUY DIEN-TINH TOAN Trongph~nn~ychungtaxetde'nmQtmohinhm(;lngsuydi~nlienquade'n . tinhloan,duqcgQi la m(;lngsuydi~n- tinhloan, ma trangnhi€u ling dlJng no chotamQtstfbi€u di~nd~ydu va thichh<;Jphoncuatri thucc~nthie'tlien quail de'ncacva'nd€ ha~cacbai tminc~ngiiii quye't.Cach bi€u di~nnhuv~yse th€ hit$nmQtcachttfnhienca'utruccuatri iliac,va giuptathie'tke'cacthu~tgiiii loantlJ'dQngmQtcachd~dangvoi nhungloi giiii tu'ongminhphilh<;Jpvoi cach fighTva lamcuaconnguoitrongcac lingd\lllggiiii loan,d~cbit$tla cacht$th6ng h6 trq cho vit$chQct~pva giiing d(;lY.Nhungph~nm~mnhu'the'dn co cach bi€u di~ntri thuctlJ'nhienva thichhqpchovit$cthie'tke'cacmodungiiii loan choWigiiiiphuhqpvoihQcsinhclingnhucacmodungiiii thich,modunki€m ITa valuyt$nt~pgiiii loan. '" 53 2.6.1 M6 hinh - Dinh m!hia2.10: MQtm~ngsuydi€n-tinh loang6mb6nthanhph~n: (1)T~ph<;fpA g6mcacthuQctinh. (2)T~ph<;fpD g6m cac lu~tsuydi~n(hay cac quail hc$suy di~n)lIen cae thuQCtinh. (3)T~ph<;fpF g6m cac c6ngthlic tinhloan hay cac thuWc tinh loan tu'dng lingvoi cac lu~tsuydi€n. 511tu'dnglingn~ythShic$nboi mQtanhx~ f:D--+F (4)T~ph<;fpR g6m mQtsO'qui Htc hay di~ukic$nrangbuQctrencac thuQc tinh. M~ngsuydi~ntinhloan g6m4 t~ph<;fpA, D, F va R nhu'the'se du'<;fcky hic$uboi bQb6n (A, D, F, R). Theo dinhnghla,tac6 (A, D) hI mQtm~ngsuydi€n va loi giiiichobailoanH --+G lIenm~illgsuydi€n n~ysexacdinhcacc6ngthlichay cacthut\lCtinhloancacph~ntii'thuQcGtucacph~n l thuQcH. Vi du 2.16:Kie'nthlic v~mQttamgiacc6 thSdu'<;fcbiSu di€n boi mQtm~ngsuy-- di~ntinhloan(A, D, F, R) nhu'sau: A ={A,B, C, a,b, c, R, 5, p, ...}la t~ph<;fpcacye'uto'cuamQttamgiacg6m 3 g6c,3 c~nh,bankinhvongtrollngo~itie'p,dic$ntich,illra chuvi, V.v..., D={r1:A,B ::::>C; r2:A, C =>B; r3:B, C ::::>A; r4:A, a=>R; rS:A, R =>a; r6:R, a ::::>A; r7:A, b, c ::::>a; ...} F ={f1:C =It-A-B; f2: B =It-A-C; D: A =It-B-C; f4:R =a/(2.sin(A)); f5:a=2.R.sin(A); f6:A =arcsin(a/(2.R)); f7:a=b2+C2- .b.c.cos(A);...} R={a+b>c; a+c>b; b+c>a;.a> bA >B; a=bA =B;...} 54 2.6.2Giai b~litmintrenm~ngsoydi~n-tinhtmin TrenmOtmq.ngsuydi~n-tinhloantac6thegiaiquye'tcacb~liloansuydi~n tinhloanching hq.nb~liloangiai tamgiachaybai loangiai tugiacdvatrenvi<$c giaibai loan suydi~ntrenmq.ngsuy di~n.Hon nii'a,cac cangthuchaythuwc tinhloan c6 thedu'<JCgall cho cac trQngs6 the hi<$ndOphuctq.ptinhloan cua chung.Tu d6tac6 thetlmra du'<JCnhii'ngWi giai chobai loansuydi~ntinhloan vOichi phi tinhloan tha'pnha'tdva tren vi<$ctlm Wi giai t6i u'utrenmq.ngsuy di~nc6trQngs6.Ngoai fa, chungtac6 theHmra du'<JCcaccangthuctu'ongminh quacacbu'ocgiai bai loanva rut gQncaccangthucdu'oidq.ngky hi<$u.Nhu'the' trenmq.ngsuydi~n-tinhloanmOttamgiactac6 thechIra mOtcachtv dOngcac c6ngthuctu'ongminhdetinhmQts6ye'ut6ngytumOts6ye'ut6khac(ne'ubai loanc6 loi giai).Ke'th<Jpdi~ungyvoi vi<$cdo tlmnhii'ngsv lienh<$suydi~n giii'acacye'ut6naod6mataquailtamsechotamOtphu'ongphapdetv dOng Hmrathemnhii'nglu~tsuydi~nvanhii'ngcangthuctinhloanlienquailde'ncac ye'ut6.E)i~ungyc6ynghlanhu'mQtky thu~tkhamphatri thuc. MOtsVmdrOngcuamq.ngsuydi~ntinhloan la chophepxet themcac quail h<$khacvoi cacquailh<$suydi~n- tinh lOanaday,ching hq.ncacquailh~hlnh hQcgiii'a cac d6i J:u'<Jnghlnh hQc diem, doq.n,ria, g6c. Sv md rOngngy se du'<Jc richh<JptrongmOtca'utruc truu tu'<Jngtheophu'ongphap l~ptrlnhhu'ongd6i tu'<JngmatagQila mQtd6i tu'<Jngtinh loan.Khai ni~mv~d6i tu'<Jngtinhloanse du'<Jcxay dvngtrongchuangtie'ptheovan6 du'<JCxemxettrongmOtmahlnhtri thucdu'<JcgQila ma hlnhtri thuccac d6i tu'<Jngtinhloan.