Н.М. Новикова - Курс лекций (1125270), страница 4
Текст из файла (страница 4)
(-.[2,. 412].),-;,-(-).,,-. .-(Nick Class,,N. Pippenger),,(-).,..,-(),-.-,-,.(|()),nnj=1j=1XXfjczwj zj K g;jjz: zj 2f0;1g 8j=1;:::;n19-,.max-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@KZAKMAKSIMALXNO 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 NERAWENSTW|(),|()-,;().|nXj=1nXcj zj B Ij=1-wj zj KS NATURALXNYMI KO\FFICIENTAMI NP POLNA DOKAZATELXSTWO NESLEDUET IZ UTWERVDENIQ TAK KAK RASSMATRIWAETSQ ^ASTNYJ SLU^AJbln PO\TOMU SM S ILI SdLQ RE[ENIQ zr IZWESTENSLEDU@]IJ METOD DINAMI^ESKOGO PROGRAMMIROWANIQpROIZWOLXNAQ INDIWIDUALXNAQ ZADA^A I2zr POGRUVAETSQ W SEMEJSTWO ZADA^ POISKA|-(8,,.
[1,. 872,. 386]).().-nnXXFi E : z: zj 2f0;1g 8j=i;:::;nf cj zj j wj zj K E g;j=ij =iF1ZNA^ENIE zr i RE[A@TSQ WSE ZADA^I DANNOGO SEMEJSTWA POREKURRENTNYMFORMULAM GDE i UBYWAET S n DO a IMENNO POLOVIMFi E : 8E K; 8i iMEEM 8E ;K; E > K wn;Fn EcnINA^EI 8i n ;:::; Fi EfFi+1 E ; ci Fi+1 E wi g ::fF2 ; c1 F2 w1 g:zi 2f0;1gfci zi Fi+1 E wi zi g F1()=max(0) |.,() = 0= 0(==max1..12:+) =((0,) = max+,1 :) ;()+(0) = max(+(0)+)=()~ISLO ITERACIJ PREDLOVENNOGO ALGORITMA RAWNO nK I TOGO VEPORQDKA BUDET EGO WREMENNAQ SLOVNOSTX oTMETIM ^TO ALGORITM NEQWLQETSQ POLINOMIALXNYM IBO DLQ ZAPISI ^ISLA K TREBUETSQ PORQDKA 2 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 DADIM.,,log-;|..20oPREDELENIE 8.
oBOZNA^IM ^EREZI MAKSIMALXNOE PO MODUL@ CELOE ^ISLO ILI 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 jIjInum( )(-0),-,=.( )|(-)8I 2 p,()( ( ))(,num( )).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 PREWOSHODQTPOLINOMA OT DLINY WHODA:.(,-).,-,pp() fI 2 pjI < 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 NPCpRIMERAMI SILXNO NP POLNYH ZADA^ QWLQ@TSQ wyp I 3-wypKAK SOWPADA@]IE SO SWOIMI POLINOMIALXNYMI SUVENIQMI blnPOSKOLXKU 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 StEOREMA 4. eSLI P 6 NP TO NI DLQ KAKOJ SILXNO NP POLNOJZADA^I NE SU]ESTWUET PSEWDOPOLINOMIALXNOGO ALGORITMA RE[ENIQdOKAZATELXSTWO PROWEDEM OT PROTIWNOGO pUSTX dmt a RE[AET SILXNO NP POLNU@ ZADA^U p I 8I 2 p tA e I < p0 jIjIDLQ POLINOMA p0 ; tOGDA 8I 2 pp() tA e I < p0 jIj;p jIjp00 jIj T E pp() 2 P PROTIWORE^IE S pp() 2 NPC ILI UTWERVDE,=-,. .num( )()-,( ) |-:.-(),(,),),=[1,(-.
123-124].,-..-((),-( ( ))).. .(( ( ))(|,num( ))()) =-NIEMsILXNO 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 p0D p0 D p ; Y p0Y p \ D p0 ANALIZ SLOVNOSTI PODZADA^6.-.,-.-:()()() =()(21),I RAZRABOTKA SHEM PEREBORA SM W xxDLQ p0 2 NPC pRI \TOMDLQ SILXNO NP POLNYH PODZADA^ NE UDAETSQ ISPOLXZOWATX METOD DINAMI^ESKOGO PROGRAMMIROWANIQ W KA^ESTWE SPOSOBA PEREBORA IBOPO WIDIMOMU REALIZU@]IE EGO ALGORITMY PSEWDOPOLINOMIALXNY ISLEDUET ORIENTIROWATXSQ NA SHEMU METODA WETWEJ I GRANIC xx(.10,12).--(-,,)(10,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 : z2Sp(I) fp I;z ;T E TAKAQ TO^KA z I 2 Sp I DLQ KOTOROJ fp I;z IOptp IzDESX Sp IOBLASTX DOPUSTIMYH ZNA^ENIJ DISKRETNOJ CELO^ISLENNOJ PEREMENNOJ z fp I; Sp I ! Z CELEWAQ FUNKCIQ( ) =. .( )max()( ),(( )) =( ) |( ).(),() :( )|,max-INDIWIDUALXNOJ ZADA^I I OPTIMIZACII ZNAKW POSTANOWKE ZADA^I MOVET BYTX ZAMENEN NAbUDEM OBOZNA^ATX S I f TE KOMPONENTY WHODNOGO SLOWA e IOPREDELQ@]EGO PARAMETRY INDIWIDUALXNOJ ZADA^I I 2 p KOTORYEZADA@T DOPUSTIMU@ OBLASTX OGRANI^ENIQ ZADA^I I FUNKCI@ CEhc;ziLI SOOTWETSTWENNO nAPRIMER DLQ zr IMEEM fzr ;zSzr fz z1;:::;zn jzj 2 f ; g 8j ;n I hw;zi K gS n;w;K I f c: zDESX I DALEE ZNAK h; i OBOZNA^AET SKALQRNOE PROIZWEDENIE WEKTOROW-min.=( ),,(.() == (= ()),)-(0 1== 1)=,,-.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@oPREDELENIE 11. pRIBLIVENNYJ ALGORITM a RE[ENIQ MASSOWOJZADA^I p OPTIMIZACII NAZYWAETSQ " PRIBLIVENNYM ALGORITMOM RE[ENIQ p DLQ NEKOTOROGO " > ESLI.
.().-.( ),,-,6.--0,jOptp I A I j < ";jOptp I j8I 2 p( )( )( )T E EGO OTNOSITELXNAQ POGRE[NOSTX NE PREWOSHODIT "dLQ " PRIBLIVENNYH ALGORITMOW PRIWEDEM SLEDU@]IJ REZULXTATSDOKAZATELXSTWO KOTOROGO OSNOWANO NA METODE DINAMI^ESKOGO PROGRAMMIROWANIQ I W DANNOM KURSE OPUSKAETSQtEOREMA 5. pUSTX DLQ ZADA^I p OPTIMIZACIISU]ESTWUET PSEWDOPOLINOMIALXNYJ ALGORITM EE RE[ENIQ8I 2 p jOptp I j < p1 jIj; I II < p2 jIj;Optp I. ..-[2,. 439],-.1)2);( )(num( ))23num( )(( ))DLQ NEKOTORYH POLINOMOW p1 ; ; p2 ; 8 e I ; I 2 p PARAMETRY S ZADA@]IE OGRANI^ENIQ I fZADA@]IE CELEWU@ FUNKCI@ NE PERESEKA@TSQ I 8z 2 Sp FUNKCIQCELI fp ;z LINEJNO ZAWISIT OT PARAMETROW fTOGDA 9p ; POLINOM 8" > 9 " PRIBLIVENNYJ ALGORITMA" RE[ENIQ p S WREMENNOJ SLOVNOSTX@ TA" jIj < p jIj; =" :tEOREMA SPRAWEDLIWA NAPRIMER DLQ zr SRAWNITE REZULXTATS UTWERVDENIEMnABOR ALGORITMOW fA" g OPREDELENNYJ W TEOREME NAZYWAETSQ POLNOSTX@ POLINOMIALXNOJ PRIBLIVENNOJ SHEMOJppps RE[ENIQ ZADA^I p OPTIMIZACII nALI^IE ppps LU^[EE^EGO MOVNO OVIDATX PRI RE[ENII NP TRUDNYH ZADA^ k SOVALENI@W CELOM RQDE SLU^AEW NA \TO NELXZQ RASS^ITYWATX TAK KAK IMEETSQtEOREMA 6.
eSLI DLQ p OPTIMIZACII SOOTWETSTWU@]AQ EJ pRASPOZNAWANIQ SWOJSTW QWLQETSQ SILXNO NP POLNOJ I 9p0 POLINOM jOptp I j < p0I 8I 2 p TO PRI USLOWII ^TO P 6 NPDLQ p NE SU]ESTWUET pppsdOKAZATELXSTWO PROWEDEM OT PROTIWNOGO pUSTX ppps SU]ESTWUET pOSTROIM ALGORITM A0 SLEDU@]IM OBRAZOM dLQ L@BOJ INDIWIDUALXNOJ ZADA^I I A0 WYZYWAET A" S " = p0ItOGDA PO OPREDELENI@ " PRIBLIVENNOGO ALGORITMA A" jOptp IA0 I j < jOptp I j= p0< p0POII = p0IUSLOWI@ TEOREMY nO W LEWOJ ^ASTI POLU^ENNOGO NERAWENSTWA BYLO CELOE ^ISLO KOTOROE OKAZYWAETSQ RAWNYM NUL@ KAK NEOTRICATELXNOE MENX[EE tAKIM OBRAZOM ALGORITM A0 TO^EN PRI^EMTA0 jIj TA" jIj < p jIj;p0 0PO OPREDELENI@ pppsIsLEDOWATELXNO ALGORITM A PSEWDOPOLINOMIALEN ^TO PROTIWORE^ITTEOREMEuTWERVDENIE 12. eSLI P 6 NP TO NI DLQ KAKOGO " > NESU]ESTWUET POLINOMIALXNOGO " PRIBLIVENNOGO ALGORITMA RE[ENIQOPTIMIZACIONNOJ POSTANOWKI ZADA^I KOMMIWOQVERAdOKAZATELXSTWO SM W SdLQ ^ASTNOGO SLU^AQ km W KOTOROM FUNKCIQ d ; RASSTOQNIQ MEVDU GORODAMI UDOWLETWORQET NERAWENSTWU TREUGOLXNIKA IZWESTEN PRIBLIVENNYJ POLINOMIALXNYJ ALGORITM kRISTOFIDESASRE[ENIQ km OPTIMIZACII(3)=( ))(:);,,,(,(),);() |:0-5(,,)(1)(11).,-5,().|-,.,,-:( )(num( ))( ) |,,=-,..-..-= 1 ((num( ))+1).-( )( )(( )(num( )) + 1)(num( )) ((num( )) + 1).-,-,(1.) =(),(,(num( )) + 1),.,4.=,0-..[2,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
