Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 4
Текст из файла (страница 4)
WKL@^ENIQ p2NPC,UDAETSQ NE WSEGDA, I W TEORII SLOVNOSTI BYL WWEDEN OB_EML@]IJNPC KLASS NP-TRUDNYH ZADA^, SODERVA]IJ1) 0p RASPOZNAWANIQ SWOJSTW, DLQ KOTORYH DOKAZANO, ^TO p0 / pDLQ p 2 NPC, NO NE POKAZANO, ^TO p 2 NP (W ^ASTNOSTI, \TO ZADA^Ip2co-NPC);2) p OPTIMIZACII, DLQ KOTORYH SOOTWETSTWU@]IE p RASPOZNAWANIQ SWOJSTW NP-POLNY (NAPRIMER, ZADA^A KOMMIWOQVERA IZ P.1x1);3) I OSTALXNYE MASSOWYE ZADA^I (NE OBQZATELXNO RASPOZNAWANIQSWOJSTW), K KOTORYM SWODQTSQ PO tX@RINGU KAKIE-LIBO NP-POLNYEZADA^I p0 2 NPC, GDE SWODIMOSTX PO tX@RINGU | p0 /T p | OZNA^AET, ^TO IZ SU]ESTWOWANIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ pSLEDUET SU]ESTWOWANIE POLINOMIALXNOGO ALGORITMA I DLQ p0 .zADA^I p (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW), DLQ KOTORYH9p0 2 NPC: p0 /T p I 9p00 2 NP: p /T p00 , NAZYWA@TSQ ZADA^AMI IZ KLASSA NP-\KWIWALENTNYH.dOKAZATELXSTWO.018wSE RASSMOTRENNYE NAMI KLASSY ZADA^ p | KLASSY SLOVNOSTIWKL@^A@TSQ W OB]IJ KLASS PSPACE MASSOWYH ZADA^ (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW), DLQ RE[ENIQ KOTORYH SU]ESTWU@TALGORITMY, TREBU@]IE NE BOLEE ^EM POLINOMIALXNOJ PAMQTI.
wOPROS O RAWENSTWE P I PSPACE QWLQETSQ OTKRYTYM. rABO^AQ GIPOTEZA SOSTOIT W NALI^II STROGOGO WKL@^ENIQ PPSPACE, PRI\TOM NP-POLNYE, NP-TRUDNYE I NP-\KWIWALENTNYE ZADA^I DOLVNYWKL@^ATXSQ W PSPACE n P. (sOOTWETSTWU@]U@ DIAGRAMMU WZAIMOSWQZI KLASSOW SLOVNOSTI SM. W [2, S. 412].)zAMETIM, ^TO TEORETI^ESKI RASSMOTRENNU@ SHEMU POSTROENIQKLASSOW SLOVNOSTI MOVNO PRIMENQTX I DLQ DRUGIH SHEM KLASSIFIKACII; W ^ASTNOSTI, WWODQT TAKVE KLASS PSPACE-POLNYH ZADA^ (K KOTORYM POLINOMIALXNO SWODITSQ L@BAQ ZADA^A IZ KLASSA PSPACE).kROME POLINOMIALXNOJ SWODIMOSTI MOVNO ANALOGI^NO GOWORITX OLOGARIFMI^ESKOJ SWODIMOSTI, O ZADA^AH, TREBU@]IH LOGARIFMI^ESKOJ PAMQTI I T.P. w NASTOQ]EE WREMQ NAIBOLEE INTENSIWNO IZU^AEMYM ZDESX OKAZYWAETSQ KLASS NC (Nick Class, AWTOR N.
Pippenger)ZADA^, RE[AEMYH ZA WREMQ, OGRANI^ENNOE POLINOMOM OT LOGARIFMADLINY WHODA, I TREBU@]IH POLINOMIALXNOJ PAMQTI (LOGARIFMI^ESKOE WREMQ PRI WOZMOVNOSTI POLINOMIALXNOGO ^ISLA PROCESSOROW).k SOVALENI@, IZLOVENIE POLU^ENNYH DLQ NC REZULXTATOW WYHODITZA RAMKI WWEDENIQ W TEORI@ SLOVNOSTI.3.
rANEE UVE OTME^ALOSX, ^TO S PRAKTI^ESKOJ TO^KI ZRENIQ RAZNICA MEVDU POLINOMIALXNYM ALGORITMOM (DLQ POLINOMOW WYSOKIHSTEPENEJ) I \KSPONENCIALXNYM WESXMA USLOWNA, A WSE DELO W WOZMOVNOSTI ILI NEWOZMOVNOSTI IZBEVATX POLNOGO PEREBORA. wOPROS, WSE LINP-POLNYE I NP-TRUDNYE ZADA^I TRUDNY DLQ PRAKTI^ESKOGO S^ETA,MY OBSUDIM NIVE W \TOM PARAGRAFE.rASSMOTRIM SAMU@ PROSTU@ (PO FORMULIROWKE) NP-TRUDNU@ ZADA^U | ZADA^U O R@KZAKE (zr), ZAKL@^A@]U@SQ W TOM, ^TOBY IZIME@]EGOSQ NABORA POLEZNYH WE]EJ SOBRATX R@KZAK OGRANI^ENNOGOOB_EMA S NAIBOLX[EJ POLXZOJ. fORMALXNO TREBUETSQ NAJTInXmaxfz: z 2f0;1g 8j =1;:::;njj =1cj zj j19nXj =1wj zj K g;GDE cj 2 Z+ | POLEZNOSTX (CENNOSTX), wj 2 Z+ | OB_EM (WES) j -JWE]I, A PEREMENNAQ zj OPREDELQET KLASTX ILI NE KLASTX EE W R@KZAK;MAKSIMALXNO WOZMOVNYJ OB_EM (WES) R@KZAKA ZADAETSQ PARAMETROMK 2 Z+ .
sOOTWETSTWU@]AQ ZADA^A RASPOZNAWANIQ SWOJSTW | SU]ESTWUET LI BULEWO RE[ENIE SISTEMY DWUH LINEJNYH NERAWENSTWnXj =1nXcj zj B Ij =1wj zj KS NATURALXNYMI KO\FFICIENTAMI | NP-POLNA (DOKAZATELXSTWO NESLEDUET IZ UTWERVDENIQ 8, TAK KAK RASSMATRIWAETSQ ^ASTNYJ SLU^AJbln, PO\TOMU SM. [1, S. 87 ILI 2, S. 386]). dLQ RE[ENIQ zr IZWESTENSLEDU@]IJ METOD (DINAMI^ESKOGO PROGRAMMIROWANIQ).pROIZWOLXNAQ INDIWIDUALXNAQ ZADA^A I2zr POGRUVAETSQ W SEMEJSTWO ZADA^ POISKAFi (E ) =:nXmaxfz: z 2f0;1g 8j =i;:::;njj =icj zj jnXj =iw j z j K E g;F1 (0) | ZNA^ENIE zr.
i RE[A@TSQ WSE ZADA^I DANNOGO SEMEJSTWA POREKURRENTNYMFORMULAM, GDE i UBYWAET S n DO 1. a IMENNO, POLOVIMFi (E ) =: 0 8E K; 8i. iMEEM 8E = 0; K 1 :Fn (E ) =0;cnE > K wn ;INA^E,I 8i = n 1; : : : ; 2: Fi (E ) = maxfFi+1 (E ); ci + Fi+1 (E + wi )g =:=: z maxfc z + Fi+1 (E + wi zi )g; F1 (0) = maxfF2 (0); c1 + F2 (w1 )g:2f0;1g i ii~ISLO ITERACIJ PREDLOVENNOGO ALGORITMA RAWNO nK I TOGO VE SLOVNOSTX. oTMETIM, ^TO ALGORITM NEPORQDKA BUDET EGO WREMENNAQQWLQETSQ POLINOMIALXNYM, IBO DLQ ZAPISI ^ISLA K TREBUETSQ PORQDKA log2 K SIMWOLOW; ON TAKVE OKAZYWAETSQ PEREBORNYM | PEREBIRAETWSE WARIANTY ZAPOLNENNOSTI R@KZAKA. oDNAKO PRI NE O^ENX BOLX[IHOB_EMAH R@KZAKA MOVNO DOWOLXNO BYSTRO POLU^ITX RE[ENIE.
dLQOBOB]ENIQ UKAZANNOGO SWOJSTWA DADIM20oPREDELENIE 8. oBOZNA^IM ^EREZ num(I) MAKSIMALXNOE PO MODUL@ CELOE ^ISLO (ILI 0), FIGURIRU@]EE PRI ZADANII^ISLOWYH PARAMETROW DLQ INDIWIDUALXNOJ ZADA^I I, I ^EREZ jIj =: je(I)j | DLINUZAPISI I. aLGORITM a RE[ENIQ MASSOWOJ ZADA^I p (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW) NAZYWAETSQ PSEWDOPOLINOMIALXNYM, ESLIDLQ NEKOTOROGO POLINOMA p(; ) WYPOLNENO tA (e(I)) < p(jIj,num(I))8I 2 p.pRIMEROM PSEWDOPOLINOMIALXNOGO ALGORITMA QWLQETSQ ALGORITMDINAMI^ESKOGO PROGRAMMIROWANIQ DLQ RE[ENIQ zr.
dLQ MNOGIH DRUGIH ZADA^ (W ^ASTNOSTI, km) PSEWDOPOLINOMIALXNYH ALGORITMOW NEIZWESTNO. ~TOBY WYDELITX KLASS TAKIH ZADA^, WWEDEM PONQTIE POLINOMIALXNOGO SUVENIQ MASSOWOJ ZADA^I p KAK MNOVESTWA TEH INDIWIDUALXNYH ZADA^, ^ISLOWYE PARAMETRY KOTORYH NE PREWOSHODQT,POLINOMA OT DLINY WHODApp() =: fI 2 pj num(I) < p(jIj)g:oPREDELENIE 9. mASSOWAQ ZADA^A p RASPOZNAWANIQ SWOJSTW NAZYWAETSQ SILXNO NP-POLNOJ, ESLI EE POLINOMIALXNOE SUVENIE NPPOLNO, T.E. 9p() | POLINOM: pp() 2 NPC.pRIMERAMI SILXNO NP-POLNYH ZADA^ QWLQ@TSQ wyp I 3-wyp(KAK SOWPADA@]IE SO SWOIMI POLINOMIALXNYMI SUVENIQMI), bln(POSKOLXKU wyp BYLA SWEDENA K EE POLINOMIALXNOMU SUVENI@, WKOTOROM MODULI PRAWYH ^ASTEJ NE PREWY[A@T n), cln (KAK OBOB]ENIE bln W OTLI^IE OT zr), A TAKVE km [1, S.
123-124].tEOREMA 4. eSLI P 6= NP, TO NI DLQ KAKOJ SILXNO NP-POLNOJZADA^I NE SU]ESTWUET PSEWDOPOLINOMIALXNOGO ALGORITMA RE[ENIQ.dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX dmt a RE[AET SILXNO NP-POLNU@ ZADA^U p I 8I 2 p tA (e(I)) < p0 (jIj,num(I))DLQ POLINOMA p0 (; ). tOGDA 8I 2 pp() tA (e(I)) < p0 (jIj; p(jIj)) =p00 (jIj), T.E. pp() 2 P | PROTIWORE^IE S pp() 2 NPC ILI UTWERVDENIEM 6.sILXNO NP-POLNYE ZADA^I S^ITA@TSQ NAIBOLEE TRUDNYMI DLQS^ETA SREDI WSEH ZADA^ KLASSA NP. dALEE MY POKAVEM, ^TO DLQ PODOBNYH ZADA^ W OPTIMIZACIONNOJ POSTANOWKE OTSUTSTWU@T \FFEKTIWNYE ALGORITMY POISKA DAVE PRIBLIVENNOGO RE[ENIQ.
rEKOMENDUEMYM PODHODOM K IH RE[ENI@ QWLQETSQ RAZBIENIE NA PODZADA^I p0 :D(p0 ) D(p); Y(p0 ) = Y(p) \ D(p0 ), ANALIZ SLOVNOSTI PODZADA^21I RAZRABOTKA SHEM PEREBORA (SM. W xx10,12) DLQ p0 2 NPC. pRI \TOMDLQ SILXNO NP-POLNYH PODZADA^ NE UDAETSQ ISPOLXZOWATX METOD DINAMI^ESKOGO PROGRAMMIROWANIQ W KA^ESTWE SPOSOBA PEREBORA (IBO,PO-WIDIMOMU, REALIZU@]IE EGO ALGORITMY PSEWDOPOLINOMIALXNY) ISLEDUET ORIENTIROWATXSQ NA SHEMU METODA WETWEJ I GRANIC (xx10,11).x4.
pRIBLIVENNOE RE[ENIE ZADA^KOMBINATORNOJ OPTIMIZACIIoPREDELENIE ZADA^I KOMBINATORNOJ OPTIMIZACII I PRIBLIVENNOGO ALGORITMA EE RE[ENIQ. uTWERVDENIE O RAZNICE MEVDU PRIBLIVENNYM I TO^NYM OPTIMUMOM DLQ ZADA^I O R@KZAKE. oPREDELENIE "-PRIBLIVENNOGO ALGORITMA I POLNOSTX@ POLINOMIALXNOJ PRIBLIVENNOJ SHEMY (ppps). sWQZX MEVDU SU]ESTWOWANIEM ppps IPSEWDOPOLINOMIALXNOSTX@. tEOREMA OB OTSUTSTWII ppps DLQ ZADA^ OPTIMIZACII, SOOTWETSTWU@]IH SILXNO NP-POLNYM ZADA^AMRASPOZNAWANIQ SWOJSTW.
pRIMER ZADA^I O KOMMIWOQVERE.wAVNYJ KLASS MASSOWYH ZADA^ OBRAZU@T ZADA^I DISKRETNOJ(KOMBINATORNOJ) OPTIMIZACII. dLQ OPTIMIZACIONNOJ POSTANOWKIZADA^I p RE[ENIEM KAVDOJ INDIWIDUALXNOJ ZADA^I I2p QWLQETSQPROIZWOLXNAQ REALIZACIQ OPTIMUMAOptp (I) =: max fp (I; z );z2Sp (I)T.E. TAKAQ TO^KA z (I) 2 Sp (I), DLQ KOTOROJ fp (I; z (I)) = Optp (I).zDESX Sp (I) | OBLASTX DOPUSTIMYH ZNA^ENIJ DISKRETNOJ (CELO^ISLENNOJ) PEREMENNOJ z, fp (I; ) : Sp (I) ! Z | CELEWAQ FUNKCIQINDIWIDUALXNOJ ZADA^I I OPTIMIZACII, ZNAK max W POSTANOWKE ZADA^I MOVET BYTX ZAMENEN NA min.bUDEM OBOZNA^ATX S I f TE KOMPONENTY WHODNOGO SLOWA = e(I),OPREDELQ@]EGO PARAMETRY INDIWIDUALXNOJ ZADA^I I 2 p, KOTORYEZADA@T DOPUSTIMU@ OBLASTX (OGRANI^ENIQ ZADA^I) I FUNKCI@ CELI SOOTWETSTWENNO.
nAPRIMER, DLQ zr IMEEM fzr (; z) = hc; zi,Szr () = fz = (z1 ; : : : ; zn )jzj 2 f0; 1g 8j = 1; n I hw; z i K g,S = (n; w; K ) I f = c: zDESX I DALEE ZNAK h; i OBOZNA^AET SKALQRNOE PROIZWEDENIE WEKTOROW.22oPREDELENIE 10. aLGORITM a NAZYWAETSQ PRIBLIVENNYM ALGORITMOM RE[ENIQ MASSOWOJ ZADA^I p OPTIMIZACII, ESLI 8I 2 pON NAHODIT NEKOTORU@ TO^KU IZ DOPUSTIMOJ OBLASTI za (I) 2 Sp (I),PRINIMAEMU@ ZA PRIBLIVENNOE RE[ENIE. zNA^ENIE fp (I; za (I)) NAZYWAETSQ PRIBLIVENNYM ZNA^ENIEM OPTIMUMA I OBOZNA^AETSQ A(I).gOWORITX OB ABSOL@TNOJ POGRE[NOSTI PRIBLIVENNOGO ALGORITMA RE[ENIQ MASSOWOJ ZADA^I OPTIMIZACII (NA KLASSE WSEWOZMOVNYHINDIWIDUALXNYH ZADA^) NE IMEET BOLX[OGO SMYSLA, KAK POKAZYWAETuTWERVDENIE 11.
eSLI P =6 NP, TO NI DLQ KAKOJ KONSTANTYC > 0 NE SU]ESTWUET POLINOMIALXNOGO PRIBLIVENNOGO ALGORITMA aRE[ENIQ zr S OCENKOJ jOptzr (I) A(I)j C 8I 2 zr.dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX NAJDENY TAKIE C I a. pOSTROIM ALGORITM a0 SLEDU@]IM OBRAZOM: 8I 2 zrDOMNOVIM WSE KO\FFICIENTY cj NA C + 1 | POLU^IM INDIWIDUALXNU@ ZADA^U I0 2 zr, K KOTOROJ PRIMENIM ALGORITM a I RAZDELIMPOLU^ENNYJ OTWET NA C + 1, T.E. A0 (I) = A(I0 )=(C + 1). o^EWIDNO, Optzr (I0 ) = (s + 1)Optzr (I) I IZ POLINOMIALXNOSTI ALGORITMA a WYTEKAET POLINOMIALXNOSTX a0 . pRI \TOM EGO TO^NOSTX RAWNAjOptzr (I) A0 (I)j = jOptzr (I0 ) A(I0 )j=(C + 1) C=(C + 1) < 1,T.E.
RAWNA NUL@ (TAK KAK WSE ZNA^ENIQ CELEWOJ FUNKCII CELYE). pOLU^ILI POLINOMIALXNYJ ALGORITM TO^NOGO RE[ENIQ zr. pROWERKAOptzr (I) B POLINOMIALXNA, ZNA^IT, POSTROILI I POLINOMIALXNYJ ALGORITM RE[ENIQ zr W POSTANOWKE RASPOZNAWANIQ SWOJSTW, ^TOS U^ETOM UNIWERSALXNOSTI POSLEDNEJ PROTIWORE^IT UTWERVDENI@ 6.oPREDELENIE 11. pRIBLIVENNYJ ALGORITM a RE[ENIQ MASSOWOJZADA^I p OPTIMIZACII NAZYWAETSQ "-PRIBLIVENNYM ALGORITMOM RE[ENIQ p DLQ NEKOTOROGO " > 0, ESLIjOptp (I) A(I)j < ";8I 2 pjOptp (I)jT.E.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
