В.Б. Алекссев - Сложные алгоритмы (1132790), страница 13
Текст из файла (страница 13)
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.
vADNYJ ALGORITM DLQ mwp NE QWLQETSQ" PRIBLIVENNYM NI PRI KAKOM FIKSIROWANNOM "-.66sLEDU@]AQ TEOREMA POKAZYWAET, ^TO TEORETI^ESKI "VADNAQ"STRATEGIQ DLQ ZADA^I mwp NE QWLQETSQ HORO[EJ.tEOREMA. dLQ ZADA^I mwp SU]ESTWUET PRIBLIVENNYJ ALGORITM S POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO rASSMOTRIM SLEDU@]IJ ALGORITM. pUSTX DANGRAF G = (V; E ). bUDEM FORMIROWATX WER[INOE POKRYTIE A.
wOZXMEML@BOE REBRO e1 = (v1; v2 ) I WKL@^IM v1 I v2 W A. wYBROSIM IZ GRAFA GWER[INY v1 I v2 I WSE REBRA, KOTORYE IMI POKRYWA@TSQ. w POLU^ENNOMGRAFE G1 OPQTX WOZXMEM L@BOE REBRO e2 = (v3; v4); DOBAWIM v3 I v4W A I UDALIM IZ G1 WER[IN v3 I v4 I WSE POKRYWAEMYE IMI REBRA.pROCESS ZAKON^IM, KOGDA BUDUT UDALENY WSE REBRA. lEGKO PONQTX,^TO \TOT ALGORITM MOVNO REALIZOWATX S POLINOMIALXNOJ SLOVNOSTX@.tAKVE PO POSTROENI@ O^EWIDNO, ^TO POLU^ENNOE MNOVESTWO WER[IN APOKRYWAET WSE REBRA. pUSTX W PROCESSE ALGORITMA WYBIRALISX REBRAe1; e2; : : : ; ek . tOGDA jAj = 2k. s DRUGOJ STORONY REBRA e1; e2; : : : ; ek NEIME@T OB]IH WER[IN I, SLEDOWATELXNO, L@BOE WER[INNOE POKRYTIEDOLVNO SODERVATX NE MENEE k WER[IN (^TOBY POKRYTX e1; e2; : : : ; ek ).tAKIM OBRAZOM FOPT > k I FALG = jAj > 2FOPT.
tEOREMA DOKAZANA.wOZNIKAET WOPROS, A NELXZQ LI DLQ ZADA^I mwp POSTROITX NEPRIBLIVENNYJ, A TO^NYJ ALGORITM S POLINOMIALXNOJ SLOVNOSTX@.wY[E BYLA DOKAZANA NP -POLNOTA ZADA^I O WER[INNOM POKRYTII (wp),GDE PO ZADANNOMU GRAFU G I ^ISLU k TREBUETSQ WYQSNITX, ESTX LI WGRAFE G WER[INNOE POKRYTIE MO]NOSTI NE BOLEE k.tEOREMA.
eSLI DLQ ZADA^I mwp SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO I DLQ ZADA^I wp SU]ESTWUET ALGORITMS POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO pUSTX ALGORITM H RE[AET ZADA^U mwp ZAPOLINOMIALXNOE WREMQ I PUSTX W ZADA^E wp ZADANY GRAF G I ^ISLOk. pRIMENQEM K GRAFU G ALGORITM H I POLU^AEM m | MINIMALXNU@MO]NOSTX WER[INNOGO POKRYTIQ W G. eSLI m 6 k, TO OTWET W ZADA^Ewp "DA", INA^E OTWET "NET". pOLU^AEM POLINOMIALXNYJ ALGORITM DLQZADA^I wp.zAME^ANIE. eSLI DLQ ZADA^I wp SU]ESTWUET ALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ I W GRAFE G n WER[IN, TO, PRIMENQQ ALGORITMH K PARAM (G; 0); (G; 1); : : : ; (G; n ; 1), MOVNO ZA POLINOMIALXNOE WREMQOPREDELITX MO]NOSTX MINIMALXNOGO WER[INNOGO POKRYTIQ, ODNAKO NEQSNO, KAK NAJTI SAMO MINIMALXNOE WER[INNOE POKRYTIE.oPREDELENIE. zADA^U OPTIMIZACII BUDEM NAZYWATXNP -TRUDNOJ, ESLI IZ SU]ESTWOWANIQ ALGORITMA POLINOMIALXNOJ1--..-,..67SLOVNOSTI DLQ NEE SLEDUET SU]ESTWOWANIE ALGORITMA POLINOMIALXNOJSLOVNOSTI DLQ NEKOTOROJ NP -POLNOJ ZADA^I (I,SLEDOWATELXNO, DLQWSEH ZADA^ IZ NP ).sLEDSTWIE.
zADA^A mwp QWLQETSQ NP TRUDNOJsLEDSTWIE. eSLI P =6 NP TO DLQ ZADA^I mwp NE SU]ESTWUETALGORITMA S POLINOMIALXNOJ SLOVNOSTX@-,.68.zADA^A KOMMIWOQVERAwY[E MY POLU^ILI USLOWNYJ REZULXTAT O TRUDNOSTI NAHOVDENIQTO^NOGO RE[ENIQ ZADA^I mwp. zDESX MY POKAVEM, ^TO TAKIE USLOWNYEOTRICATELXNYE REZULXTATY MOVNO POLU^ATX I DLQ NAHOVDENIQ PRIBLIVENNYH RE[ENIJ.nAPOMNIM, ^TO CIKL W GRAFE NAZYWAETSQ GAMILXTONOWYM, ESLI ONPROHODIT ^EREZ KAVDU@ WER[INU ROWNO 1 RAZ.
wY[E BYLO POKAZANO, ^TOZADA^A O SU]ESTWOWANII W GRAFE GAMILXTONOWA CIKLA (gc) QWLQETSQNP -POLNOJ.zADA^A KOMMIWOQVERA (zk).wHOD POLNYJ GRAF Kn, W KOTOROM KAVDOMU REBRU e = (vi ; vj )SOPOSTAWLEN WES d(e) = d(vi ; vj ) > 0. pRI \TOM BUDEM S^ITATX, ^TO WSEd(e)| CELYE ^ISLA I DLINA WHODA WKL@^AET W SEBQ SUMMARNU@ DLINUDWOI^NOGO PREDSTAWLENIQ WSEH d(e).tREBUETSQ NAJTI GAMILXTONOW CIKL W Kn S MINIMALXNOJ SUMMOJWESOW REBER.tEOREMA. zk QWLQETSQ NP TRUDNOJdOKAZATELXSTWO pUSTX SU]ESTWUET ALGORITM H DLQ zk SO SLOVNOSTX@, POLINOMIALXNO ZAWISQ]EJ OT DLINY WHODA. pUSTX DAN GRAFG = (V; E ) S n WER[INAMI I SPRA[IWAETSQ ESTX LI W G GAMILXTONOWCIKL.
pUSTX V = fv1; v2; : : : ; vn g. pOSTROIM POLNYJ GRAF Kn NA MNOVESTWE WER[IN V I ZADADIM WESA SLEDU@]IM OBRAZOM:pRIMENIM ALGORITM H DLQ zk K GRAFU Kn S \TIMI WESAMI. eSLIPOLU^IM DLQ zk, ^TO Fmin = n, TO W G SU]ESTWUET GAMILXTONOW CIKL,INA^E W G NE SU]ESTWUET GAMILXTONOWA CIKLA. tAKIM OBRAZOM, POLU^AEM ALGORITM DLQ ZADA^I O GAMILXTONOWOM CIKLE (gc). pOSKOLXKU W GMENX[E, ^EM n2 REBER, TO SUMMARNAQ DLINA DWOI^NOJ ZAPISI WSEH WESOWNE PREWOSHODIT cn2, GDE c|NEKOTORAQ KONTSANTA, TO ESTX DLINA WHODADLQ H NE PREWOSHODIT POLINOMA OT n.
tAK KAK H |POLINOMIALXNYJ (OTDLINY WHODA) ALGORITM, TO POSTROENNYJ NAMI ALGORITM DLQ gc IMEETPOLINOMIALXNU@ OT n SLOVNOSTX. tAKIM OBRAZOM IZ SU]ESTWOWANIQALGORITMA S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk WYTEKAET SU]ESTWOWANIE AGORITMA S POLINOMIALXNOJ SLOVNOTX@ DLQ gc. pOSKOLXKUZADA^A gc QWLQETSQ NP -POLNOJ, TO POLU^AEM, ^TO ZADA^A zk QWLQETSQNP -TRUDNOJ.tEOREMA.
eSLI P =6 NP TO NI DLQ KAKOGO SKOLX UGODNO BOLX[OGO POSTOQNNOGO ^ISLA " PRIBLIVENNOGO ALGORITMA DLQ zk S POLINOMIALXNOJ SLOVNOSTX@::-..,---.69dOKAZATELXSTWO dOPUSTIM, ^TO SU]ESTWUET " I SU]ESTWUET"-PRIBLIVENNYJ ALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk.pOSTROIM TOGDA ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ gc.pUSTX DAN GRAF G = (V; E ) S n WER[INAMI. pOSTROIM POLNYJ GRAFKn = (V; E 0 ) I DLQ WSEH e 2 E 0 POLOVIMpRIMENIM K Kn c WESAMI d ALGORITM H . pUSTX ALGORITM HNAHODIT GAMILXTONOW CIKL S SUMMARNOJ DLINOJ FH .lEMMA. eSLI W GARFE G ESTX GAMILXTONOW CIKL TO FH 6 n(1 +") eSLI W GRAFE G NET GAMILXTONOWA CIKLA TO FH > n(1 + ") + 1dOKAZATELXSTWO eSLI W G ESTX GAMILXTONOW CIKL, TO W zk DLQKn c dtcfvb d BUDET FOPT = n.
tAK KAK H QWLQETSQ "-PRIBLIVENNYMALGORITMOM DLQ zk, TO FH 6 FOPT(1 + ") = n(1 + "). eSLI W G NETGAMILXTONOWA CIKLA, TO L@BOJ GAMILXTONOW CIKL SODERVIT HOTQ BYODNO REBRO S WESOM [3 + "n] I n ; 1 REBER S WESOM NE MENEE 1. tAKIMOBRAZOM, SUMMARNYJ WES L@BOGO GAMILXTONOWA CIKLA NE MENX[E ^EMn ; 1 + 2 + "n = n(1 + ") + 1.lEMMA POKAZYWAET, ^TO PO REZULXTATU RABOTY ALGORITMA H MOVNO OPREDELITX, ESTX LI W G GAMILXTONOW CIKL. tAKIM OBRAZOM, MYPOLU^AEM ALGORITM H1 DLQ ZADA^I gc.
oCENIM WREMQ EGO RABOTY.dLINA DWOI^NOGO PREDSTAWLENIQ KAVDOGO WESA d(e) NE PREWOSHODITc log2 n, GDE c|NEKOTORAQ KONSTANTA, I KOLI^ESTWO WESOW MENX[E, ^EMn2. pO\TOMU DLINA WHODA DLQ ALGORITMA H NE PREWOSHODIT POLINOMAOT n. pOSKOLXKU WREMQ RABOTY H ZAWISIT POLINOMIALXNO OT DLINYWHODA, TO OB]EE WREMQ RABOTY ALGORITMA H1 NE PREWOSHODIT POLINOMAOT n. w REZULXTATE MY POLU^AEM, ^TO ESLI SU]ESTWUET "-PRIBLIVENNYJALGORITM H S POLINOMIALXNOJ SLOVNOSTX@ DLQ zk, TO SU]ESTWUETALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ ZADA^I gc.
nO ZADA^Agc NP -POLNA. tOGDA POLU^AEM, ^TO P = NP . tEOREMA DOKAZANA.wO MNOGIH PRAKTI^ESKIH ZADA^AH WESA UDOWLETWORQ@T ESTESTWENNOMU OGRANI^ENI@, NAZYWAEMOMU NERAWENSTWOM TREUGOLXNIKA:d(vi ; vj ) 6 d(vi ; vk ) + d(vk ; vj )DLQ WSEH RAZLI^NYH i; j; k. bUDEM GOWORITX, ^TO DANA ZADA^A KOMMIWOQVERA S NERAWENSTWOM TREUGOLXNIKA (zknt), ESLI NA WHOD POSTUPA@TTOLXKO WESA, UDOWLETWORQ@]IE NERAWESTWU TREUGOLXNIKA.tEOREMA. zknt NP POLNAdLQ DOKAZATELXSTWA \TOJ TEOREMY POLNOSTX@ PROHODIT DOKAZATELXSTWO TEOREMY ( ). dOSTATO^NO TOLXKO OTMETITX, ^TO NABOR WESOW,KOTORYJ STROITSQ W \TOM DOKAZATELXSTWE, UDOWLETWORQET NERAWENSTWUTREUGOLXNIKA..,.,.-.70.tEOREMA. dLQ zknt SU]ESTWUET PRIBLIVENNYJ ALGORITM S1-POLINOMIALXNOJ SLOVNOSTX@dOKAZATELXSTWO mY DOLVNY POSTROITX ALGORITM H DLQ zkntTAKOJ, ^TO WSEGDA FH 6 2FOPT. pRIMENIM K ZADANNOMU GRAFU KnS WESAMI d ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ POSTROENIQKRAT^AJ[EGO OSTOWNOGO DEREWA.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
