Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 3
Текст из файла (страница 3)
fORMALXNOSU]ESTWUET FUNKCIQ SWODIMOSTI f : e0 (D(p0 )) ! e(D(p)), TAKAQ^TO f (e0 (Y(p0 ))) = e(Y(p)), T.E. 80 2 e0 (Y(p0 )) f (0 ) 2 e(Y(p))I 800 2 e0 (D(p0 ) n Y(p)) f (00 ) 2 e(D(p) n Y(p)),I SU]ESTWUET dmt Af ; REALIZU@]AQ f ZA POLINOMIALXNOE WREMQ,T.E. 9pf () | POLINOM: 8 2 e0 (D(p0 )) TAf (jj) < pf (jj):w SLU^AE, KOGDA SOOTWETSTWU@]IE KODIROWKI NE IZBYTO^NY, BUDEMISPOLXZOWATX TERMIN POLINOMIALXNOJ SWODIMOSTI PO OTNO[ENI@ KSAMIM ZADA^AM (BEZ UKAZANIQ KODIROWOK) I PRIMENQTX OBOZNA^ENIEp0 / p:(kORREKTNOSTX UPRO]ENIQ WYTEKAET IZ POLINOMIALXNOJ SWODIMOSTIZADA^I K SAMOJ SEBE, NO S DRUGOJ NEIZBYTO^NOJ KODIROWKOJ, I SLEDU@]EGO O^EWIDNOGO UTWERVDENIQ | TRANZITIWNOSTI OTNO[ENIQ /.)uTWERVDENIE 3.
eSLI p1 / p2 I p2 / p3 ; TO p1 / p3 .sU]ESTWENNYM DLQ TEORII SLOVNOSTI QWLQETSQuTWERVDENIE 4. eSLI p0 / p I p 2 P; TO I p0 2 P.dOKAZATELXSTWO. oBOZNA^IM a dmt, RE[A@]U@ p S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@, I POSTROIM dmt A0 , RE[A@]U@ p0 S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@, KAK SUPERPOZCI@dmt A I Af : A0 = A Af ; T.E. SNA^ALA K L@BOMU WHODNOMU SLOWU0 2 e0 (D(p0 )) PRIMENQETSQ Af ; A POTOM K POLU^IW[EMUSQ SLOWU = f (0 ) (DLINOJ NE BOLEE pf (j0 j)) PRIMENQETSQ A.
wREMENNAQSLOVNOSTX A0 | TA0 () TAf () + TA (pf ()) | POLINOM.aNALOGI^NO DOKAZYWAETSQ (PRI ZAMENE SLOWA dmt NA ndmt)uTWERVDENIE 5. eSLI p0 / p I p 2 NP; TO I p0 2 NP.13oPREDELENIE 7. mASSOWAQ ZADA^A p NAZYWAETSQ NP-POLNOJ ILIUNIWERSALXNOJ, ESLI p 2 NP I 8p0 2 NP p0 / p (T.E. L@BAQ NEDETERMINIROWANNO POLINOMIALXNAQ ZADA^A POLINOMIALXNO SWODITSQK p). kLASS WSEH NP-POLNYH ZADA^ (RASPOZNAWANIQ SWOJSTW) OBOZNA^AETSQ NPC (NP-complete).nEPUSTOTU KLASSA NPC DOKAZAL s. a. kUK W 1971 G. iM BYLA RASSMOTRENA ZADA^A O WYPOLNIMOSTI (wyp): WYQSNITX WYPOLNIMOSTXKON_@NKTIWNOJ NORMALXNOJ FORMY (knf) | KON_@NKCII KONE^NOGO^ISLA DIZ_@NKTIWNYH FUNKCIJ, T.E.
DIZ_@NKCIJ BULEWYH PEREMENNYH zi ILI IH OTRICANIJ zi . a IMENNO, W ZADA^E wyp TREBUETSQRASPOZNATX DLQ knf NA WHODE, SU]ESTWUET LI WYPOLNQ@]IJ NABORz 0 (DLQ KOTOROGO ZNA^ENIE knf RAWNO 1).tEOREMA 2 (S. A. Cook). wyp 2 NPC.dOKAZATELXSTWO POLINOMIALXNOJ SWODIMOSTIK wyp L@BOJNEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I OSNOWANO NA FORMALXNOJ ZAPISI USLOWIQ PRINADLEVNOSTI SLOWA QZYKU IZ KLASSA NP (TOGO, ^TO PRINIMAETSQ NEKOTOROJ ndmt, A ZNA^IT, I KAKOJ-TO dmt)W WIDE NABORA DIZ_@NKTIWNYH FUNKCIJ OT SPECIALXNO WWODIMYH BULEWYH PEREMENNYH, SWQZANNYH S SOSTOQNIQMI dmt W RAZLI^NYE MOMENTY WREMENI, I QWLQETSQ NEDOSTATO^NO PROSTYM DLQ WWODNOGO KURSA (SM. [1,2]).
pO\TOMU MY LI[X UBEDIMSQ W TOM, ^TO wyp 2 NP.dEJSTWITELXNO, WHODNOE SLOWO (PARAMETRY, OPREDELQ@]IE INDIWIDUALXNU@ ZADA^U WYPOLNIMOSTI) SODERVIT ^ISLO DIZ_@NKTIWNYHFUNKCIJ W knf I UKAZANIE DLQ KAVDOJ IZ NIH, KAKIE PEREMENNYEWHODQT S OTRICANIEM, A KAKIE NE WHODQT WOOB]E. dLINU TAKOGO SLOWAMOVNO OGRANI^ITX SNIZU SUMMOJ DLIN DIZ_@NKTIWNYH FUNKCIJ, PONIMAQ POD DLINOJ FUNKCII ^ISLO EE PEREMENNYH (ILI ^ISLO ZNAKOWDIZ_@NKCII + 1). eSLI TEPERX W KA^ESTWE PODSKAZKI DLQ OPREDELQEMOJ WHODNYM SLOWOM knf WZQTX z0 | WYPOLNQ@]IJ EE NABOR, TOWY^ISLENIE NA NEM ZNA^ENIQ knf (PROWERKA WYPOLNIMOSTI) POTREBUET TAKOGO VE PO PORQDKU ^ISLA [AGOW.iZ OPREDELENIQ NP-POLNOTY NEPOSREDSTWENNO SLEDUETuTWERVDENIE 6. eSLI P \ NPC 6= ;, TO P = NP.
a ESLINPC \ (NP n P) 6= ;, TO NPC NP n P.tAKIM OBRAZOM, ESLI BY UDALOSX NAJTI POLINOMIALXNYJ ALGORITM RE[ENIQ HOTX ODNOJ NP-POLNOJ ZADA^I, TO BYLI BY POSTROENY14POLINOMIALXNYE ALGORITMY RE[ENIQ WSEH NP-POLNYH ZADA^ I WSEHZADA^ IZ KLASSA NP, A ESLI DLQ KAKOJ-LIBO NP-POLNOJ ZADA^I DOKAZATX OTSUTSTWIE POLINOMIALXNOGO ALGORITMA EE RE[ENIQ, TO \TONE TOLXKO DAET STROGOE WKL@^ENIE P NP (T.E. OTWET K OSNOWNOJPROBLEME TEORII SLOVNOSTI), NO I WLE^ET ZA SOBOJ DOKAZATELXSTWO NEWOZMOVNOSTI POSTROENIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ L@BOJ ZADA^I IZ KLASSA NPC. pOSKOLXKU NI TOGO, NI DRUGOGO POKA NESDELANO, S^ITAETSQ, ^TO ZADA^I IZ NPC OTWE^A@T VITEJSKOMU PREDSTAWLENI@ O TRUDNOJ ZADA^E I WRQD LI DOPUSKA@T \FFEKTIWNOE RE[ENIE.
pO\TOMU, ESLI WSTRE^AETSQ ZADA^A, DLQ KOTOROJ NA PRAKTIKENE UDAETSQ PRIDUMATX NEPEREBORNYJ ALGORITM, TO IMEET SMYSL POPYTATXSQ DOKAZATX EE NP-POLNOTU, ^TOBY OPRAWDATX PRIMENENIE KNEJ TEH ILI INYH PEREBORNYH SHEM.3. pOSLE TOGO KAK BYLA USTANOWLENA NEPUSTOTA KLASSA NPC (TEOREMOJ kUKA), POQWILASX WOZMOVNOSTX DOKAZATELXSTWA NP-POLNOTYMASSOWOJ ZADA^I p PUTEM POLINOMIALXNOGO SWEDENIQ K p ODNOJ IZIZWESTNYH NP-POLNYH ZADA^ (SOOTWETSTWU@]IJ SPISOK SM.
W [1]).dEJSTWITELXNO, IZ UTWERVDENIQ 3 SLEDUETtEOREMA 3 (KRITERIJ NP-POLNOTY). mASSOWAQ ZADA^A p RASPOZNAWANIQ SWOJSTW NP-POLNA TOGDA I TOLXKO TOGDA, KOGDA ONA PRINADLEVIT KLASSU NP I K NEJ POLINOMIALXNO SWODITSQ KAKAQ-LIBONP-POLNAQ ZADA^A:fp 2 NPCg () fp 2 NP I 9p0 2 NPC : p0 / pg:pOLXZUQSX TEOREMOJ 3, MOVNO POKAZATX NP-POLNOTU ZADA^I O SU]ESTWOWANII CELO^ISLENNOGO RE[ENIQ SISTEMY LINEJNYH NERAWENSTWS CELYMI KO\FFICIENTAMI (cln).uTWERVDENIE 7. cln 2 NPC.dOKAZATELXSTWO. 1) cln 2 NP, TAK KAK PODSKAZKOJ MOVETSLUVITX RE[ENIE SISTEMY, A EGO PROWERKA SWODITSQ K UMNOVENI@ NAZADANNYE KO\FFICIENTY I SLOVENI@, ^TO NE PREWOSHODIT POLINOMAOT DLINY ZAPISI WSEH KO\FFICIENTOW (DOKAZATELXSTWO POLINOMIALXNOSTI DLINY ZAPISI RE[ENIQ SM. W [2, S.
330]).2) wyp / cln. oB]IJ WID SISTEMY LINEJNYH NERAWENSTWaj 1 z1 + aj 2 z2 + : : : + ajn zn bj ; j = 1; : : : ; m:nETRUDNO PREDSTAWITX W PODOBNOJ FORME USLOWIE ISTINNOSTI DIZ_@NKTIWNOJ FUNKCII. dLQ \TOGO ZAMENIM W KAVDOJ j -J FUNKCII ZNAKI15DIZ_@NKCII ZNAKAMI SUMMY, A OTRICANIQ PEREMENNYH zi | NA (1 zi )I NAPI[EM DLQ POLU^IW[EJSQ LINEJNOJ FUNKCII USLOWIE 1, DOBAWIW OGRANI^ENIQ zi 0 I zi 1 NA WSE PEREMENNYE. cELO^ISLENNOERE[ENIE z0 = fzi0g SISTEMY WSEH POSTROENNYH NERAWENSTW QWLQETSQ WYPOLNQ@]IM NABOROM DLQ ISHODNOJ knf (TAK KAK ISTINNOSTXknf \KWIWALENTNA ISTINNOSTI WSEH OBRAZU@]IH EE DIZ_@NKTIWNYHFUNKCIJ). tAKIM SPOSOBOM RE[ENIE L@BOJ INDIWIDUALXNOJ ZADA^IO WYPOLNIMOSTI SWODITSQ K RE[ENI@ NEKOTOROJ INDIWIDUALXNOJ ZADA^I I 2 cln.
pOLINOMIALXNOSTX SWEDENIQ O^EWIDNA.zAMETIM, ^TO FAKTI^ESKI W P.2 DANNOGO DOKAZATELXSTWA DOKAZANBOLEE SILXNYJ REZULXTAT O SWEDENII wyp K PODZADA^E cln | ZADA^E O SU]ESTWOWANII BULEWA RE[ENIQ SISTEMY LINEJNYH NERAWENSTWS CELYMI KO\FFICIENTAMI (bln). dOKAZATELXSTWO PRINADLEVNOSTIbln KLASSU NEDETERMINIROWANNO POLINOMIALXNYH ZADA^ POWTORQETP.1 DANNOGO DOKAZATELXSTWA BEZ SSYLKI NA [2] (TAK KAK POLINOMIALXNOSTX DLINY BULEWA RE[ENIQ O^EWIDNA), TEM SAMYM POLU^ENO IuTWERVDENIE 8. bln 2 NPC.x3. kLASSY SLOVNOSTI.sILXNAQ NP-POLNOTA I PSEWDOPOLINOMIALXNOSTXdOKAZATELXSTWO NP-POLNOTY ZADA^I O 3-WYPOLNIMOSTI.
wZAIMOOTNO[ENIE KLASSOW r, Nr I Nrs, Nr I SO-Nr. NP-TRUDNYEZADA^I. kLASS rSrase. pSEWDOPOLINOMIALXNYE ALGORITMY. pRIMER DLQ ZADA^I O R@KZAKE. sILXNAQ NP-POLNOTA. tEOREMA O SWQZI SILXNOJ NP-POLNOTY ZADA^I S SU]ESTWOWANIEM PSEWDOPOLINOMIALXNOGO ALGORITMA EE RE[ENIQ.1. kROME ZADA^I O WYPOLNIMOSTI, NP-POLNOTA WSEH OSTALXNYHIZWESTNYH ZADA^ IZ KLASSA NPs (W TOM ^ISLE I km) BYLA DOKAZANANA OSNOWE TEOREMY 3 S POMO]X@ POLINOMIALXNOGO SWEDENIQ. oB]IERECEPTY DOKAZATELXSTWA POLINOMIALXNOJ SWODIMOSTI (SM. W [1]) LEGKO ISPOLXZOWATX LI[X W PROSTEJ[IH SLU^AQH.
~TOBY NAU^ITXSQ IHPRIMENQTX, NADO RAZOBRATX BOLX[OE ^ISLO PRIMEROW (W ^ASTNOSTI,IME@]IESQ W [1,2]), NA ^TO U NAS W RAMKAH DANNOJ RABOTY NET WOZMOVNOSTI. oDNAKO, E]E ODIN PRIMER BUDET DALEE PRIWEDEN S CELX@POKAZATX, ^TO NE TOLXKO L@BAQ PODZADA^A SWODITSQ K SOOTWETSTWU@]EJ ZADA^E (AWTOMATI^ESKI), NO WOZMOVNO I OBRATNOE SWEDENIE.16rASSMOTRIM ^ASTNYJ SLU^AJ ZADA^I O WYPOLNIMOSTI, KOGDA Wknf MOGUT WHODITX LI[X DIZ_@NKTIWNYE FUNKCII TREH PEREMENNYH (3-wyp).
pOSKOLXKU D(3-wyp)D(wyp), TO PO OPREDELENI@ 3-wyp/wyp. tAK ^TO 3-wyp2NP (PO UTWERVDENI@ 5). nOEE NP-POLNOTA TREBUET SPECIALXNOGO DOKAZATELXSTWA, IBO ^ASTNYEMASSOWYE ZADA^I SODERVAT MENX[E INDIWIDUALXNYH ZADA^ I MOGUTOKAZATXSQ PRO]E; NAPRIMER, ANALOGI^NAQ ZADA^A 2-wyp POLINOMIALXNA. dLQ POLU^ENIQ REZULXTATA 3-wyp 2 NPs DOKAVEM, ^TO NPPOLNAQ ZADA^A O WYPOLNIMOSTI SWODITSQ K SWOEJ PODZADA^E (^ASTNOMUSLU^A@) 3-wyp.uTWERVDENIE 9.
wyp / 3-wyp.dOKAZATELXSTWO. pOKAVEM, ^TO PROIZWOLXNU@ DIZ_@NKTIWNU@FUNKCI@ f j (zj ) k PEREMENNYH MOVNO PREDSTAWITX W WIDE KON_@NKCII DIZ_@NKTIWNYH FUNKCIJ OT TREH PEREMENNYH (ZA S^ET WWEDENIQjDOPOLNITELXNYH PEREMENNYH uj ). oBOZNA^IM ^EREZ yi PEREMENNU@ ziILI zji W ZAWISIMOSTI OT TOGO, KAK i-Q KOMPONENTA zj WHODIT W RASSMATRIWAEMU@ DIZ_@NKTIWNU@ FUNKCI@; TOGDA POSLEDN@@ MOVNOZAPISATX KAK y1 _ y2 _ : : : _ yk I PRI k > 3 ZAMENITX NA knf:(y1 _ y2 _ uj1)&(y3 _ uj1 _ uj2)&(y4 _ uj2 _ uj3)& : : :: : : &(yk 2 _ ujk 4 _ ujk 3 )&(yk 1 _ yk _ ujk 3 ).oTMETIM, ^TO DANNAQ ZAMENA NE QWLQETSQ \KWIWALENTNOJ.
dEJSTWITELXNO, ESLI ISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX NUL@, TO POSTROENNAQ knf RAWNA NUL@ PRI WSEH ZNA^ENIQH u, NO ESLIISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX 1, TO NAJDETSQ TAKOEZNA^ENIE u, ^TOBY knf RAWNQLASX 1. |TOGO, ODNAKO, DOSTATO^NO DLQSOHRANENIQ OTWETA NA WOPROS O SU]ESTWOWANII WYPOLNQ@]EGO NABORA.upravnenie 4. zAWER[ITX DOKAZATELXSTWO Nr-POLNOTY ZADA^I 3-wyp (RASSMOTRETX SLU^AI k < 3).2. uNIWERSALXNOSTX ZADA^ IZ KLASSA NPs (NP-POLNYH ZADA^) SOSTOIT W TOM, ^TO OSNOWNYE NERE[ENNYE WOPROSY DLQ KLASSA NP (NEDETERMINIROWANNO POLINOMIALXNYH ZADA^) DOSTATO^NO RAZRE[ITX HOTQ BY DLQ ODNOJ NP-POLNOJ ZADA^I, ^TOBY POLU^ITX OTWET DLQ WSEGOKLASSA NP.
kROME UTWERVDENIQ 6 ZDESX TAKVE WAVNOuTWERVDENIEeSLI DLQ NEKOTOROJ NP-POLNOJ ZADA^I p DOPOLNITELXNAQ K NEJ p PRINADLEVIT KLASSU NP, TO NP = co-NP.10.17tAK KAK p 2 NPC, TO 8p0 2 NP p0 / p,OTS@DA I p / p (POLINOMIALXNOE SWEDENIE OSU]ESTWLQETSQ0 TOJ VEFUNKCIEJ | SM. OPREDELENIE 6).
nO p 2 NP, ZNA^IT, p 2 NPPO UTWERVDENI@ 5. s U^ETOM PROIZWOLXNOSTI p0 2 NP POLU^ILI,^TO co-NP NP. oBRATNOE WKL@^ENIE DOKAZYWAETSQ NA OSNOWANIIO^EWIDNOGO RAWENSTWA p = p.nAPOMNIM, ^TO GIPOTEZA NP = co-NP W NASTOQ]EE WREMQ KAVETSQ NEREALXNOJ (REALXNAQ GIPOTEZA P = NP\co-NP), I WRQD LIDLQ KAKOJ-LIBO NP-POLNOJ ZADA^I UDASTSQ DOKAZATX PRINADLEVNOSTXKLASSU co-NP. pO\TOMU DLQ KONKRETNOJ NEDERMINIROWANNO POLINOMIALXNOJ MASSOWOJ ZADA^I p2NP, ESLI EE RE[ENIE PREDSTAWLQETINTERES, IMEET SMYSL POPYTATXSQ DOKAZATX WKL@^ENIE p 2 NP (T.E.EE HORO[U@ HARAKTERIZACI@) I ZATEM POSTROITX POLINOMIALXNYJALGORITM RE[ENIQ, LIBO, KOGDA UKAZANNOE WKL@^ENIE NE DOKAZYWAETSQ, NADO POPROBOWATX POLINOMIALXNO SWESTI K p ODNU IZ IZWESTNYHNP-POLNYH ZADA^ (T.E. POKAZATX NP-POLNOTU p) I W SLU^AE USPEHAPODYSKIWATX PEREBORNU@ SHEMU RE[ENIQ (U^ITYWAQ OGRANI^ENIQ NARAZMERNOSTX PRAKTI^ESKI RE[AEMYH INDIWIDUALXNYH ZADA^).dOKAZATELXSTWO UNIWERSALXNOSTI p, T.E.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
