Các giải thuật tìm kiếm và lựa chọn thành phần Cots tối ưu theo các tiêu chí giá thành và dữ thừa dữ liệu

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

43
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

In this paper we presented two algorithms applied to select COTS components witth optimization of cost and data redunancy (size). The proposed algorithms are realized based on .NET platform and experimented on case study Geographic Translator Service. The comparison between proposed and original algorithm also is presented.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các giải thuật tìm kiếm và lựa chọn thành phần Cots tối ưu theo các tiêu chí giá thành và dữ thừa dữ liệu

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.23, S.2 (2007), 153–163 ı e e . . a ` . ’ ´ ´ ´ ˆ ` .. ` ˆ ˆ . CAC GIAI THUAT T` KIEM VA LU A CHON THANH PH` N COTS TOI U U IM ˆ A . . . `. ˜. ˆ ´ ˆ ´ ` ` THEO CAC TIEU CH´ GIA THANH VA DU THU A DU LIEU I . ´ ´ ` ˆ ˘ ` HUYNH QUYET THANG1 , PHAM THI QUYNH2 . . o CNTT, Tru.`.ng DHBK H` Nˆi a o . 2 .`.ng DHSP H` Nˆi a o Khoa CNTT, Tru o . 1 Khoa Abstract. Component-based software development is gaining recognition as the key technology for the construction of high-quality, evolvable and large software systems in timely and aﬀordable manners. Commercial components (COTS) is being used more and more in Component-Based Software Engineering for building software applications, and accordingly, some mechanisms are demanded by developers of software applications to describe, search, select and compose COTS components. In this paper we presented two algorithms applied to select COTS components witth optimization of cost and data redunancy (size). The proposed algorithms are realized based on .NET platform and experimented on case study Geographic Translator Service. The comparison between proposed and original algorithm also is presented. ´ ’ ` ` ` T´m t˘t. Ph´t triˆn phˆn mˆm hu.´.ng th`nh phˆn (Component-Based Software Development o a a e a e o a a .ng k˜ thuˆt tiˆu biˆu xˆy du.ng c´c phˆn mˆm l´.n, ph´.c tap, gi´ p giam ’ a ` ` ’ a a e o y a e e u . u CBSD) l` mˆt trong nh˜ a o u . . . ` ` ` th`.i gian, cˆng s´.c v` gi´ th`nh xˆy du.ng phˆn mˆm. C´c th`nh phˆn thu.o.ng mai (COTS) dang o a e a a a o u a a a a . . ’ ` ` ` ’ . a a e a a ´ a a e o e ` a e du.o.c su. dung ng`y c`ng nhiˆu trong cˆng nghˆ phˆn mˆm du.a th`nh phˆn dˆ xˆy du.ng c´c u.ng . . . . ’ ´ ´ ` ´ ’ o a a a e ´ a e ` a o o dung phˆn mˆm, v` do d´ c´c nh` ph´t triˆn u.ng dung d˜ yˆu cˆu mˆt sˆ co. chˆ dˆ mˆ ta, t` kiˆm, a ` e a e e o ’ ım e . . . ` ’ a a a a a a a a u o ınh a a . lu.a cho n v` xˆy du.ng c´c th`nh phˆn COTS. Trong b`i b´o n`y ch´ ng tˆi tr` b`y giai thuˆt lu.a . . . . ’ ` ´ chon c´c th`nh phˆn COTS tˆ i u.u theo du. th`.a d˜. liˆu (k´ thu.´.c) v` gi´ th`nh, dˆ t´ ho.p trong a a o e ıch . u u e ıch o a a a . a . ´ ´ ` ` ` ’ a a ` a a a e e a o o u . phˆn mˆm cˆn xˆy du.ng. Thuˆt to´n dˆ xuˆt c´ dˆ ph´.c tap chˆp nhˆn du.o.c. C´c thu. nghiˆm a e a a . . . . . . .o.c thu.c hiˆn trˆn mˆt b`i to´n cu thˆ: Thiˆt kˆ dich vu chuyˆn dˆ i khuˆn dang c´c anh khˆng ’ ’ ’ o ´ e . ´ ’ du . o a o e e o a a . e e e . . . . . gian. ’. A ˆ 1. MO D` U ` ` ` a a e o a e’ . u Ph´t triˆ n phˆn mˆm du.a th`nh phˆn (CBSD) cho ph´p ngu.`.i ph´t triˆ n tao ra nh˜.ng a e’ a e . .ng dung d`ng mˆt phˆn phˆn mˆm du.o.c goi l` c´c th`nh phˆn. Th`nh phˆn phˆn mˆm ` ` ` ` ` ` ` u o a a e a a a a a e u ´ . . . . a a .n vi cˆ u th`nh v´.i giao diˆn du.o.c thoa thuˆn tru.´.c v` chı phu thuˆc du.´.i g´c dˆ ´ ’ a o e a o a ’ o o o o l` mˆt do . a a o . . . . . . . ´ ’ a a o ınh a e o e a o a u o e e nˆi dung d˜ r˜ r`ng, ch´ng c´ kha n˘ng liˆn kˆt, tu.o.ng t´c v´.i nhau h` th`nh nˆn mˆt hˆ o . . . ` ` ` ´ a a a e o e’ e’ o a thˆng m´.i. Th`nh phˆn phˆn mˆm c´ thˆ du.o.c triˆ n khai mˆt c´ch dˆc lˆp. COTS l` mˆt o o o a a o . . . . . .o.ng mai (c´ thˆ du.o.c cˆ p giˆ y ph´p, ho˘c du.o.c b´n) ’ ` ` ` ´ ´ th`nh phˆn phˆn mˆm mang t´ thu a a a e ınh o e a e a . . a . . a ´ ´ u ’ ´ o ’ u u a y e u cho ph´p d´ng g´i, phˆn phˆi, lu.u gi˜., su.a ch˜.a v` tu` biˆn theo y ngu.`.i su. d`ng, nh˜.ng e o o a o .`.ng l´.n v` du.o.c lu.u tr˜. trong c´c kho phˆn mˆm. ` ` o a u a a ` e th`nh phˆn n`y thu o a a a . ’n phˆn mˆm du.a nˆn th`nh phˆn COTS ng`y c`ng tro. nˆn linh hoat l` do ` ` ` ’ e Viˆc ph´t triˆ e a e a e e a a a a . . ` . a ’ ` a ` ` ’ a ’ a c´ su. gia t˘ng vˆ chˆ t lu.o.ng v` su. da dang cua c´c san phˆ m du.a nˆn th`nh phˆn COTS o . a e ´ a . e a a . . . 154 ´ ´ ` ˆ ˘ ` HUYNH QUYET THANG, PHAM THI QUYNH . . ´ ’ u e nhu. hˆ diˆu h`nh, co. so. d˜. liˆu, hˆ thˆng tin nh˘n, thu. diˆn tu., GIS, GUI builders... C´c e ` e o a a e ’ . e a . . ´ . .ng dung v` c´c th`nh phˆn ho`n thiˆn v` d˜ c´ m˘t trˆn thi tru.`.ng ’ ` a ´ ` ’ a a a a a e a a o a e o san phˆ m n`y gˆ m c´c u a a o . . . . ` ´ . ´ ´ ’ a a a u e a a CNTT. Sˆ lu.o.ng c´c th`nh phˆn COTS dang tiˆp tuc gia t˘ng, chˆ t lu.o.ng c˜ng nhu. kha o . . ` ` ’ ’ o a a e u a e’ a e e n˘ng u.ng dung cua n´ ng`y c`ng du.o.c cai thiˆn. Ho.n n˜.a, ph´t triˆ n phˆn mˆm du.a trˆn a ´ . . . . ’ ` ´ ´ ` ` ’ a ’ o c´c th`nh phˆn COTS c`n cung cˆ p kha n˘ng mo. rˆng v` biˆn dˆ i c´c u.ng dung phˆn mˆm a a a o a a e o a ´ a e . . a u o o o e’ u . o thˆng qua c´c h`m APIs, c´c ngˆn ng˜. plug- ins v` script. T`. d´, n´ c´ thˆ ph` ho.p v´.i o a a a o u . dung cua t`.ng muc d´ r`ng buˆc kh´c nhau. ` ’ u o a nhu cˆu su . a ’ . . ıch, a ’n phˆn mˆm du.a th`nh phˆn COTS, viˆc lu.a chon th`nh phˆn COTS ` ` ` ` Trong ph´t triˆ a e a e a a e . a a . . . .p l` mˆt trong nh˜.ng b`i to´n rˆ t quan trong. Trong b`i b´o n`y ch´ng tˆi tˆp trung ´ u a a a a a a u o a ph` ho a o u . . . . .u mo. rˆng giai thuˆt lu.a ’ o ’ v`o nghiˆn c´ a e u a . . . ’ ` ´ ’ e a a chon c´c tˆ ho.p th`nh phˆn u.ng cu. viˆn a o . . ´n tr´c phˆn mˆm cˆn xˆy ` ` ` COTS cho kiˆ e u a e a a ’ o ’ a a . du.ng. C´c mo. rˆng trong giai thuˆt lu.a . . . a e e ı: chon n`y du.o.c xˆy du.ng trˆn 2 tiˆu ch´ a . . . ` ’ a u u e a a a du. th`.a d˜. liˆu cua c´c th`nh phˆn v` . ´ tu.o.ng ch´ng ` ’ gi´ th`nh cua th`nh phˆn. Y ’ a a a a u ’ ’ tˆi ´p dung trong giai thuˆt xˆy du.ng giai o a a a . . . .a chon l` phu.o.ng ph´p nh´nh cˆn. a a a thuˆt lu a . . a . . ´u tr´c cua b`i b´o du.o.c tr` b`y ’ Cˆ a u a a ınh a . ınh a ` e e ´ ınh a nhu. sau. Muc 2 tr` b`y vˆ tiˆn tr` xˆy . ` ` ` a e a a du.ng phˆn mˆm du.a th`nh phˆn COTS. . . ’ Muc 3 s˜ tr` b`y giai thuˆt COTSCone ınh a a . . ’ ’ a a a ` a e ﬁgs v` nh˜.ng d´nh gi´ vˆ c´c kha n˘ng mo. a u ´ ´ rˆng v` tˆi u.u thuˆt to´n. Tiˆp theo, Muc o a o a a e . . . ` ´ ’ o e a a a 4 l` c´c mo. rˆng dˆ xuˆ t cho thuˆt to´n a a . . ’ COTSConﬁgs. Trong Muc 5 l` c´c mo. a a . rˆng thˆng tin trong d˘c ta COTS Doco o a ’ . . ’ lu.u tr˜. gi´ th`nh th`nh phˆn. ` u a a a a e ument dˆ . nghiˆm e a ’ Muc 6 tr` b`y c´c d´nh gi´ thu ınh a a a . . .c hiˆn v´.i c´c giai thuˆt dˆ xuˆ t, ` ´ ’ d˜ thu a e o a a e a ` ` ´ . . . a e H` 1. Tiˆn tr` xˆy du.ng phˆn mˆm ınh e ınh a . .´.ng ph´t triˆ n. ´ ´ . .a trˆn c´c th`nh phˆn COTS cuˆi c`ng l` kˆt luˆn v` hu o o u a e a a a e’ ` du e a a a . ’ ´ ˆ ´ ˆ ˆ ˆ 2. TIEN TR` INH PHAT TRIEN PH` N M` M A E . ` N COTS ˆ ´ ` ˆ DU A TREN CAC THANH PHA . ´ ` ` ` ` Mˆ h` tiˆn tr` ph´t triˆ n phˆn mˆm hu.´.ng th`nh phˆn du.a trˆn c´c th`nh phˆn o ınh e ınh a e’ a e o a a e a a a . ’ trong H` 1, du.o.c chia th`nh ba giai doan ([1, 5, 6]): a COTS, mˆ ta o ınh . . ’ . ’ a o o ınh o ı . o o Giai doan 1: Su. dung c´c cˆng cu mˆ h` h´a (v´ du UML-RT cua bˆ cˆng cu Rational . . . . ’ mˆ ta v` thiˆt kˆ kiˆn tr´c phˆn mˆm. Mˆu d˘c ta du.o.c xˆy du.ng v` tr` b`y ˜ a ’ ´ ´ ´ ` ` a ınh a e e e e u a e a Rose) dˆ o ’ a . a . . trong [1, 5]. ´ ´ ’ . o e ınh . o Giai doan 2: Su. dung mˆt tiˆn tr` tu. dˆng dˆ xuˆ t c´c thˆng tin t`. k´ ph´p UML - RT e’ a a o u y a . . . ˜u d˘c ta XML. th`nh c´c mˆ a ’ a a a . ´ ´ ` ´ ’ Giai doan 3: Tiˆn tr` COTSTrader, thu.c hiˆn t` kiˆm danh s´ch c´c th`nh phˆn u.ng cu. e ınh e ım e a a a a . . . ’ ´ ´ . ´ ˆ ˆ ` .. ` ˆ ˆ CAC GIAI THUA T T` KIEM VA LU A CHON THANH PH` N COTS TOI U U IM A . . 155 ˜ ´ ’ ’ ’ viˆn trong kho ch´.a mˆu XML. Co. so. cua tiˆn tr` n`y l` giai thuˆt COTSTrader. Giai e u a e ınh a a ’ a . .o.c tr` b`y chi tiˆt trong [1]. ´ ınh a e thuˆt d˜ du . a a . ’ ` u ´ ´ ´ ´ a a Tiˆp theo tiˆn tr` t` kiˆm l` tiˆn tr` COTSConﬁgs lu.a chon tˆ ho.p th`nh phˆn t`. e e ınh ım e a e ınh . . o . .ng cu. viˆn dˆ tao ra c´c cˆ u h` thoa m˜n kiˆn tr´c phˆn mˆm yˆu ` ´ ´ ´ ` ’ e e’ . danh s´ch th`nh phˆn u a a a a a ınh ’ a e u a ` e e . tu.o.ng v´t can ` ´ ’ cˆu. Trong [1, 2, 3] c˜ng tr` b`y chi tiˆt giai thuˆt COTSConﬁgs, ´p dung tu ’ a u ınh a e a a e . . . ´ ´ ´ ’ ’ ’ o a a ınh. Mˆt sˆ cai tiˆn cua giai thuˆt n`y c˜ng d˜ du.o.c tr` o o ’ e a a u ınh a c´c tru.`.ng ho.p thoa m˜n cˆ u h` a . . . . b`y trong [5, 6]. a ´ ´ ´ o o u u a a ’ a a ınh a Bu.´.c cuˆi c`ng trong giai doan n`y, khi tˆ t ca c´c cˆ u h` d˜ du.o.c sinh, ch´ng ta thu.c . . . .´.c d´ng g´i c´c cˆ u h` dˆ tao ra mˆt u.ng dung ho`n chınh. ´ ’ a o a a ınh e’ . o ´ hiˆn bu o o e . . . ´ ınh ’ a a a ’ Trong tˆm cua b`i b´o tˆp trung v`o bu.´.c th´. hai cua giai doan 3 - tiˆn tr` COTSConﬁgs a a o u e . . . .a chon tˆ ho.p th`nh phˆn. ’ ` a a lu . . o . . . ’ ˆ ˆ ´ 3. THUAT TOAN COTSConﬁgs LU A CHON TO HO P . . . . ´ ` ˆ CAC THANH PH` N COTS A 3.1. Mˆ ta b`i to´n o ’ a a ` ´ ´ ´ a a e a o a ınh Tiˆn tr` sinh c´c cˆ u h` t`. tˆp c´c th`nh phˆn u.ng viˆn l` mˆt qu´ tr` quan trong e ınh a a ınh u a a . . . ´m c´c th`nh phˆn COTS. Tiˆn tr` n`y s˜ lu.a chon tˆp c´c ` ´ trong to`n bˆ qu´ tr` t` kiˆ a o a ınh ım e a a a e ınh a e . . . a a . ´ ´ ` ` ` ` a o e u a e ` a a e e u . ’ a th`nh phˆn ph` ho.p nhˆ t v´.i kiˆn tr´c phˆn mˆm cˆn xˆy du.ng. Diˆu kiˆn ph` ho.p o. dˆy a a u . . . ` ´ ınh a ´ ’ ’ i lu.a chon c´c th`nh phˆn sao cho tˆp dich vu m` cˆ u h` d´p u.ng du.o.c phai kh´.p a a a . o l` pha . a . a . . a a . .i tˆp dich vu yˆu cˆu cua kiˆn tr´c phˆn mˆm cˆn xˆy du.ng. ´ ` e ` a ’ e u a ` e ` a a v´ a . o . . . ’ ` a a a e’ o B`i to´n lu.a chon tˆ ho.p c´c th`nh phˆn COTS du.o.c ph´t biˆ u nhu. sau ([1]): Cho mˆt a a . . o . a . . .a to`n bˆ c´c th`nh phˆn u.ng viˆn COTS ph` ho.p ´ u ` ` ´ kiˆn tr´c phˆn mˆm A. C´ mˆt kho B ch´ e a ` e o o u a o a a a e u . . . ` ´ ` ’ ’ a a a a a ınh a a a a dˆ lu.a chon t´ ho.p v`o A. Cˆn phai sinh ra c´c cˆ u h` S l` tˆp ho.p cua c´c th`nh phˆn e’ . . ıch . . . ´ ınh e o a a . u a a e a ´ u.ng viˆn COTS c´ trong B, sao cho cˆ u h` S d´p u.ng c´c dich vu/ch´.c n˘ng m` A yˆu ´ . . vˆy cˆ u h` S cˆn d´p u.ng hai diˆu kiˆn: ´ ` ` ` a a ´ e e cˆu. Nhu a a ınh a . .o.c hˆ tro. bo.i c´c th`nh phˆn cua S phai tr`ng v´.i tˆp c´c dich vu ˜ . ’ a ` ’ u a a ’ o a a . (i) Tˆp c´c dich vu du . o a a . . . . . .o.c hˆ tro. bo.i A (t´.c l` khˆng c´ c´c lˆ hˆ ng dich vu). ˜ ˜ ’ du . o . ’ u a o o a o o . . ` ´ (ii) Khˆng c´ hai th`nh phˆn n`o cua S cung cˆ p c`ng mˆt dich vu chung (t´.c l` khˆng o o a a a ’ a u o . u a o . . c´ dich vu tr`ng) o . u . ´ a a a a e a a ınh Sau dˆy l` thuˆt to´n s˜ sinh ra c´c cˆ u h` S ([1]). . ’ Giai thuˆt COTSConﬁgs a . 1 function COTSconﬁgs(i, Sol, S) ´ ’ a ’ a 2 // 1 i size(CB(A)) khao s´t qua tˆ t ca c´c kha n˘ng c´ trong kho CB(A) a ’ a o ` ´ ’ e (ch´.a danh s´ch c´c th`nh phˆn u.ng cu. viˆn) u a a a a .i dang du.o.c xˆy du.ng trong giai thuˆt ´ ’ a 3 // Sol l` cˆ u h` tam hiˆn th` a a ınh . e o . a . . . .a du.ng tˆp ho.p tˆ t ca c´c cˆ u h` c´ gi´ tri dˆi v´.i kiˆn tr´c A ´ ´ ´ ´ 4 // S ch´ u a u . . . a ’ a a ınh o a . o o e 5 if i size(CB(A)) then ´ e o a ’ a . 6 for j := 1 to size(Ci.R) do//thu.c hiˆn v´.i tˆ t ca c´c dich vu trong C1 . . . ’. gom dich vu Ci.Ri v`o Sol 7 // thu a . . 8 if {Ci.Ri} ∩ Sol.R = ∅ then // Ci.Ri ∈ Sol : R? 9 Sol := Sol ∪ {Ci.Ri} 10 if A.R ⊆ Sol.R then // Kiˆ m tra xem Sol c´ l` mˆt cˆ u h` khˆng? e’ o a o a ınh o . ´ ´ ´ ` ˆ ˘ ` HUYNH QUYET THANG, PHAM THI QUYNH . . 156 ´ S := S ∪ {Sol} // Nˆu Sol l` mˆt cˆ u h` e a o a ınh, n´ s˜ du.o.c gom nh´m v`o o e o a . ´ . trong S ´ ˜ ´ e a o a . o a . 12 else // nhu.ng nˆu vˆn c`n c´c dich gˆi nhau v` dich vu tr`ng nhau . u 13 conﬁgs(i, Sol, S) ; // t` trong Ci... ım 14 endif 15 Sol := Sol − {Ci.Ri} 16 endif 17 endfor ´ 18 conﬁgs(i + 1, Sol, S) // tiˆp tuc trong CB(A) e . 19 endif 20 endfunction ˜ ´ ` ’ . ’ ’ C´c kho.i tao cua giai thuˆt l` S =; Sol =; conﬁgs (1; Sol; S). Mˆi cˆ u h` (d`ng 9) dˆu a a a o a ınh o e . .o.c sinh ra b˘ ng c´ch thu. tˆ t ca c´c u.ng cu. viˆn, kˆt ho.p dˆn c´c dich vu Cj.Rj c`n chu.a ` ´ ´ ’ a ’ a ´ ’ e e . ` a . a a a o du . . ` o ’ a ’ a u a o o a o a ch´.a trong A, v` bo di nh˜.ng dich vu m` A d˜ c´ rˆ i (d`ng 8 v` d`ng 10). Khi giai thuˆt u . . . .a tˆ t ca c´c cˆ u h` cˆn thiˆt. ´ ´ ´ ´ a e kˆt th´c, biˆn S s˜ ch´ a ’ a a ınh ` e u e e u ´ 11 3.2. D´nh gi´ nhˆn x´t vˆ giai thuˆt a a a e ` e ’ a . . . tu.o.ng giai thuˆt quay lui dˆ thu.c hiˆn qu´ tr` t` kiˆm lu.a ´ ’ ’ e a ınh ım e a e’ . Thuˆt to´n ´p dung tu a a a . . . . . .p lˆ. N´ s˜ sinh t`. tˆp ho.p c´c u.ng cu. viˆn trong kho B : CB(A) = ´ ınh . . ’ e o e u a a ´ chon c´c cˆ u h` ho e a a . . . ´ u ` ´ {C1 , ..., Ck}, v` t`. kiˆn tr´c phˆn mˆm cˆn xˆy du.ng A, mˆt tˆp S c´c cˆ u h` ho.p lˆ (d`ng a u e a ` e ` a a o a a a ınh . e o . . . . ˜ ’ ` ´ o a a ınh o o . o o o o . 11). Khˆng c´ tru.`.ng ho.p c´c cˆ u h` trong S c`n tˆ n tai c´ lˆ hˆ ng dich vu (mˆt dich vu o o . . . . . ` a . e n`o d´ khˆng du.o.c d´p u.ng) hay c´c dich vu chˆ ng ch´o. Do d´, giai thuˆt s˜ chı sinh nh˜.ng a o o o ’ a e ’ u . a ´ . o . ´ ´ ınh . e ’ ’ e a a o e’ a o a ım e e cˆ u h` ho.p lˆ. Tuy nhiˆn, giai thuˆt n`y c´ nhu.o.c diˆ m l` mˆt giai thuˆt t` kiˆm v´t a . . . . . .i dˆ ph´.c tap l` O(2n ), trong d´ n l` sˆ lu.o.ng c´c dich vu m` tˆ t ca c´c th`nh phˆn ´ ` ´ a . a a o a o . can, v´ o u . a o . . a a ’ a . ’ d´p u.ng. Khi d´ v´.i mˆt kho c´c th`nh phˆn u.ng viˆn l´.n, th` s˜ dˆn ˜ ` ´ o a a a e o ı e a o o trong CB(A) c´ thˆ a ´ o e . ’ ’ ´ ’ t´.i b`ng nˆ tˆ ho.p. Qu´ tr` t` kiˆm nhu. vˆy s˜ khˆng kha thi. o u o o . a ınh ım e a e o . ´ ’ ´ ’ ˆ ˆ ˆ ˆ ´ E 4. CAC D` XUAT CAI TIEN GIAI THUAT COTSCONFIGS . . . ’ ˆ ´ ` ˆ A LU A CHON TO HO P CAC THANH PH` N COTS . . . ` ´ ’ ’ a a e u o e’ ` Dˆ giam dˆ ph´.c tap cua thuˆt to´n trˆn, ch´ng ta c´ thˆ dˆ xuˆ t thay b˘ ng giai thuˆt e’ ’ o u . e a a a . . . . tu.o.ng cua thuˆt to´n nh´nh cˆn l` nh`. v`o mˆt sˆ c´c ´ a ’ ’ nh´nh cˆn (brand and bound). Tu a a a a a a a o a o o . . . . ´ ´ ´ ’ a o o o a a a a o a o e’ ` a thˆng tin d˜ c´ dˆ nh˘ m loai bo b´.t mˆt sˆ c´c phu.o.ng ´n ch˘c ch˘n khˆng phai l` tˆi u.u, o . ´ . ’ o .c l` c´ thˆ lu.o.c b´.t mˆt sˆ n´t khˆng cˆn thiˆt trˆn cˆy t` kiˆm. Vˆy mˆt sˆ tiˆu ch´ c´ ’ . o ´ u ` ´ e a ım e ´ ´ e o o o a e a o o ı o t´ a o e u . . . ´ ’ ım e a e’ a e thˆ du.a v`o dˆ t˘ng hiˆu qua t` kiˆm nhu.: e’ . ` ´ - Lu.a chon th`nh phˆn v´.i du. th`.a d˜. liˆu l` tˆi thiˆ u. a a o u u e a o e’ . . . ’ ` ´ a a o o a a a o e’ - Lu.a chon th`nh phˆn v´.i tˆ ng gi´ th`nh l` tˆi thiˆ u. . . ’ ´ ` ´ ’ ’ 4.1. Cai tiˆn giai thuˆt lu.a chon th`nh phˆn v´.i du. th`.a d˜. liˆu tˆi thiˆu e a . a a o u u e o e . . . ´ ınh u . ´ ` ` Khi xˆy du.ng c´c cˆ u h` ph` ho.p v´.i kiˆn tr´c phˆn mˆm yˆu cˆu, ch´ng ta c´ thˆ a a a o e u a e e ` a u o e’ . .o.c nhiˆu kˆt qua cˆ u h` ([1, 2, 5, 6]). Trong d´, s˜ c´ nh˜.ng cˆ u h` l` tˆ ho.p c´c ’ ` ´ ´ ınh ´ ınh a o . a ’ a e e a thu du . o e o u ´ ` ` a e u a ` e a e ` a o o u th`nh phˆn m` ngo`i nh˜.ng dich vu m` kiˆn tr´c phˆn mˆm d˜ yˆu cˆu, c`n c´ nh˜.ng dich a a a a u . . . . th`.a khˆng cˆn d`ng. Nˆu su. dung c´c cˆ u h` n`y s˜ l`m t˘ng dˆ ph´.c tap dˆn t´.i ˜ ` ´ ´ vu du u o u . o a u e ’ . a a ınh a e a a a o . . ` ` ` ´ a a u du. th`.a d˜. liˆu v` th`nh phˆn cua hˆ thˆng phˆn mˆm du.o.c xˆy du.ng. Dˆy l` nh˜.ng cˆ u u u e a a a ’ e o a e a . . ´ . a . ’ ´ ´ . ´ ˆ ˆ ` .. ` ˆ ˆ CAC GIAI THUA T T` KIEM VA LU A CHON THANH PH` N COTS TOI U U IM A . . 157 ` ´ ’ a ’ h` khˆng du.o.c lu.a chon. V` vˆy ch´ng ta cˆn phai xˆy du.ng giai thuˆt t` kiˆm, lu.a chon ınh o ı a u a a ım e . . . . . . . . .ng cˆ u h` khˆng cˆn thiˆt n`y. ´ ` ´ ’ a ınh o a e a COTSConﬁgs sao cho loai bo nh˜ u . ` ´ ´ . ’ a a o u u e a o e’ Giai thuˆt nh´nh cˆn t` kiˆm lu.a chon c´c th`nh phˆn v´.i du. th`.a d˜. liˆu l` tˆi thiˆ u a a a ım e . a . . . ´ du.o.c dˆ xuˆ t nhu. sau. e a . ` ’ ´ ´ ’ ’ Giai thuˆt COTSConﬁgs cai tiˆn v´.i du. th`.a d˜. liˆu tˆi thiˆu a e o u u e o e . . ’ ´ 1 total = numOfInterfaces(CB(A)) //tˆ ng sˆ dich vu cua mˆt cˆ u h` o o . o a ınh . ’ . ´ ’ 2 function brandAndBound(i, Sol, S) //giai thuˆt nh´nh cˆn a a a . . 3 if i size(CB(A)) then ´ e o a ’ a . 4 for j := 1 to size(Ci.R) do //thu.c hiˆn v´.i tˆ t ca c´c dich vu trong C1 . . . ’ a // thu. gom dich vu Ci.Ri v`o Sol . . 5 if {Ci.Ri} ∩ Sol.R = ∅ then // Ci.Ri ∈ Sol : R? 6 Sol := Sol ∪ {Ci.Ri} 7 if A.R ⊆ Sol.R then // 8 if numOfInterface(S) < total then ´ ´ ’ //sˆ dich vu cua cˆ u h` n`y c`n ´ ho.n ca ngu.˜.ng(muc tiˆu) nˆn o . o e e . ’ a ınh a o ıt . .˜.ng vˆ sˆ dich vu cua mˆt cˆ u h` ` o . e ´ o a //dˆy l` mˆt gi´ tri cua ngu o a a o a . ’ . ’ . ´ ınh . m´.i o 9 total := numberOfInterface(S ) // cˆp nhˆt ngu.˜.ng m´.i a a o o . . ´ ’ u 10 S := // x´a c´c kˆt qua c˜ o a e .a Sol v`o tˆp kˆt qua S ´ ’ 11 S := S ∪ {Sol} // du a a e . 12 else if numberOfInterface(S ) = total then ` o . ’ //thoa m˜n ngu.˜.ng vˆ sˆ dich vu a o e ´ . ´ ’ a a e 13 S := S ∪ {Sol} // du.a Sol v`o tˆp kˆt qua S . 14 endif ´ ˜ ´ 15 else // nhu.ng nˆu vˆn c`n c´c dich vu gˆi nhau ho˘c dich vu tr`ng nhau e a o a . a . . o . . u 16 conﬁgs(i, Sol, S) // t` trong Ci... ım 17 endif 18 Sol := Sol − {Ci.Ri} 19 endif 20 endfor 21 if (numberOfInterface(S) + (n − m)× minOfInterface(CB(A)) ⇐ total then 22 brandAndBound(i + 1, Sol, S) 23 endif 24 endif 25 endfunction ´ ` ´ ’ Ta c´, mˆt cˆ u h` tˆi da s˜ l` tˆp ho.p cua to`n bˆ c´c c´c th`nh phˆn u.ng viˆn. Nhu. o o a ınh o a o a a a a e e a a . ´ . . . .c l` sˆ c´c dich vu tˆi da cua mˆt cˆ u h` s˜ l` tˆ ng cua c´c dich vu du.o.c cung cˆ p ’ ´ a . ´ ´ ´ ınh e a o ’ ’ a . a vˆy, t´ a o a u o a . o . . . . .i c´c th`nh phˆn u.ng viˆn. Vˆy, tru.´.c tiˆn, ta goi biˆn total l` biˆn lu.u tˆ ng sˆ dich vu ’ ` ´ ´ ´ ´ ’ a a e a o e e a e o o . bo a . . . .i tao biˆn n`y b˘ ng tˆ ng sˆ dich vu cua to`n bˆ c´c th`nh ’ ` ´ ´ ’ ’ cua mˆt cˆ u h` (d`ng 1). Kho . o a ınh o e a a o o . a o a a . ´ . ’ . ` ´ ` o ´ ’ a ınh a phˆn u.ng viˆn. Dˆy ch´ l` ngu.˜.ng vˆ tˆ ng sˆ d˜. liˆu cua mˆt cˆ u h` a e o e ’ o u e o a ınh. . . ´