В.Б. Алекссев - Сложные алгоритмы (1132790), страница 12
Текст из файла (страница 12)
tAKKAK ZADA^A nm NP -POLNAQ I wp 2 NP , TO I ZADA^A wp NP -POLNAQ.oPREDELENIE. cIKL W GRAFE, PROHODQ]IJ ^EREZ KAVDU@ WER[INU ROWNO 1 RAZ, NAZYWAETSQ GAMILXTONOWYM. gAMILXTONOWOJ CEPX@ NAZYWAETSQ NEZAMKNUTAQ CEPX, PROHODQ]AQ ^EREZ KAVDU@ WER[INU ROWNO1 RAZ.zADA^A O GAMILXTONOWOM CIKLE (gc).wHOD PROIZWOLXNYJ GRAF G.:..::..-.:59.wOPROS ESTX LI W G GAMILXTONOW CIKL?lEMMA. gc 2 NPdOKAZATELXSTWO dLQ DANNOGO GRAFA G S n WER[INAMI SERTIFIKATOM QWLQETSQ POSLEDOWATELXNOSTX WER[IN (v1; v2; : : : ; vn). aLGORITMPROWERKI SERTIFIKATA DOLVEN UBEDITXSQ, ^TO W \TOM SPISKE STOLXKOVE WER[IN, SKOLXKO W GRAFE G, ^TO WSE ONI RAZLI^NY I ^TO DLQ WSEHj = 1; 2; : : : ; n ; 1 W GRAFE G ESTX REBRO (vj ; vj+1 ), A TAKVE ESTX REBRO(vn; v1). wSE \TO MOVNO WYPOLNITX ZA POLINOMIALXNOE WREMQ.tEOREMA.
zADA^A gc NP POLNAdOKAZATELXSTWO pOSTROIM POLINOMIALXNOE SWEDENIE ZADA^I3-wyp K ZADA^E gc. rASSMOTRIM 2 WSPOMOGATELXNYH GRAFA: -GRAFI -GRAF, IZOBRAVENNYE NA RIS. pUSTX -GRAF QWLQETSQ PODGRAFOMNEKOTOROGO GRAFA G, PRI^EM S DRUGIMI WER[INAMI GRAFA MOGUT SOEDINQTXSQ TOLXKO WER[INY A1; A2; B1; B2 , I PUSTX W G SU]ESTWUETGAMILXTONOW CIKL. nETRUDNO PROWERITX, ^TO ESLI \TOT CIKL WHODITWNUTRX -GRAFA, TO ON OBQZAN SRAZU OBOJTI WSE WNUTRENNIE WER[INY-GRAFA.
pRI \TOM, ESLI ON WHODIT ^EREZ WER[INU A1, TO WYHODITOBQZATELXNO ^EREZ B1 I NAOBOROT. aNALOGI^NO, ESLI ON WHODIT ^EREZA2, TO WYHODIT ^EREZ B2 I NAOBOROT. pO\TOMU USLOWNO MOVNO S^ITATX,^TO -GRAF IMEET WSEGO 2 REBRA A1B1 I A2B2 I TREBUETSQ, ^TOBY CIKLPROHODIL ROWNO PO ODNOMU IZ NIH.pUSTX -GRAF (RIS.) QWLQETSQ PODGRAFOM NEKOTOROGO GRAFA G,PRI^EM S DRUGIMI WER[INAMI GRAFA G MOGUT SOEDINQTXSQ TOLXKOWER[INY P I S .
eSLI GAMILXTONOW CIKL WHODIT W -GRAF ^EREZ P ILIS , TO ON DOLVEN SRAZU OBOJTI WSE WER[INY \TOGO -GRAFA (I WYJTI^EREZ DRUGU@ WER[INU PARY P; S ).w -GRAFE (RIS.) 3 PRAWYH REBRA PQ; QR I RS BUDEM NAZYWATXOSNOWNYMI, A WER[INY P I S | GRANI^NYMI.lEMMA. nE SU]ESTWUET GAMILXTONOWOJ CEPI W GRAFE IZ WER[INY P W WER[INU S PROHODQ]EJ PO WSEM TREM OSNOWNYM REBRAM PQ; QR; RS dLQ L@BOGO DRUGOGO PODMNOVESTWA OSNOWNYH REBERWKL@^AQ PUSTOE PODMNOVESTWO SU]ESTWUET GAMILXTONOWA CEPX IZP W S PROHODQ]AQ W TO^NOSTI PO \TOMU PODMNOVESTWU OSNOWNYHREBERpERWAQ ^ASTX \TOJ LEMMY O^EWIDNA, DLQ DOKAZATELXSTWA WTOROJ^ASTI DOSTATO^NO RASSMOTRETX WSE WOZMOVNYE SLU^AI I W KAVDOM POSTROITX SOOTWETSTWU@]U@ GAMILXTONOWU CEPX (POSTROJTE).pUSTX A | ALFAWIT ZADA^I 3-wyp.
kAVDOMU SLOWU a 2 A MYSOPOSTAWIM GRAF G TAK, ^TOBY W G SU]ESTWOWAL GAMILXTONOW CIKL:..-..-,-.(-),.60TOGDA I TOLXKO TOGDA, KOGDA a | WYPOLNIMAQ 3-knf. eSLI a 2 A I a| NE 3-knf, TO SOPOSTAWIM a GRAF G S DWUMQ WER[INAMI I 1 REBROM.o^EWIDNO, W NEM NET GAMILXTONOWA CIKLA. pUSTX TEPERX a = K = D1 D2 : : : Ds | PROIZWOLXNAQ 3-knf S PEREMENNYMI x1; x2; : : : ; xn. pUSTXH1; H2 ; : : : ; Hs | -GRAFY S GRANI^NYMI WER[INAMI Pj ; Sj . sOEDINIMREBRAMI WER[INY Sj I Pj+1 DLQ j = 1; 2; : : : ; s ; 1.
pOLU^ENNYJ GRAFOBOZNA^IM G1. ~EREZ G2 OBOZNA^IM GRAF S WER[INAMI C0; C1; : : : ; Cn,W KOTOROM DLQ KAVDOGO i ESTX 2 REBRA (Ci;1; Ci ) I NET DRUGIH REBER.wER[INU P1 GRAFA G1 SOEDINIM REBROM S C0, A Ss SOEDINIM REBROM SCn. iZ DWUH REBER (Ci;1; Ci ) ODNO SOPOSTAWIM PEREMENNOJ xi, A DRUGOE| xi . pERWOE OBOZNA^IM e1i , WTOROE e0i . w KAVDOM PODGRAFE Hj OSNOWNYEREBRA Pj Qj ; Qj Rj ; Rj Sj SOPOSTAWIM LITERALAM tj;1; tj;2; tj;3 DIZ_@NKTADj . pUSTX LITERAL xi WSTRE^AETSQ W k DIZ_@NKTAH Dj I W PODGRAFAHHj LITERALU xi SOOTWETSTWU@T k REBER e1; e2; : : : ; ek . mEVDU REBROMe1i = (Ci;1; Ci ), SOOTWETSTWU@]IM xi, I KAVDYM IZ REBER e1; e2; : : : ; ekWSTAWIM SOEDINITELXNYE REBRA TAK, ^TOBY OBRAZOWALOSX k -GRAFOW.tAK POSTUPIM DLQ WSEH xi .
aNALOGI^NO POSTUPIM DLQ WSEH xi S ZAMENOJe1i NA e0i . pOLU^ENNYJ GRAF OBOZNA^IM Gk .lEMMA. w Gk ESTX GAMILXTONOW CIKL TOGDA I TOLXKO TOGDAKOGDA knf K WYPOLNIMAdOKAZATELXSTWO pUSTX W Gk SU]ESTWUET GAMILXTONOW CIKL W .pO SWOJSTWAM -GRAFA (SM.WY[E) MOVNO USLOWNO S^ITATX, ^TO GAMILXTONOW CIKL PROHODIT ROWNO PO ODNOMU IZ REBER A1B1 ILI A2B2 -GRAFA.sLEDOWATELXNO, MOVNO S^ITATX, ^TO CIKL W SNA^ALA PROHODIT POWSEM WER[INAM PODGRAFA G1, POTOM PO WSEM WER[INAM PODGRAFA G2,PRI \TOM WYPOLNQETSQ TREBUEMOE SWOJSTWO DLQ KAVDOGO -GRAFA. dLQKAVDOJ PARY REBER e0i ; e1i W G2 CIKL W , O^EWIDNO, DOLVEN PROHODITXROWNO PO ODNOMU IZ \TIH REBER. dLQ KAVDOGO i POLOVIM xi = 0, ESLI WPROHODIT PO e0i , I xi = 1, ESLI W PROHODIT PO e1i . pOLU^ENNYJ NABOROBOZNA^IM ~ = (1; : : : ; n ). rASSMOTRIM ODIN IZ PODGRAFOW Hj W G1. pOLEMME GAMILXTONOW CIKL W NE PROHODIT PO KRAJNEJ MERE PO ODNOMU IZOSNOWNYH REBER PODGRAFA Hj .
pUSTX \TOMU REBRU SOSPOSTAWLEN LITERALt S PEREMENNOJ xi. eSLI t = xi , TO \TO REBRO SOEDINENO -GRAFOM S e1i ,ESLI t = xi, TO S e0i . tAK KAK PO DANNOMU REBRU CIKL W NE PROHODIT,ON DOLVEN PROHODITX PO e1i , ESLI t = xi , I PO e0i , ESLI t = xi . iZWYBORA i POLU^AEM, ^TO W L@BOM SLU^AE t(~) = 1 I, SLEDOWATELXNO,Dj (~) = 1. pOSKOLXKU \TO WERNO DLQ WSEH j , TO K (~) = 1, TO ESTX knfK WYPOLNIMA.oBRATNO, PUSTX knf K WYPOLNIMA I K (~) = 1, GDE ~ =,..61(1; : : : ; n ).
pROWEDEM CIKL W PO PODGRAFU G2 TAK, ^TOBY DLQ KAVDOGOi = 1; 2; : : : ; n ON PROHODIL PO e0i , ESLI i = 0, I PO e1i , ESLI i = 1. tOGDAPO SWOJSTWAM -GRAFOW CIKL W NE MOVET PROHODITX PO OSNOWNOMU REBRUPODGRAFA G1, KOTOROMU PRIPISAN LITERAL t, TAKOJ, ^TO t(~) = 1, IOBQZAN PROHODITX PO OSNOWNOMU REBRU, ESLI EMU PRIPISAN LITERAL t,TAKOJ, ^TO t(~) = 0. tAK KAK Dj (~) = 1 DLQ WSEH j , TO W KAVDOM PODGRAFEHj SU]ESTWUET HOTQ BY ODNO REBRO, TAKOE, ^TO DLQ SOOTWETSTWU@]EGOEMU LITERALA tj WYPOLNQETSQ tj (~) = 1. sLEDOWATELXNO W KAVDOMPODGRAFE Hj SU]ESTWUET ODNO, DWA ILI TRI OSNOWNYH REBRA, TAKIH,^TO CIKL W NE DOLVEN PO NIM PROHODITX, I DOLVEN PROHODITX POOSTALXNYM OSNOWNYM REBRAM. pO LEMME W KAVDOM Hj MOVNO POSTROITXGAMILXTONOWU CEPX, UDOWLETWORQ@]U@ \TIM TREBOWANIQM, I W CELOM WGRAFE Gk MOVNO POSTROITX GAMILXTONOW CIKL.
lEMMA DOKAZANA.pROWERITX, QWLQETSQ LI SLOWO a 2 A 3-knf, I POSTROITX GRAFGk , ESLI a = K | \TO 3-knf, MOVNO ZA POLINOMIALXNOE (OT DLINY a)WREMQ. pO\TOMU MY POLU^AEM POLINOMIALXNOE SWEDENIE ZADA^I 3-wypK ZADA^E gc. tAK KAK ZADA^A 3-wyp NP -POLNA I gc 2 NP , TO I ZADA^Agc NP -POLNA.62zADA^I OPTIMIZACIIw PRAKTI^ESKIH PRILOVENIQH ^ASTO WOZNIKA@T ZADA^I OPTIMIZACII, KOTORYE IME@T SLEDU@]U@ STRUKTURU. kAVDOMU WHODU x SOPOSTAWLQETSQ NEKOTOROE MNOVESTWO Yx DOPUSTIMYH RE[ENIJ. zADANFUNKCIONAL F : Yx ! R, GDE R | MNOVESTWO DEJSTWITELXNYH ^ISEL.tREBUETSQ NAJTI miny2Yx F (y), ILI maxy2Yx F (y), ILI TO DOPUSTIMOERE[ENIE y0, NA KOTOROM DOSTIGAETSQ OPTIMALXNOE ZNA^ENIE FUNKCIONALA.
eSLI FUNKCIONAL F WY^ISLQETSQ BYSTRO, TO NAJDQ OPTIMALXNOE DOPUSTIMOE RE[ENIE, MY MOVEM LEGKO POLU^ITX I OPTIMALXNOEZNA^ENIE FUNKCIONALA FOPT. oBRATNOE, WOOB]E GOWORQ, NE QSNO: MOVETSU]ESTWOWATX BYSTRYJ ALGORITM, KOTORYJ NAHODIT FOPT, NE NAHODQOPTIMALXNOGO RE[ENIQ.s KAVDOJ ZADA^EJ OPTIMIZACII MOVNO SWQZATX ZADA^U RASPOZNAWANIQ.
pRI \TOM NA WHOD KROME x PODAETSQ ^ISLO k I SPRA[IWAETSQ,WERNO LI, ^TO FOPT 6 k (ILI FOPT > k).nA PRAKTIKE DLQ RE[ENIQ ZADA^ OPTIMIZACII ^ASTO ISPOLXZU@TSQALGORITMY, NAZYWAEMYE VADNYMI ILI GRADIENTNYMI. w TAKIH ALGORITMAH DOPUSTIMOE RE[ENIE STROITSQ POSTEPENNO PO [AGAM, PRI^EMNA KAVDOM [AGE DELAETSQ WYBOR, OPTIMALXNYJ DLQ DANNOGO [AGA. kAKMY UWIDIM NIVE, TAKOJ PODHOD NE WSEGDA PRIWODIT K OPTIMALXNOMU RE[ENI@ W CELOM.
oDNAKO DLQ SLEDU@]EJ ZADA^I ON WSEGDA DAET OPTIMALXNOE RE[ENIE. nAPOMNIM, ^TO DEREWOM NAZYWAETSQ L@BOJNEORIENTIROWANNYJ SWQZNYJ GRAF BEZ CIKLOW. pODGRAF G1 GRAFA GNAZYWAETSQ OSTOWNYM, ESLI G1 SODERVIT WSE WER[INY GRAFA G. ~EREZKn OBOZNA^AETSQ POLNYJ GRAF NA n WER[INAH, TO ESTX GRAF, W KOTOROMKAVDAQ PARA WER[IN SOEDINENA REBROM.zADA^A O KRAT^AJ[EM OSTOWNOM DEREWE.wHOD NEORIENTIROWANNYJ POLNYJ GRAF Kn, W KOTOROM DLQ L@BOGOREBRA e ZADAN WES w(e) > 0.tREBUETSQ WYDELITX W Kn OSTOWNOE DEREWO S MINIMALXNOJ SUMMOJ WESOW REBER.zAME^ANIE.
nA PRAKTIKE \TO OZNA^AET TREBOWANIE POSTROITXSETX MINIMALXNOJ STOIMOSTI, SWQZYWA@]U@ n DANNYH OB_EKTOW.nAPOMNIM NEKOTORYE FAKTY IZ TEORII GRAFOW.uTWERVDENIE 1. eSLI W GRAFE S n WER[INAMI ^ISLO REBER q <n ; 1 TO GRAF NE SWQZNYJuTWERVDENIE 2. eSLI W GRAFE G NET CIKLOW I q = n ; 1q; n ^ISLO REBER I WER[IN TO G DEREWO::,(|.),|63.uTWERVDENIE 3. w L@BOM DEREWE S n WER[INAMI ^ISLO REBERq = n;1uTWERVDENIE 4. eSLI K DEREWU DOBAWITX NOWOE REBRO NA TEH.VE WER[INAH TO OBRAZUETSQ ROWNO CIKLrASSMOTRIM SLEDU@]IJ ALGORITM DLQ ZADA^I O KRAT^AJ[EM OSTOWNOM DEREWE.1.
wZQTX L@BOE REBRO e1 MINIMALXNOGO WESA.2. rEKURSIWNYJ [AG: PUSTX UVE WYBRANY REBRA e1; e2; : : : ; em . eSLIm = n ; 1, TO OSTANOWITXSQ. iNA^E, SREDI WSEH REBER, NE OBRAZU@]IHCIKLOW S e1; e2 ; : : : ; em , WZQTX REBRO em+1 MINIMALXNOGO WESA I POWTORITXREKURSIWNYJ [AG.aLGORITM DELAET MENX[E, ^EM n ITERACIJ I NA KAVDOJ PROSMATRIWAET MENEE, ^EM n2 REBER. pRI \TOM, ESLI IZ REBER e1; e2; : : : ; emSFORMIROWATX SWQZNYE KOMPONENTY, TO TOT FAKT, ^TO em+1 NE OBRAZUETS NIMI CIKLOW, \KWIWALENTEN TOMU, ^TO KONCY REBRA em+1 NE LEVATW ODNOJ SWQZNOJ KOMPONENTE. |TO SWOJSTWO LEGKO PROWERQETSQ.
tAKIMOBRAZOM, ALGORITM MOVET BYTX REALIZOWAN S POLINOMIALXNYM OT n^ISLOM OPERACIJ, WKL@^A@]IH POISK INFORMACII I SRAWNENIE WESOW.tEOREMA. oPISANNYJ ALGORITM KORREKTNO STROIT MINIMALXNOE OSTOWNOE DEREWOdOKAZATELXSTWO 1) dOKAVEM, ^TO ESLI m < n ; 1, TO SU]ESTWU@TREBRA, NE OBRAZU@]IE CIKLOW S e1; e2; : : : ; em . eSLI m < n ; 1, TOPODGRAF, SOSTOQ]IJ IZ WSEH WER[IN I REBER e1; e2; : : : ; em , NE SWQZNYJ(PO UTW. 1). eSLI WZQTX L@BOE REBRO, SOEDINQ@]EE DWE WER[INY IZRAZNYH KOMPONENT \TOGO PODGRAFA, TO CIKLY NE OBRAZU@TSQ. tAKIMOBRAZOM, ALGORITM PRORABOTAET DO m = n ; 1.2) pRI OSTANOWKE m = n ; 1 I REBRA e1; e2; : : : ; em NE OBRAZU@TCIKLOW.
tOGDA (PO UTW. 2) ONI OBRAZU@T OSTOWNOE DEREWO.3) pUSTX ALGORITM STROIT OSTOWNOE DEREWO D. dOKAVEM, ^TO D |MINIMALXNOE OSTOWNOE DEREWO. rASSMOTRIM WSE MINIMALXNYE OSTOWNYEDEREWXQ, I PUSTX T | MINIMALXNOE OSTOWNOE DEREWO, IME@]EE S DNAIBOLX[EE ^ISLO OB]IH REBER. dOKAVEM (OT PROTIWNOGO), ^TO D = T .dOPUSTIM, ^TO T 6= D. tAK KAK I W T I W D n ; 1 REBRO (UTW. 3), TOW D ESTX REBRA, NE WHODQ]IE W T . pUSTX W ALGORITME REBRA DEREWAD POQWLQLISX W PORQDKE: e1; e2 ; : : : ; en;1 I PUSTX REBRA e1; e2; : : : ; ekPRINADLEVAT DEREWU T , A ek+1 2= T . rASSMOTRIM GRAF H = T [fek+1g. wH IMEETSQ EDINSTWENNYJ CIKL C (UTW.4), SODERVA]IJ ek+1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
