Алексеев - Сложность алгоритмов (1123759), страница 13
Текст из файла (страница 13)
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.
pUSTX ON STROIT KRAT^AJ[EE OSTOWNOEDEREWO D S SUMMARNYM WESOM REBER d(D). pUSTX C | L@BOJ GAMILXTONOW CIKL. eSLI WYBROSITX L@BOE REBRO IZ C , TO POLU^IM DEREWO T .pRI \TOMd(D) 6 d(T ) 6 d(C ):pO\TOMU d(D) 6 FOPT. rASSMOTRIM DEREWO D I ZAMENIM KAVDOE REBROe = (vi ; vj ) W D DWUMQ REBRAMI e0 = (vi; vj ) I e" = (vi ; vj ). tOGDAPOLU^IM MULXTIGRAF K (GRAF S KRATNYMI REBRAMI), W KOTOROM STEPENXKAVDOJ WER[INY ^ETNA.
tAK KAK D| OSTOWNOE DEREWO, TO MULXTIGRAFK SWQZNYJ. wY[E DOKAZANO (SM. TEOREMU ( )), ^TO W L@BOM SWQZNOMMULXTIGRAFE, W KOTOROM STEPENI WSEH WER[IN ^ETNY, SU]ESTWUET \JLEROW CIKL. pRIMENIM K K ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQPOSTROENIQ W K \JLEROWA CIKLA C1 (SU]ESTWOWANIE TAKOGO ALGORITMADOKAZANO W TEOREME( )). pOSKOLXKU CIKL C1 PROHODIT PO KAVDOMU REBRUW K ROWNO 1 RAZ, TO WES d(C1) = 2d(D) 6 2FOPT. wYBEREM L@BU@ WER[INU v1 W C1 W KA^ESTWE NA^ALXNOJ I PUSTX WER[INY W C1 WSTRE^A@TSQW PORQDKE v1; v2 ; v3; : : : ; vi;1 ; vi ; vi+1 ; : : : ; v1 . pUSTX WYDELENNOE ZNA^ENIEvi WSTRE^AETSQ W CIKLE RANX[E.
tOGDA ZAMENIM POSLEDOWATELXNOSTXREBER (vi;1; vi ); (vi ; vi+1 ) NA REBRO (vi;1; vi+1 W ISHODNOM GRAFE. pRI \TOMPOLU^IM OPQTX CIKL, PROHODQ]IJ PO WSEM WER[INAM. pOSKOLXKU WESAUDOWLETWORQ@T NERAWENSTWU TREUGOLXNIKA, TO SUMMARNYJ WES CIKLAPRI \TOM NE WOZRASTET. eSLI W POLU^ENNOM CIKLE SNOWA ESTX POWTORQ@]IESQ WER[INU, TO OPQTX WYBROSIM ODNU WER[INU, OSU]ESTWIW"SPRQMLENIE". |TOT PROCESS BUDEM POWTORQTX DO TEH POR, POKA NEPOLU^ITSQ CIKL C2 BEZ POWTORQ@]IHSQ WER[IN. tOGDA CIKL C2 BUDETGAMILXTONOWYM I d(C2) 6 d(C1) 6 2FOPT.
w REZULXTATE MY POLU^AEMALGORITM DLQ zknt S POLINOMIALXNOJ SLOVNOSTX@, KOTORYJ QWLQETSQ1-PRIBLIVENNYM...71zADA^A O MAKSIMALXNOJ KLIKEwY[E BYLO DOKAZANO, ^TO ZADA^A klika QWLQETSQ NP -POLNOJ.rASSMOTRIM TEPERX SLEDU@]U@ ZADA^U mk.wHOD NEORIENTIROWANNYJ GRAF G.tREBUETSQ NAJTI KAKU@-NIBUDX MAKSIMALXNU@ PO ^ISLU WER[INKLIKU.tEOREMA. zADA^A O MAKSIMALXNOJ KLIKE mk QWLQETSQNP TRUDNOJdOKAZATELXSTWO pUSTX A | ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ DLQ mk, I PUSTX PARA (G; k) | WHOD DLQ ZADA^I klika.pRIMENIM K G ALGORITM A I NAJDEM MO]NOSTX m POLU^ENNOJ MAKSIMALXNOJ KLIKI W G.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
