Алексеев - Сложность алгоритмов (1123759), страница 12
Текст из файла (страница 12)
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. tAK KAK DNE SODERVIT CIKLOW, TO W C ESTX HOTQ BY ODNO REBRO e TAKOE, ^TO e 2= D.pRI \TOM e 2 T . rASSMOTRIM H1 = H n feg.
gRAF H1 | SWQZNYJ I BEZ,1.-..64CIKLOW, TO ESTX H1| OSTOWNOE DEREWO. pUSTX w(H1) I w(T ) | SUMMYWESOW REBER W H1 I T1. tAK KAK T | MINIMALXNOE OSTOWNOE DEREWO, TOw(H1) > w(T ) Iw(H1) = w(T ) + w(ek+1) ; w(e) > w(T ):oTS@DA w(e) 6 w(ek+1). pOSKOLXKU e 2 T I e1; e2; : : : ; ek PRINADLEVAT DEREWU T , TO e NE OBRAZUET CIKLOW S e1; e2 ; : : : ; ek .
eSLI BY BYLOw(e) < w(ek+1), TO NA k + 1-M [AGE ALGORITMA NE MOGLO BY WYBIRATXSQREBRO ek+1 . zNA^IT w(e) = w(ek+1) I w(H1) = w(T ). pOLU^AEM, ^TO H1| TAKVE MINIMALXNOE OSTOWNOE DEREWO, NO IME@]EE S D NA 1 OB]EEREBRO BOLX[E, ^EM T S D. |TO PROTIWORE^IT WYBORU DEREWA T . iZPOLU^ENNOGO PROTIWORE^IQ SLEDUET, ^TO DOLVNO BYTX D = T , TO ESTXD | MINIMALXNOE OSTOWNOE DEREWO. tEOREMA DOKAZANA.pRIBLIVENNYE ALGORITMY.zADA^A O MINIMALXNOM WER[INNOM POKRYTII (mwp).bUDEM GOWORITX, ^TO WER[INA v POKRYWAET REBRO e, ESLI e QWLQETSQ ODNIM IZ KONCOW REBRA e. PODMNOVESTWO A V WER[IN GRAFAG = (V; E ) NAZYWAETSQ WER[INNYM POKRYTIEM, ESLI WER[INY IZ APOKRYWA@T WSE REBRA IZ E .wHOD NEORIENTIROWANNYJ GRAF G = (V; E ).tREBUETSQ NAJTI WER[INNOE POKRYTIE (wp) MINIMALXNOJ MO]NOSTI."vADNYJ" ALGORITM DLQ mwp.nA KAVDOM [AGE WYBIRAETSQ L@BAQ WER[INA, POKRYWA@]AQ NAIBOLX[EE ^ISLO E]E NE POKRYTYH REBER.
aLGORITM OSTANAWLIWAETSQ,KOGDA WSE REBRA POKRYTY.lEGKO POKAZATX, ^TO "VADNYJ" ALGORITM DLQ mwp IMEET POLINOMIALXNU@ SLOVNOSTX.tEOREMA. dLQ VADNOGO ALGORITMA DLQ ZADA^I mwp DLQ L@BOGO NATURALXNOGO n SU]ESTWUET GRAF Gn TAKOJ ^TO PRI WHODE GnWYPOLNQETSQ NERAWENSTWOFALG > FOPT(ln n ; ln2 ; 1):::""-,:dOKAZATELXSTWO wKL@^IM W GRAF Gn SNA^ALA WER[INYu1; u2; : : : ; un , MEVDU KOTORYMI NE BUDET REBER. dALEE WYDELIM IZ WER[IN u1; u2 ; : : : ; un [ n2 ] NEPERESEKA@]IHSQ PAR (ODNA WER[INA MOVET NE.65U^ASTWOWATX W PARAH) I KAVDU@ PARU SOEDINIM S NOWOJ WER[INOJ, PRI\TOM POLU^IM NOWYE WER[INY v1; v2; : : : ; v[ n2 ] STEPENI 2.
zATEM WYDELIMIZ WER[IN u1 ; u2; : : : ; un [ n3 ] NEPERESEKA@]IHSQ TROEK I KAVDU@ TROJKUSOEDINIM S NOWOJ WER[INOJ (STEPENI 3). dALEE ANALOGI^NO WYDELIMNEPERESEKA@]IESQ ^ETWERKI, PQTERKI WER[IN I T.D. nA POSLEDNEM\TAPE WYDELIM IZ u1 ; u2; : : : ; un GRUPPU IZ n ; 1 WER[IN I SOEDINIMEE S NOWOJ WER[INOJ (STEPENI n ; 1). zAMETIM, ^TO POSLE DOBAWLENIQNOWYH WER[IN STEPENI k WER[INY u1; u2 ; : : : ; un IME@T STEPENX NE BOLEEk ; 1, W ^ASTNOSTI, W ZAKL@^ITELXNOM GRAFE Gn ONI IME@T STEPENX NEBOLEE n ; 2. pO\TOMU "VADNYJ" ALGORITM, PRIMENENNYJ K Gn, SNA^ALAWYBERET DOBAWLENNU@ WER[INU STEPENI n ; 1, ZATEM (POSLE UDALENIQ\TOJ WER[INY I POKRYWAEMYH E@ REBER) WYBERET WSE DOBAWLENNYEWER[INY STEPENI n ; 2, ZATEM WSE DOBAWLENNYE WER[INY STEPENI n ; 3 IT.D.
nA POSLEDNEM \TAPE ON WYBERET WSE DOBAWLENNYE WER[INY STEPENI2. tAKIM OBRAZOMih inn >FALG = 2 + n3 + : : : + n ;1nnn> 2 ;1 + 3 ; 1 +::: + n; 1 ; 1 =111= n + +::: +2 3n ; 1 ; (n ; 2) >Zn> n x1 dx ; n = n(ln n ; ln 2) ; n (20)h2s DRUGOJ STORONY MNOVESTWO fu1; u2 ; : : : ; un g QWLQETSQ WER[INNYM POKRYTIEM W Gn. pO\TOMU FOPT 6 n IFALG = n(ln n ; ln 2 ; 1) > FOPT(ln n ; ln 2 ; 1):oPREDELENIE. pUSTX DANA ZADA^A OPTIMIZACII S FUNKCIONALOMF . aLGORITM DLQ \TOJ ZADA^I NAZYWAETSQ "- PRIBLIVENNYM, ESLI WSEGDA FALG ; FOPT < ";FOPTGDE FALG I FOPT |ZNA^ENIE FUNKCIONALA, WYDAWAEMOE ALGORITMOM, IOPTIMALXNOE ZNA^ENIE.eSLI DANA ZADA^A MINIMIZACII I FOPT > 0, TO UKAZANNOE NERAWENSTWO \KWIWALENTNO NERAWENSTWU:FALG 6 (1 + ")FOPT:sLEDSTWIE.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
