最小重み点被覆問題に対する並列分枝限定法の性能評価

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2003−AL−91 (8) 2003／9／19.

(2) !#" $&%('!)(" &*,+!-(" .!/(0!1(" ]wT24xQ:3 ^454_868`87:a494R:;8B:b4<:=?c4d8>:@8e4f4A:@4Z:g4B:C4hjD8i:h8E:F4V4G4`:H4^4I8_4k8J:K8Y4L:l4M?m4Q4N:O4O4P4P:=4Q:G?c4d8RTS4e4U8f:n4V4o8B:M4L:;8p8W4qjX4wTr:x4Y4O:x8s4Z:=8t4 I8J:K4Z:[4u8\v 4 Y : l 4 5 8 6 : 7 4 9 8 ; : ` 4 y 8 b 4 z : < 4 = { 5 8 6 : Q 4 | 4 b 8 } 4 ~ : ` 4 y 8 b 8 z 8 4 G 4 H 8 M : ` 4 4 b 4 4 9 8 M : Z 4 = 4 6 w 4Z:|?c4NT?d8`::4Y:44488B:4Z:?44N:4B?M4c4;8djL4:h8b8L:Y8 4a:k?`84:4aT=4z:k8c4d8B4E4:h8:=4Z:4M4?;8Q:> x4=44c4I8d8`:8e4f{B{Q:Z4n4Y4o8l4Z:m84:8W:=4W4 µ4Y{¶4l ·4@{O¡¸°=¢¹45£º 68J:7K89£`:;8»4`{k¼<:Y =¤J¡K8½4¥{¾4Q8¿4¦À:Q¡8§4W4hjQ:L4sÁ¨¡t49{54k868Y{7:©«94;8ª¬5{` 644§{b8h4z:£=4®{ ¯°4Q 4cÁ®±d8Z{`:X4y8Y£Â4l³Y:²£°´j4W4M4<¡;4=¢GÃ 8Q:Ä4Å4=45464§4h44®8QÄ4Å8L:c4d4Æ4Ç4È8`88É4Ê4k8Y4l [. ]. PC. Performance Evaluation of Parallel Branch-and-Bound Algorithms for the Weighted Vetex Cover Problem. ". Yoshitaka Shimoda ,. ". Daisuke Takafuji ,. Satoshi Taoka. ". and. Toshimasa Watanabe. ". [abstract] Even though a branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems, the computation time is likely to be exponential as the size of input increases. Parallelization is one way of improvement. We can expect that using a better upper bound makes bounding operations appear at early stages of computation, possibly resulting in short computation time. Here we consider using an approximation algorithm in computing an upper bound. In this paper, we experimentally evaluate how using an upper bound given by an existing approximation algorithm and variable selection strategies affect the computation time of a parallel BB for solving the minimun cost vertex cover problem on a PC cluster.. ÐÔ h4c4Ë Ñ4;4Ì!Ò8ÍÏQ:Î C°D8wTx E:F4G4H4I8J:K8<:S4U8` Ó O4Q4W4P4O4X4`:P:G4C4Y8Ø8D84Q:E:a:Ù4F4Z:ÕD8G4H{<:I8Ú{Û8J:z:K8yV4B:Q:Ö=8Ü4S4Ý8U8m4Q:L:V:G4Þ4M4H4ß?;?M8aTa4k8L:r:×8Y4z:5{P4l{6Ym 7²4:ä494å;8Z:ªæ54à?64N:ç4© è4wT=já4â7:94> ç4x è4z:=4b88Y4él:5468c47:d494=4;8Ü{QÝã ;°W:Ã4ÒÁ4¯jk8`ê°Y:ð4b8ñ4zÁò4< ã4²4` 4ë4ó8ìÁ<8í! x > x `:ã4z:yîô?N³ï=4l:²54áÁ68â7 94Þ4;8ß?<4aTk8J:K8Y8Q:4õ4a:ö8Z4ZX4ì8Y{8O4P:N:=4B4c4Y8d8aT÷4e4ì8f:n4B:c4o8d8Q:S4e4ø{f{;L a84Q:r:4z:s49 t4 I8ú4ûZ:u8`8v:{wùxzê=Y4l8:Q8a::=?8|4bje Q T[8`8: Y

(3) 8e4f _44üþý ÿ Q T[8`8: Y

(4) 8e4f WRT948W4> x 4YY4_£l 4üjZ a:B£Y {=4_{{= 55468468L794T;8© `{ªæ<:54= 654 6 ¸ ±4Q8®4¦¯ =8 Q J:¸K¼¥4{Q858¦:J:Q K §4hW 1. NP-. [4]. (. "!$#&%'%'()'*+,-. Hiroshima University. ). Graduate school of Engineering,. 4L ¨`ê94y4kjb&Y4z¼©( ªæx!54w6{Q §4Áh{®44øÁ®£;&¯°Q `¼.{ jYêQ:sÁ£t°®85ÁZ{68X?7 ï9 = ;b88Y4Z l ½4¾4¿ÁÀ / 012¼½:8W344ÇÁÈ?> x z z8NT?@48O::G4=4Y8H454 Mj6jù`:`47:494B?b4;8c44`:d894y4M8b8:h8L:z44L:<:b=4x854w k?68 ={Q:464}jaZ:~44`:T8y4Z:|bW ::=W:54=4Å8 {V4 `c4=?d8:`:Q:4M44;88Q:4B:444I84Z 647?M4;j> xL:4Y4b8l4mY · 4Y4a:`8l :Y:c{d8:h8Q:4?µ°¶4aT=4·4c4¸Ád8¹4e4º f4Qn4o8L 8 ¾4z:²4=4¿4´8À:48W4< W4c4=Qd8s494t4`:¾ 454:Á468Q:4G7:494M4;8;8`8L:8H4M?4k8NTJêÙ{YjK8D84L `:aT4ò4b5½ 64§4h44®4;8Q:Ä{Å8L:c4d4Æ4Ç4È8`88É4Ê4k8Y [7]. PC. PC. 2. ;=<. .. A CDFEH>@G ?B JILw KNMPORQ <=TS±7{BVUjxW£\¡B bx ¸ ë£G DWK aG X ý ë{aRDY ` k ?O £aa¢© R¡X í±Y{Y4lalZ°X K `=[b{O L£Zdm c£b z¡b°K]BI b Q R =^Q O_I ªfe Q 2.1. 1 −51−.

(5) ¸bdX{i Ml¯8k aùª i =gMLc£k m^bjK z:= bji Y±a[i Rk QÏ<ªhnSFS8b W£X£X4¯¤¢Z{z±i X R4Öù= b£j¯ QL j L $a I v MlojkpQ Rl= SFSbdb XYX8qrL i Mlqkts Ml<kts = a i `°© k°w l i5MLo4k L{Ù4m4D°$Q = XjedQ b u X8¸ W k\wjx Qb £W{X{Y±aùk±Y{l kx±z{Q$XjZdebVX ª m x a| TbeSb b$l:94X{²4¾¯°´8:4Q W4L:9£=8<:¾= m :4y8x L¡`\:g= xz?eFX4Tby?Z49£B: ¾ b8| :«7?94¾{fª Se:8bb a 9{X4v ¾ y?o8:¡l ¯ G `y4b±z= Xr} ~ i MlkpQïZ G dQ XjW eF b 4 9 ¾ : ý I XXx8} =8 @4= O°¸ < i ¸ a ¸k4ak X$< } ?< r!z:b8r:zêYjb8aTb4Y8b£a =b¸ ùl{i @a Ob& =Y¼a:¼ Q = 8XBÁ} Y X}L¡<} PM }l !Z r:zê&b8 Q Y&u aT¸ b L l S ¼r:zQ ¸ i Mli kêaR rz:b±Y8ax = jB4YdX} M} Zji a4R` k8w B4 Q X8E{:L = } ?Jý aTI b MlkpQ dl }LTXBJý } I Z4MlkpO Qï W4X{±Y8Q a¡¸ :=i L u ¸ a4r:z:b8Y8a::=4k8B4E4:=H} ý~I¶ i M i QÖQ8a::= XB} b 949±L¾¾:4 : LG¢ ¡ ?ý£CaTI¤bDK ¡ EM O l aT¡ QT b Z£ =Hl K ?¡R ¥ K X?©£¦R 8O @4¡ B ý ¡±° WÁXÁY°B w = § I i Mlk¨QVm©O«ª i m¬K ¡® ~ k ¯ m K Ga¡ < 94¾ : G ¡ CDJE a b4b4= Gd· K ¡ ¸ a¹4k°l Q K `8: Y ²³´¶µ 9 º ¾ : G ` y b z = ¸ â X H Q »©¼ t ý Ë Ð½ ÎJÑ ý ý Ë w kÄ¸ Ì Í ÎJÏZº k¿¾ÀM} ÁMlkp PMPÂÂPÂlMlkÄÃpÅÆ ÇM}ÈÃpMl¸ kÄÃ kÊÉVº Y8 laÖ?:=[rT½H= }ÈL ÉÖ×ý k IØ¾kÙÉÚ©ÅÛ ÇMÜkÄÉlQ k Ã Î¶w8ÏQ$Î¶Ó?Ñ >W4Ñ{QX ÔZ:Õ Ò{aTk8 b « YX84lL ¸Þ4_?k ¾ r:© O8w R:k Q4Ã w8L ß Q Ý8à¿4á â?J` aTk ¾ bMÜk Ã ÿl:L [4 \8u ¸½ ã8aTk8Q Ó Y L àÑá ä â?ÿ a4 a v rT=8o8m4l Q Ó?>: Z å4h?a:B4Y:[4\8 ½ ã8L º æ >:ß ¸ i Mlw k `»&G rz°R = i a 9{¾¸ : G `y b±z³= ¦¡Q ¬ k dL u a kj$Y Ýj¿ G Z Ò{k°Y{B w ¸ = V< ç¡Û¥ è±W{X Yjm x aT b ` l49{k8¾ Y:: kx8z{~ý Q I¤KNX8MPORL Qïé© {ê8Y8ë{4BD a:K L:= K#¸ ë a D a `4K k¡ Q l ëdì aùb£b¢í= é î ê :dO ïjQ 9 ¾ :{L Gñð K ¡ ò p8Q ¸ ë°DBK ¡ó¥ K `:»?rT=Hôaõ±Ð"ö÷I¤K ¡ Q ý §Èø m ¡Q ý K ð K ¡ ª¡ k m[K ¡ IØk¨M ø Q&m¡ O ° § aT° y8wê= ù ö I¤K x xªúôûõ±ôaÐ"ö÷õ±Ð I¤ö K IØkpQÈQ ªï=a õ ¹4ö IØkjkpQ l ay8¹{ ` k°K lTõ ýö IØkpkQïL B ¸ k³Q =&¸ üm h \a v o8l µýþ ÿ?a:<4X4Y{J:K8L:b?NT8x©4Q µ õ4ö8B{J K»?r:4z858 R J:nK 8`:`:5454M8M?L rù8=°P©:5{464í çÁ> è =jO$4m45jQ 8J:K8z4L` M?E:F4N4G°4H4a:I8W:Ò Jê8K8V4Q:S°` jU8Q4V:J:MÁK8;8L:W4M?XÁN4Y4l T8B:=4W C 8· DL

(6) x8Y4l 2. 2. 1. ,. 2. ,. 1. (. ,. ). (. ). 2. and. (. ). (. ). µ4¶4·4¸4¹{º m4x94:W4`:¾»4<:4: ²4k8Q ¸4´jY:4¹{Wº{M4a:;8<:49 =`:¾44: ¸b8Q:ë4Gz:D8ð4W4k8X4{Y .z:= òJ:K?p8Qa X Qu ¸ QW¡ ¢&¸°B ¹ÁN º a±R¡¶ÁS±· ø¼L¸4 ¹Áº R¢Q°W±X x¸4Y ¹4Y#(q º "1 = ¸ 2 !Q ¶±)·%l $& W±¸4X±Q ¶4Y · l±9 <ê¾= ±: QêG µ±`ñ¶±&·@ <O8a= := (4'¶ h8· GQ µ a:B4LY 4)¸ ¹4eº Lb×849 P4¾Y44: ZJ * v wTx J:K8 K&½¨W4¾ :XÁY°0l1 + 2QÁ3 J:K¼ª 4Æ<:ª658= ü 7Q¼9 `:9-4, I > x Y/. :;<= GHIJ 7K9LM4?@>AB@CBNCOD>EPF QR@ J LMS TVUXW#YKZ D[E]\]^`_aP NP-bKcDKE#F`dKefSAgVhXi W ^kv jm u |J Jwl xK[9]yPkzn`{o]Jpk|q}Kr~Skst i`^1, 2 KF [10-41]. }~J |K} SDEFe>Pu Je|}F~ ~ S7 ~J DEF`deS D h(i F i^ W FW de k F WYKZ J[8] A^ j J|K^k}P]~@ LM` SU #P@LD`M_S JY> Z 1 > 1P 2 J CLAP BARP NTP BEP NI U Pu i` ¦§K¨#©SkªK« i`^| j¬}l~ P ~ ®- ki¯ ¡#ef¢K¡£¢ ¤#z-¥`{° kh FACLA DEFe(ª« i^ W F . S]7±_³²´1-p 1: wxyz{J|}~ |} ¡¢Kµ ¶· ¸ ¹Xº¼»¾½¿»ÁÀÃÂÅÄÆ»¾Ç¿»ÉÈ [17] CLA 2 2 [11] BAR ¹Xº¼»¾½¿»ÊÈ ¹Xº¼»É½¿»Ã»¾Ç(» ËÌÈ 2 [35] NT ÍÏÎ À¾ÂÅÍ ÄÐÀÃÂÅÄ»¾Ç¿» ¹Xº¼»¾½¿»¾»¾Ç(»ÑÀ¾ÂÅÄÐ»ÉÇ³»ÊÈ [12] BE À¾ÂÅÄÐ»ÉÇ³» ¹Xº¼»¾½¿»ÊÈ 2 ÒÓÔÕÖ [38] PIT 2: @LMS JYZJwxyz{k|}~ |} ¸ ¡¢µ ¶· ÍÏÎ ØÅÙ × »¾½³» NI »¾ÇfØ » ËÛÚ × »É½³» ¹ÜºÝ»¾Ç¿»Ã»É½f»ÊÈ [34] ÍÏÎ Þ Ø º¼ßàÈ ¹ÜºÝ»¾Ç¿»Ã»É½f»ÊÈ [32] MS Ú f Þ â º¼ßáÈ »¾Ç¿»äãº Í Þ Ú Ù Èæåçº Í Þ Ú Í È èé 7K9 Jê 3 2.2. 3. 3 ëíìïîíðòñ óôõö >k÷ølúùøû(NOlúü JýKþ Sÿp F é Pü `Jé DP79KLM@BC. 2 −52−.

(7) .

(8) . . . J LM> 1: @BC ( J @ )

(9) . . 16. . . . 7 9-LM-@ BC ( J @ ) J (7- ~ ) kL M> 10 W J NO ^ óôõö ` F 3.1 J ûX ö iFKNAO ( d i "!KZ t"#K7K ` $ NO &e %('F ) )e + F * 0:;1<2=3 , .º - ÈÐ587é 92U J 7 5 $ -6_ /1%70 'P hXiF#Sk01PK3 4 D#> 8`hp W , º . È õ lú79 $ NO ùøûdek F { e <=Ai?P > õ@ Z é > d d k D P 4 > 9 : ; Z ê õ C @ A ¢KMLOBN @ ZP DJEKFõ" þDóQE @ Z e U ^õ G > FCH@ I ZT 3S J ° u > P > ¶ R ? hS]\Û(P V 2 J ¶ Rõ þ óXl @ WZ Y iF > õ Z ¶ R:#[;K<J @= Z & p _ADKEFK` 0#> :;<= aUé _ J ( @ Z eu U ^> P -b/10 d > c[S kè`é de AU ^ W F#De , º . È > f c1/Qâ 0 k U ê ^ ê 3Õ P ¤3Õ( g p _ 'F23@ DZ h P , 0 j 5 i( > , â 0Km 5 l (¤3 ) DEF 3 @ Z ) EF W k no 3.1 g ' hfi é G-H-T I p q ºÝÇaP ½XÈ J @ @ Z P r @ Z ui i Ç qs Ø uP tvtvtxw.Fzy P-k Ç â |KÇ q s º~} PuçÈa»} POh/ Çw}q y e F- ½ é {±Ph Ç 5 i ( ê 3 @ q Z ) >Ø Q @ / ÇVLU M ~º È g ' FJ 23DPê KMºx LOº N ÈæPJ tvt@ twvZ ºF È Èae Pb4 ^ FHI 3 J e F ddDP d q s q 0 - ~º c¼P tvtvtwc XÈ /`4 » c/ s P Ø y º Ø 1ã }Û ã FÆÈ U ° ^ J ~º P Þ È /#½ ^ d c Ú c ¢å ¡ Ø y e(j¤£ d J e¥79q LM#@BCNO> U 701934 :0;1<2=3 -, .º /1- È 0 P é ¦-258 ¸ iF -pj e P fS W ^ J § 1 e F J Y Z M K O L N F?HIJ SP t¨F7 9@BCNO DEF ©ª . 2:. F W £ °#J ¬b® ¢ U ^kj¯£f ±° % ] " D b « ¬ ² >P óô³ j(´F@ J deDElP óôõö 2j~W ° ^> þ ó NO°µ(¶ J~F½ ¾·¸(¹ºm»ú>P i^jh&¼[P u S¿(ÀÁh(i^ _ W pJ"ÉW#þ ó NAJ O KóÂ ô @`½D¾ E#FK ¢ÃÅÄÆQÇÈö >k P NkO Ê 3 c û ÀKD k\]^kÕSË i^ W p W ( EF W > <= óÌ ô ö ½S¾Í(JÎ Ï U ^ W J p W ) É 3 ö D i Eé F ( EKÄF ÆW Ç> È<K>= P Ì ö "S ÍÅÎ UAé K) É u 3`D#ÕEKS FKË ÐÑÒ >P aÓ~W ^ W F þ ó NOj W ^P01 J 7 5ÕDEF Ô ÑÒ >P aÓ ~23 W S^ ÷ø W F lú` þ ó FÕ NO j WÒ ^P0123Sk÷ølúFé J ÕÖ× 7J9ÕDKEF J ÕÆ >Pd(iDKJ"h(iÚ ö Õ û À#~ Dk7]9 ÕDKEl ØP ÕaÆ?ÓÙ~K>kW P u W þ Õó g ' F DEF ÛôÜM½Ý(¾>P Ú^ ö ~F NO W° ~ hdXi Ö J ó s K \ ^ _ l° _ JÞ ó#ô ½Sk¾ h(ip W deSt ° \ é YKZ Pud é ¢ ã ß3à7DáCEÈF >k. P óô h ½¾ _ U £> ¿( ô ÀCâ Ál F½dK¾e D#sEK\ F óK3.2ô õkä ö å>"æ¯H çJ è`é û U ^f¤Ks U ^ W £ ÀP8 hp W ½õ ¾ lú79 $ NO° e U ó^ ô ½ ¾F ìíVU P ~ S 9ê >óPë N O h ô ½¾ î ´FdeDEFK ddD ( h i F D J ð J Éñ Ë ö ½¾ e(Pu óô ½¾ e>kPïNO ¤ þ ó ié ½`¾ l NAO (òNO ) WY F ½Q¾kZ t # EóKFô õö J hD þ P ( 5 ¥ p ó ô D E k F P E F ó NO U ûi Ö J óô ½¾ ¿(ÀCÁF õ ö ½¾ S × Õ ¬ W ^stiF pK J ¡ × ÕS Ú ö ÕVl±5(¥ W e¥PEF W > × t Õ ÀP þ ó NO J 7 ~ S õh(i é e ¥>kPd Jþ ¢ D ó NO ° h J ui Ö J óô ½¾ >¿(ÀÁ`F d J ô â lúe WW P óô ½¾` s\^ Ú û(ö p ~ ½¾ WK _ W `lÞ ð ~ SAJ öhX÷i~ p W e Ì 8éDYK¥#Z F YKóZ ô P E¾F >udkD Sz h(iøù ½ { #F `JFúdKû eD> Pó¡ óô¿(õö ÀÁ ô ¢³ D t iP ë NO> J ü Pò`NO>ïNO Â @ý îV i ³ Â @KP ó# ô þÿ > ³ J ô ò Â @ é _AF`dFeXò P ô â l(SW é NkO> ³ J epF ð õF YZJ óô`õö J ¤ PK7 ~ é U P þ ó NO

(10) J ü 2 J ý ô â F l > J U ^ W J ÚFö ~ é PK¡ ¢~ Í(Î kP/phC=d e¥ SA7 DE l PÓXU Su W J 7ÕDEF q ph = ö÷~ > p ) s +*y P Ú ö Õ, ) P 7 1. " !$)/#&. % @ Z(' $ + ~ ( e1Z 0#Ó F ' 3 q 2 ' q @ 2. (; ) ph=¡¢Í¯Î . ph ó. 3 −53−.

(11) ô Â @ U 4 N # N NSR 5 W/' J v ° h þ ó NO J ÖQ × Õ8 U 7 69 ]¡ ¢ U 7 9 3úp h¢=kP1 ) 7 9 3. U e J P ° ~ Ú ö ~ _1: é ; FK <7 9 J ¡K¢``l J 7× S h(i ph= Step 7 =s¤£f 4. Õ7 > ¡]¢ F] ?7 > ¡ Ûp `h =fP Step s f £ 7 =¤ `l bP ° h J ó#ô ½¾ S ekp 5. ióô = ÉQStep ( ñ U 7 4 =N # N VSR ° h Éñ c l 6. U U @'3 P )/ ° 'G`h s ÞBA J òNO DC wtvttwv éFE 2 U W 1 Y é P DC wvttvtw DE yAe F Þ P ; q ¯ H Ø 'F òN]Þ O ° JJI Rq }DK (Ø è ã c ã )> P } K JQ }ML ' ( ã N]ã kc( N J$) I U P ° O H P J

(12) KRAi`"F òNkO RVeA>ÿ`pKF _' )/e ' Î Fs 7. yke1: ; U ÂP Step 2 = SF ©ª W éZY[V\XJ ]^`_baVU c(ódôk e õå ö 3.3 TVUX¯ 79L~ M@BCNO`> H û( ^ p l J £@ dZeS D¥ñ F J W ° @ @ H U 5(¥ @ &U h(É9 ñ (W @ q = Ø dw. wtvtvtxw.Ke PQkqk Æ c > @W ËB C J @ #Z ¯ H ' c >]@B-C J J Ö@ × Z HÅ× 'p dJe ¿7#9 LKMK@B#CNkO ÕKP Õ> H û(¡¢ F f × Õ ¡¢ * ó-ô ½ ¾ ]j ´-F#Q þ ó N]O g e b J v D-@ B C D J q G Ø H I h º c W È q Ë ö PV_ ö U U£é >A@iBg C °J @ Z ( H ' pö ºc È ó ek Ë p q @ q hØ jÍ k U ^Þ º Ç w ½ È uP } w w t t t w Fl m Y eZ prqFs é P»ÉÇÝñ» qoZn æprPq Q p Ð D J 7 5 H ñ 9 H prq s pr} qF e J F CJ !h]Z n ã t Jc YPZQ7-n P c P } F c^ # U Q p v J @#BC ñJ 7Kn 9Ê Õ F J Yõ Z > ^d(i h ` e ^ 7 j ¥ P Æ . ã t u U é n J Yd(Zi >P ¬ ^ F õ F - P wvx prq s qbn Î Ø J e¥ Ø F q »É½ »zy prqs c prq s cc qb nÎ Ø J e ¥ öD F d(i p J @ J 7 9LM { ´ é _ × Joq e J U é|q J} ~ þ ó Õ NO >P UAé @ J LK M J~ D e v J d @BKCû³ Ë ö ^ õ EF × Õ¡¢ * Ö× Õ>P þ ó NO J Ë ö Éñ f Ö @ Z U P 4 ÂJ ~ é > | }~ ¬ W ^F .. Yo@ VZ(V'% VJ Vv Z _ ó#oô VÂ VVþ Vó i ° "N !#&N % h U @ Ò ö ÉNñ` O J v U 4° ó #ô Éñ (NSR) \ ^ . U 4 P Ë é 0 hé U 4 ö N # N É(VSR) \ ^ b P ; > J 1 N Õ N Ë F ñW U 4 F `d(i w ñ J 9D # S. i ^ F S ó ¦ X e ¦ § ê@ 1p þ ó >W e V7_ËK\#^ W F`û(DEVl P [4] ó5ôY õö i ^ j W F^ >Pd(ih J U 4 N # N J! Z t # U ^P NO ~W ^_(Vh(iF ó ô³ J S É t\^ U û 5\^¡¢ ãñ P @ g ' é P U 4 N # N ¡J¢!Z z{ 6_ 5( ¥ p. t # óôõö j W ^L p ` e1( ' . ² º (NSR) 3.4.1 ° NSR H (a) (b) ¡ ¢ (a) Depth-First Node Selection £ ¤ £ (DFN)[4] ¥§¦ ¨ © ¤&ª¬« X ¸ ¹ º¼» ½bJ¾¿®"±1 ´b¯ À¼ Á °ÂÄ±Ã )² ÅÄ³Æ ´ Ç¼µ È¶ É (· ¢ Ê Ë ±1Ì ÉÀ Á ÂÃÅ Í Î ÏÐ ÑÒ Ó È É ¢ 3.4. £ ¨© ¤`ªÔ«bÕ®|¼¯b JÖ¼£V×¤i ¥ § ¦ Ø Ù ² ¡ Éµ ¶ ÅÆ Ç È É ¢$Ê Ë ±1Ì ÉÀ Á"Â Ã Å Ú1¤ Û ÑÒ Ó È É ¢ ÜbÝ Þ bß [1-3, 6] Jàbá ÅJâã1 µb¶¼Æ Çb£¼¤ £ ß DFN Åä ´ É . 3.4.2 å æ ç è é ê é (VSR) Á ë µ ¶ ÆÇ±1Ì É ì1 í ßî ïð ñ ò"¯ ó ñ ò Åbïð ÈôÉ õ ÅÄö ð÷Jø ãÌôù ø úÄø´ ¢ VSR Ñ ·´ û ßü ¹þý ÿ ÂÃÑ û ý ´ ñ É Ã

(13) Ñ ÷ûä È É ¢ Ù Â ¾ ¶ ÂÄÃ

(14) Ñ ¿÷û¼ßí (i) (ii) Åä ´ É . Ù (i) ² í¼ò¶ôÙ ÅÆbÇ¼È É (¿÷ íbòô Ñ

(15) ß ¾¶ ÅÆ Ç È É ) ¢ Ù ¾ ¶ ÅÆ Ç È É ¢ (ii) í ò ø É

(16) (b) Best Upper-Bound Node Selection (BUN)[4]. 4. ! "#%$&%')(%* !. Ù ¾ b¶ ÂÄÃôÑ

(17) bÈôÉ,+ -./1032546487:9<; = > @? 2 ACBÉ 2 @ > /GFIH ®ôK ì Ü J1M® LNý;PO ÿ QRSUT .C/WVNXZY · EÅ DE[= \È .C É ] Eø O; µ A + - . / O Q = > . /D

(18) ^_

(19) ` ß í D

(20) a ¹ A B É ] bc : dC à e fgUhijCkl0mKnporq:sIt?ì ¶ C@uò vw oy x{zM|{}~ ò ] c : ¶ Fo]. −54− 4.

(21) r5 (1) oy{o;00E o ;FK¢¡ . ¡ ¸ ÙA

(22) £ ¤ ÅE¥ ¹§¦ È : (2) om 76ÿ ¨ª© n«¬t? ¾D ¶®«

(23) ¯ 3 o Å$Æ@°A$í@D

(24) ±C²"Å³ ]

(25) ÷; í ò?

(26) ´ ÷1´ Ù ¶@?

(27) µ ò ¶ · È É

(28) ß

(29) ;¸«Z¹º D ¯ A ¶C ? ² D ¶ì1È É ] o o»¼n¾½p«À¿ Á ®7ÃÂ:¨r©Än«¬tÅtÆ;ÇFÈ FlÁ ®7ÃÂ:¨r©ÄnÉ«¬tÊ;0Ë{0 o . 4.2 ÌÍÎCÏÐ [17] (1) Ñ DÒ«C¯ o Ñ

(30) ÷;Ón«¬tº v n«¬t , ÔÕnÉ«¬tI 7 ¨ nÉ«¬t:] (2) FK¢¡ , o{o , sË{s] ¹§¦ È ¥ (3) sÀm¡ ìø É ¸ A í

(31) D. ± ² "

(32) Å ¥ Ü ×ÙØÛÚ ? Ù ¾ìJø É¼«¯@ “ Ö, o ÅJÆ Ý]PFÞFÁ ½p«À¿ ×Ù,ØÛÚÓn«¬tàß , oºIàoºË»á½¾«À¿ , sIsË» ½6n«ç qÄ«â täã<«â" ¯ ®M7Â:¨r©Än«¬t¾¿ . ¿ ÷;03mnporqås tæ]. è ¯®Mç 7Â ¨ª© n«¬t Ñéç O¼´ôûé;Ón ç têëÓç n ç t3» Ö,Ü ×ì×ÙØÛØÛÚ Ú , ÔÕn tíÔÕn tâ»ïç $î ì<È"É] ð ÷ÇÔÕn tñmKß ø úù

(33) ;oªo¬»½ ¿ ì1È É ] ” 4.3 ÌÍò Ð

(34) ó [11] o Ñ

(35) ÷;Ón«¬tí v nÉ«¬t:] (1) Ñ Dá«

(36) ¯¸| (2) FK¢¡;sË{s] ¹§¦ È ¥ (3) sÀm¡ ìø É ¸ A í

(37) D. ± ² "

(38) Å ¥ Ñ®n çõô q çö tí¯¸ÿs ÅÆCÝ@]ïÓn çõô tí÷øÓn çùö t “Ñ øôúJù®Â mèî6;ú ¼ A øbãJÌôù¼Âmü û ì¼÷Äû,; Fý çFÒÁ½ ç ¹ ¿ , sP ç sñ»þ½ÿn ç ¹ qÅ« tCã3«âé¯ ®7ÃÂ ¨r© n ¹:t¾¿å;

(39) Ó@Ë Ón ¹6?t çì È"ÉC]º| ÷;

(40) 0Àm n orqås t§A¼ B É] Ñé;Ón tàÓn ç t3»Ó@ (3møîZqåû ) ì1È É ] ”

(41) [38] 4.4 (1) FK¢¡Ë]¸sË{s] ¹§¦ È ¥ (2) sÀm¡ ìø É ¸ A í

(42) D. ± ² "

(43) Å ¥ ç qÅ«¬t¯s ÅJÆ Ý]éßé çt “ÑU. ¢ Ñ n ÷ þ÷ v n R v n«¬t»î ø ÉòÅ Ê± É]"Å é; v n ç t÷ v nÉ«¬t ì ÿ È É"] $# v n ç ?t øúJç ù ! FK{FÕÁí½p« ¿BìÄ÷º;ú AøÄã Ì"ùKF{FÁí½ ¿ ì1È É ] Ñ

(44) ;sË{sù»½Û46¿ ì1È É ] ” %& &123% A 506 4.1 (')(*+,-Ù .0/ ) 4 1 ú1Ìij k Ñ

(45) È É ¾ ¶C " ÂÃÅ786 É . ú Ì89Ì Ö× Ø;:<"Ñ¼032546487:9<;,FäH ® Å = 4 3; 4 ß$ ä÷

(46)

(47) D > ³ Ë ?@A B É ] ú Ì09Ì ; À Á ¹ ÂÃ Å 8 @"¸ ß 4 @ Ê ¹ ÈbÉìA>C³@? B8Cb÷$ûO 1; Ö ×Ø):<D/ Ñ " :<FEò?HG"øÉ0I ì?ÁõÉ] 4.1. U L. V WSXSO V P Y XSO. JLKNMPONQSRUT. 1 U=15 L=6 < 13. U=15 L=10 < 13. bfcAdPe ] U=15 L=15. 1. 8. 7 0. e. 3. 4. Z\[S]_â`. ZS[S]m^"`. 6 0. b. bfcAdPe ] U=13 L=13. 0. d. 2. 1. 0. c. 1. 1 U=15 L=10 < 13. U=13 L=2 < 13. 0. bPcAdfe ] gih\j ]Uk U=10 JlKNMSO\QSRUT. 5. L=10. 4 3: Ö× Ø:<"Ñ®0N2548487: 9 Åä ´ U D Á ë8nð / D. > ³ ? ] . o ÷ ;. p 0 ¶. q D r. s ß À. Á ÂÃDt uvw Ñ

(48) x È É U L. P\| f \|. yLzN{P|N}S~N. 1 U=14 L=6 < 10. PUP iS U U=10 L=10. U=10 L=2 < 13. 0. 1. c. 1 d. 0 4. 0. 2. 3. \ Pma. \ Pma. 4 4: Ö ×Ø:)< Ñ®FIH ®Åä ´

(49) D$Á ë8nð u/ D >w ³?]o ÷;p ¶0q Drs ßÀ Á"ÂÃDt v Ñ

(50) x È É. 5. . . Ù5.1¾Køô ¶øQÂ¼ÃQÑ ôÈQÉ¡ ôÁôë¢n ðK/¿Å 100Base-TX D»¤ ) º £¡ Ï ¤íAà8÷ ( 4 6 ¥)¦ )12 @D 8 Û §m¨Ï º } CPU:Pentium II 450MHz õ ú Penõú 1GBõúJø tium III 500MHz; ©!ª¬« :800MB É :)<®)£8 Ï ¤U¯<¤"ÐÖ ( :)<®@D OS ß FreeBSD 4.3-RELEASE) Ñ C °± Åä ´ û >²

(51) ÷ ] ³ Ñ ß MPI[5] Åä ´ ] µ¸·$¹¶º»$¼ Ù5.2¾´¶ ¶8ÂJÃDC^`KiUjk 0{m n orqåsät<ôßé¹ ; ã oêãrm®û ß q¾½ ßZq¾¿ ß q¾À ß q:î ß6ß

(52) Ñ ¿÷éû ; íD!Á /Ñ ú0 Ì 9Ì 10 @ (Â ò 50 @ ) D Ë i j kbÅÊ Ë ÷

(53) Ü : ¶ ò DÃ Å jÄÅÇÆ ÑJÊ Õ÷ ;ßÉÈ ûãìoãÊÇî D Ë ?èãìoãùË Å Ì ÍÏÎÐ £ ¹ ¤ Û

(54) Å ²úø´ ÿ Ñ jÄÅÆ Ñ ÑÒ È É ] (·"¸ ;UãìsãâmKîÉÈ ûãìoã¾UîIA B É ] ) 5.3 ÓÔ¸ÕÖ :<®D× ò ÅÙØìOÛÚ]. 5 −55−.

(55) D 1 12 / ° Ô'ÖØ× 3Ùv d @A æ T def # t f ó1ô2#hi ñ U / )DL #Ò1 ÓMõ Ï y ) #ön¾÷o:pqpq#r ø D#Lhi bU c k ùúû ¬ ü#ý k )L bc 3 æ T )$LÞ D w bx c#æ 2 T .# 0 1þ wx / ° û ¬üÿý B*fe h*i U g Ý ¡ e Ú'èë*ìk U3!ÿ" D Ú )* *L 3Ù v D ¤gy ëì g#« ° & D 12#ñ /0

(56) C00(ROOT) C01(WORKER1) C11(WORKER11) 6 100Base-TX åAæPçNèAéêëíìïîñð , A ñ#ÞSÙ # , D S | aD ùúû ¬güý k 3 PC EFGH 4 5: ò Íó0ÆôõD

(57) [ö 1ý)þ ! Í E h , §"d!#Ê N }ËÌÍÌ #hi U )L ÷) øù) [.

(58) ú û)üû] ÿ 3; 4 5!#)4"%$'6 &( *)ÿ+ )Lbc$ f /. D&%(' 3&) D / 3* ô + j k 5 7 4 8 6 : 4 < 9 > ; > = ? = #. @ A 1 # 2 3 , §- wx / ° #Ê N }ËÌÍÌ $ Bf e ,-./0 3 )L M#N #OP . SM T{ #| #}Ë #B CD PC EFGHJÿ I #K ÿ PC N *| 3R}Ë ( #d!S # { N '1@0A ¡ $ . D1 # 5 7 4 8 6 Q 4 % 9 > ; > = ? = #. @ A. R B C D Û # J S ÿK 4 EF HIX#& 2 f z wx #« ° & )/ STU ÿ 5(1)PC G W#& + Ú)JL bc PC (5) ) L M N V 2 #hi U )Ljk , # ¡ e Ú y Y 9Z;\[^]\[^_\[^`\[^;>] #a D )L bc 3 %d#e#fgD . Bhi U )Ljk lm kno:pqpsrut 3#v f ef D ý 56 ° & D lm 3#Ùv d #¤ wx ÿ 5 y z (i) ST{ N #| 3#}~ ( d ëì3$54 50¡ . D 2 f z wx #k« ° & + { N @A S g |3}~ ) f w )L,7 bc 58 # { 59 , D + x 3 d#e#f D | # #Bf e D |3 |A # D 2#W #| #{ N # 3 (1) PC EFGH )L:;N f @A # Df | N 5 f @A ó<§- + D 12# ,- W#& 3 12 y F K w F # $¡ . D { N #T - f | |# ÒÓ k3$ y« ° & 3#} ¢£#¤ y ¥%¡# F # K w F # (2) S Ò Ó #SÙ2 5= aó< . # $¡ . ¥¦ # §¨©ª 3#« e#¬ ® D (i) f wx 3 %defgD 2'¯ ° & D >?@A [±²³´ ] » 6g 7 8# 9g10 ¶ u·

(59) ¾¸ ¹#º ¿ ¼ !"$'7 & [1] T. Watanabe, S. Kajita and K. Onaga, “Experi » µ ½ ( *)+ ,-./0 123 » » 6 8 W#&X mental evaluation of node/variable-selection and loadbalancing strategies in parallel branch-and-bound algo&À47684:9<`>= 47684:9Á;Â=>=? @A #B CD PC EFG rithms for solving 0-1 knapsack problems on a trans K. #OP W#&X#& puter network”, Transputer/Occam Japan 4(S. Noguchi and H. Umeo (Eds. )), IOS PRESS, Amsterdam, pp. 4ÄH6?I 4Å9Æ`Â= PC47684Q)9ÆL ;>M=Â=?N #@A #Ã»BÇC7D 9PC EFGH 102–119, W [2] B C , D&E 1992-06. I&X *& K Y PC9Ç ;>[q)]>[qLÇ_>[qM#`>[qN ;s] #SaTJ U D » 10(1)3 V È(5)d FHG&I “ JLK&MNOQPSRTVUXWYJ[Z\RY]H^ _à 0-1, bc ef W\d\efWS]Hg\hYiVj&kYl\mHno ”IpHq & r s ) L b c D . B hÉ wx / °Ê N }ËÌÍÌ (i) S , NA37-9, pp. 67–74, 1991. T{ N |g3}Ë D ( d { N @A [3] tv_u `&,aSDv|HE } , FvGI “wVx 0-1 byW[dQecr&W[s ]zj{kYlQmvoY^ I~H&& ”I(pHq , CPSY89-49, #S #| 3#}Ë D ) 3#v f e#f D pp. 25–31, 1989. yÇ 47684Î9Ï;>=Â= Y 9Æ;>]8 *@JA *BfÇe \fH » h8 i 9U )L RÐÑÒÓ kÕÔ'ÖØ× 3#Ùv D 1 [4] & && I I&“H&&Y&VHo &8 H”RIj&&kYl\Vm oy, 1980. 2 y O )JL M*NÚ K PC )LÛM#N #STU [5] P.&¡&® ¢Y ¤¦¥ , §&¨©HI “MPI w&xydª&«&KY¬VM&« ”, ¯ I£2001. ÚÜd Ý / $d Þ D 12# ,- 3R ÙJ v d #@JA O [6] T ° KajitaI “Evaluations of Parallel Branch-and-Bound Algorithms for Some Combinatorial Optimization Probàß ? â × á àã ¾ \ ä å ) K. #. S T U È # d # e f D ³H´&q lems µ&¶&·Hon¸&a¹HTransputer º&»&¼½HNetwork“ ¾ s ´&q&¿HIÀ&uÁ ±V¹&²&Â&qHÃ ²&I q&1992. L M#N Ú y D PC2 )L M# N Úæ y _X` “PC ]ÅKÅN5TVwÅx&jÅkXl\mÅnÅo^ f[8] 3!#" d#çÔe#èB Öé× ÒßÓ ×êá¾ àãk #ä\åí ª #îÚïëì #O [7] a\C5ÆÄ }&, DÅÇ EÅ~&I H È&ÉYiVÊË&ÌÍ ”I IEICE Technical . î ï 1 2 ñ a È ð # d e f D D / Report COMP2003-7, pp. 47–54, 2003. )y L MN 9ò;>]' #@A #Bf e 3Ùv d #» @10 A [8] Î&Ï , C&Ä , DHE , “&Ð&ÑHÒ }HÓ&Ô gVh^VÕ&Ö aV×&Ø Y ' Ô Ø Ö × nä oYiSÊ&ËÙÚÛ&ÌÍ ”, Ü 16 ÝÝSÞfVßNSàYá\âã O )L M#N ÜÝ d Ú // ñ ° ( )L bc Z\Ry]&ßyåæW\d , pp. 507–512, 2003. ÜPÝHÞàßmá\âàã_ä. 6 −56−.

(60) [9] M. R. Garey and D. S. Johnson, “Computers and Intractability: a Guide to the Theory of NPCompleteness”, Freeman, San Francisco, 1979. [10] E. M. Arkin, M. M. Halldrsson, and R. Hassin, “Approximating the tree and tour covers of a graph,” IPL, pp. 275–282, 1993. [11] R. Bar-Yehud and S. Even, “A linear time approximation algorithm for the weighted vertex cover problem,” J. Algorithms, Vol. 2, pp. 198–203, 1981. [12] R. Bar-Yehuda and S. Even, “A local-ratio theorem for approximating the weighted vertex cover problem,” Analysis and Design of Algorithms for Combinatorial Problems, pp. 27–46, 1985. [13] N. Bshouty and L. Burroughs, “Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem,” in Proc. 15nth Ann. Symp. on Theoretical Aspects of Comput. Sci. LNCS, pp. 298–308, Springer-Verlag, 1998. [14] J. Chen and I. Kanj, “On approximating minimum vertex cover for graphs with perfect matching,” in International Symposium on Algorithms and Computation, pp. 132–143, 2000. [15] J. Chen, I. Kanj, and W. Jia, “Vertex cover: Further observations and further improvements,” in Workshop on Graph-Theoretic Concepts in Computer Science, pp. 313–324, 1999. [16] J. Chen and I. A. Kanj, “On constrained minimum vertex covers of bipartite graphs: Improved algorithms,” in Graph-Theoretic Concepts in Computer Science WG’01, A. Brandstädt and V. B. Le, Eds. Vol. 2204 of LNCS, pp. 55–65, Springer, 2001. [17] K. L. Clarkson, “A modification of the greedy algorithm for vertex cover,” IPL, Vol. 16, pp. 23–25, 1983. [18] T. Fujito, “A note on approximation of the vertex cover and feedback vertex set problems - unified approach,” IPL, Vol. 59, No. 2, pp. 59–63, 1996. [19] T. Fujito, “Approximation algorithms for submodular set cover with applications,” IEICE Trans. INF. SYST., Vol. E83-D, No. 3, pp. 480–487, Mar. 2000. [20] M. K. Goldberg, T. H. Spencer, and D. A. Berque, “A low-exponential algorithm for counting vertex covers,” Graph Theory, Combinatorics, Algorithms, and Applications, Vol. 1, pp. 431–444, 1995. [21] O. Goldreich, “Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs,” ECCC Reports TR01-102, Electronic Colloquium on Computational Complexity (ECCC), 2001. [22] T. F. Gonzales, “A simple LP-free approximation algorithm for the minimum weight vertex cover problem,” IPL, Vol. 54, No. 3, pp. 129–131, 1995. [23] E. Halperin, “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs,” in Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2000. [24] J. H˚astad, “Some optimal inapproximability results,” in Proc. 29th ACM Symp. on Theory of Computing, El Paso, pp. 1–10, 1997. [25] D. S. Hochbaum, “Approximation algorithms for the set covering and vertex cover problems,” SIAM J. Computing, Vol. 11, pp. 555–556, 1982. [26] H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns, “Nc-approximation schemes for NP- and PSPACE-hard problems for geometric graphs,” J. Algorithms, pp. 238– 274, 1998.. ç. »ê. } ËÌÍÌ (4Ä6?4 ò 9 ;>=>= ) è3é O Ê N ) L M#N ë ì í î ïë ì 3:. (i) 353134 359328 365848 434580 413128 (ii) 11970695 12609898 10913486 9982364 7135929. Ê N }ËÌJÍÌ ( 4764 9<;Â=>= ) è3é PC EFGH K IA é 2 PCó é#)L M#Nðé STUð+5ñò I Y 9%; é @ ê é ë í ëïì ». 4:. (i) 353134 146048(2.4179) 62114(5.6852) (ii) 11970695 3700799(3.2346) 968768(12.3566). [27] M. Karpinski and A. Zelikovsky, “Approximating dense cases of covering problems,” Tech. Rep. TR97-004, ECCC, 1997. [28] M. Karpinski and A. Zelikovsky, “Approximating dense cases of covering problems,” Electronic Colloquium on Computational Complexity (ECCC), Vol. 4, No. 004, 1997. [29] S. Khuller, U. Vishkin, and N. E. Young, “A primal-dual parallel approximation technique applied to weighted set and vertex covers,” J. Algorithms, Vol. 17, No. 2, pp. 280–289, 1994. [30] S. Khuri and T. Bäck, “An evolutionary heuristic for the minimum vertex cover problem,” in Genetic Algorithms within the Framework of Evolutionary Computation – Proc. of the KI-94 Workshop, J. Hopf, Ed., Saarbrücken, Germany, pp. 86–90, 1994. [31] J. Kleinberg and M. X. Goemans, “The lováz theta function and a semidefinite programming relaxation of vertex cover,” SIAM Journal on Discrete Mathematics, Vol. 11, No. 2, pp. 196–204, 1998. [32] B. Monien and E. Speckenmeyer, “Ramsey numbers and an approximation algorithm for the vertex cover problem,” Acta Inf., pp. 115–123, 1985. [33] R. Motwani, “Lecture notes on approximation algorithms: Volume I,” Tech. Rep. CS-TR-92-1435, Stanford University, Department of Computer Science, 1992. [34] H. Nagamochi and T. Ibaraki, “An approximation of the minimum vertex cover in a graph,” Japan J. Indust. Appl. Math., pp. 369–375, 1999. [35] G. L. Nemhauser and L. E. Trotter Jr., “Vertex packing: Structural properties and algorithms,” Mathematical Programming, Vol. 16, pp. 232–248, 1975. [36] R. Niedermeier and P. Rossmanith, “Upper bounds for vertex cover further improved,” LNCS, pp. 561–570, 1999. [37] C. H. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,” J. Comput. System Sci., Vol. 43, pp. 425–440, 1991. [38] L. Pitt, “A simple probabilistic approximation algorithm for vertex cover,” Tech. Rep. YaleU/DCS/TR-404, Department of Computer Science, Yale University, 1985. [39] Y. Saab, “Iterative improvement of vertex covers,” IPL, Vol. 55, No. 2, pp. 95–98, 1995. [40] C. Savage, “Depth-first search and the vertex cover problem,” IPL, Vol. 14, pp. 233–237, 1982. [41] A. Srinivasan, “Improved approximation guarantees for packing and covering integer programs,” SIAM Journal on Computing, Vol. 29, No. 2, pp. 648–670, 1999.. 7 −57−.

(61) } ËÌÍÌ è3é#)L bc (óôöõø÷ » 5: Ê N Y 9Z; ù ïì ú íûú (1) üïú îïú ëïúïú (i) 0.007 0.017 0.275 2.406 23.422 (ii) 0.007 0.043 9.039 803.466 9Z117.217 ] (2) Y ù ìïú íûú üïú îïú ëïúïú (i) 0.008 0.032 0.353 2.376 23.215 (ii) 0.010 0.058 10.042 691.703 9Z102.564 _ (3) Y ù ìïú íûú üïú îïú ëïúïú (i) 0.017 0.023 0.323 1.962 17.708 (ii) 0.010 0.049 6.567 446.277 9Z61.400 ` (4) Y ù ìïú íûú üïú îïú ëïúïú (i) 0.021 0.042 0.182 0.862 13.522 (ii) 0.028 0.069 3.266 9Ç;>39.062 ] 253.731 (5) Y ù ìïú íûú üïú îïú ëïúïú. ». ). Greedy CLA BAR PIT. ù. Greedy CLA BAR PIT. ù. Greedy CLA BAR PIT. ù. (i) 0.061 0.079 0.216 0.656 10.231 (ii) 0.082 0.105 1.953 31.506 167.862. ». 6:. Greedy CLA BAR PIT. Ä4 6è4 9ò`>= é O )L M#N hi U ê ) Lë jk ì ( í ) è3 î ëïì Greedy CLA BAR PIT. 43580 40103 55637 51925. 39423 40984 51093 51764. 40116 40550 51362 47016. 31603 32013 41727 35087. ù. 28699 30718 36828 31087. ýÿþ. Ä4 6?4 9ò`>= ) è3é PC EFGHI » K 7: hi U ) Ljk (S T Uð+5ñò I Y 9%; é @ é 2 PCó é#)L M#Nðé A é ê ë í ëïì Greedy CLA BAR PIT. 43580 40103 55637 51925. 17869(2.4388) 19531(2.0532) 23222(2.3958) 20934(2.4804). 0.017 0.103 0.042 0.027. ìïú. (2). 0.032 0.100 0.050 0.038. ìïú. (3). 0.023 0.081 0.050 0.028. ìïú. (4). ìïú. 0.353 1.578 0.635 0.474. 2.376 23.215 11.360 4.764 66.568 3.421 42.084. 0.323 1.148 0.500 0.382. 1.962 17.708 7.573 3.423 42.368 2.510 28.869. 0.182 0.578 0.262 0.191. 0.862 13.522 2.939 1.305 28.184 0.973 19.867. 0.216 0.437 0.231 0.179. 0.656 2.120 0.987 0.764. Y 9Ç_ íûú üïú. 0.017 0.018 0.008 0.010. 0.061 0.092 0.084 0.089. 2.406 23.422 12.040 5.477 81.378 3.698 52.647. Y 9Ç] íûú üïú. 0.008 0.009 0.014 0.011. 0.021 0.060 0.034 0.042. 0.275 1.692 0.607 0.427. Y 9Ç` íûú üïú. 0.042 0.079 0.049 0.049. îïú. ëïúïú. îïú. ëïúïú. îïú. ëïúïú. Y 9Ç;>] íûú üïú îïú. (5). 0.079 0.112 0.110 0.103. ëïúïú. 10.231 33.067 19.205 13.635. (sec). (i) (ii) 100. 10. 1. 0.1. . V. . V. ¼ 6: Ê N }ËÌÍÌ è3é)Lgbc ( Y 9Ç;Â] ý# ó ôöõø÷ ) 0. Greedy 353134 359328 365848 434580 413128 CLA 392433 BAR 719509 673788 679658 782872 658357 PIT 605062 441850 568256 633961 532472.

(62) . 20. 40. 60. 80. 100. (sec). 100. 10. hi U )LJjk ( 47684 9%;>=Â= ) è3é PC EFGH K IA é 2 PCó é#)L MRN3é STJU3+5ñò I Y 9%; é @ êé ë í ëïì 9:. Greedy 353134 146048(2.4179) 62114(5.6852) CLA 59258( - ) BAR 719509 250908(2.8676) 93041(7.7332) PIT 605062 204590(2.9574) 77995(7.7577). Greedy CLA BAR PIT. 0.007 0.007 0.007 0.007. ). 1000. 4245(10.2661) 4448(9.0159) 5220(10.6584) 4619(11.2416). 9 ;>=>= ) è3é O » 8: ê hi U ) Ljk (4Ä6?4 ò ) L M#N ë ì í î ïë ì. ». hi U ) Ljkè39Ç é#;)L b c ( ó ôöõø÷ Y ù ìïú (1) íûú üïú îïú ëïïú ú. 10:. Greedy CLA BAR PIT. 1. 0.1. ¼ 7: hi U Ljkè3é ôöõø÷ ) 0. 8 −58−. 20. 40. . 60. Lgbc Y 80. 100. ( . ý# ó.

(63)