[учебник] Основы оптимизации. Новикова (1998) ([учебник] Основы оптимизации. Новикова (1998).pdf)

n. m . n O W I K O W Aosnowy optimizacii(KURS LEKCIJ)moskwa 19981oTWETSTWENNYJ REDAKTORAKADEMIK ran p. s. kRASNO]EKOWw SVATOJ FORME DAETSQ IZLOVENIE OSNOW TEORII SLOVNOSTI,LINEJNOGO PROGRAMMIROWANIQ (lp) | S OPISANIEM POLINOMIALXNYH ALGORITMOW, CELO^ISLENNOGO lp, MATEMATI^ESKOGO PROGRAMMIROWANIQ (NEOBHODIMYE USLOWIQ \KSTREMUMA PRI OGRANI^ENIQHNERAWENSTWAH, LOKALXNYE METODY BEZUSLOWNOJ OPTIMIZACII, METOD[TRAFOW, IDEI GLOBALXNOJ OPTIMIZACII), SHEM METODOW DINAMI^ESKOGO PROGRAMMIROWANIQ I WETWEJ I GRANIC.rABOTA NAPISANA NA BAZE SEMESTROWOGO KURSA LEKCIJ, ^ITAEMOGOAWTOROM STUDENTAM 4-GO KURSA PROGRAMMISTSKOGO POTOKA FAKULXTETAwmIk mgu, S U^ETOM DOPOLNENIJ I ZAME^ANIJ, UKAZANNYH STUDENTAMI.

aWTOR BLAGODARIT WSEH STUDENTOW, SODEJSTWOWAW[IH IZDANI@\TOGO KURSA I PREDLOVIW[IH ISPRAWLENIQ, SPOSOBSTWU@]IE EGO ULU^[ENI@, W TOM ^ISLE, lASKAWOGO sERGEQ, sANNIKOWA aNDREQ I sWAHINAnIKOLAQ. zAME^ENNYE OPE^ATKI I NETO^NOSTI PROSXBA SOOB]ATX AWTORU PO ADRESU nnovik@ccas.rurABOTA ^ASTI^NO PODDERVANA GRANTOM rffi No.96-01-00786.rECENZENTY: s. k. zAWRIEW,a. w.

lOTOW2c n. m. nOWIKOWA3~ASTX 1. wwedenie w teori` slovnostilITERATURA:1. g\RI m., dVONSON d. wY^ISLITELXNYE MA[INY I TRUDNORE[AEMYE ZADA^I. m.: mIR, 1982.2. pAPADIMITRIU h., sTAJGLIC k. kOMBINATORNAQ OPTIMIZACIQ.m.: mIR, 1985.x1. pONQTIE O SLOVNOSTI RE[ENIQ ZADA^oSNOWNYE OPREDELENIQ: INDIWIDUALXNAQ I MASSOWAQ ZADA^I, KODI SLOVNOSTXROWKA, ALGORITM RE[ENIQ MASSOWOJ ZADA^I, WREMENNAQALGORITMA. kLASSY P I NP (FORMALXNYE OPREDELENIQ, PRIMERY).1. nA WOPROS, DLQ ^EGO NADO IMETX PREDSTAWLENIE O SLOVNOSTI RE[AEMYH ZADA^, NAIBOLEE NAGLQDNYJ OTWET DAN WO WWEDENII K KNIGE[1]. w \TOJ KNIGE TAKVE PRIWODITSQ BOLEE 500 ZADA^ (IZ SAMYH RAZNYH OBLASTEJ, WKL@^AQ TEORI@ GRAFOW I SETEJ, TEORI@ RASPISANIJ,TEORI@ AWTOMATOW I QZYKOW, OPTIMIZACI@ PROGRAMM, BAZY DANNYH,IGRY I GOLOWOLOMKI I T.P.), DLQ KOTORYH W NASTOQ]EE WREMQ NETOSNOWANIJ NADEQTXSQ POSTROITX \FFEKTIWNYE ALGORITMY IH RE[ENIQ.

~TO \TO ZNA^IT FORMALXNO, BUDET RASSKAZANO W DANNOM RAZDELE(xx1{4), A SOOTWETSTWU@]IE PRAKTI^ESKIE WYWODY KAVDYJ ^ELOWEK,TAK ILI INA^E SWQZANNYJ S RAZRABOTKOJ ALGORITMOW I PROGRAMM, DELAET DLQ SEBQ SAM. kROME TOGO, TEORIQ SLOVNOSTI | NOWAQ, MODNAQ,INTENSIWNO RAZWIWA@]AQSQ OBLASTX MATEMATIKI I KIBERNETIKI, EETERMINOLOGIQ [IROKO RASPROSTRANENA W SOWREMENNOJ NAU^NOJ LITERATURE I TREBUET OPREDELENNOGO S NEJ ZNAKOMSTWA.pOQWLENIE WY^ISLITELXNOJ TEHNIKI PRIWELO K TOMU, ^TO WSE REVEPRIHODITSQ RE[ATX OTDELXNU@ KONKRETNU@ ZADA^U, A WSE BOLX[E PISATX PROGRAMMY, RASS^ITANNYE NA CELYJ KLASS ZADA^, POLU^A@]IHSQ ODNA IZ DRUGOJ ZAMENOJ RQDA ISHODNYH DANNYH.

pO\TOMU IMEETSMYSL GOWORITX O SLOVNOSTI NE DLQ ODNOJ INDIWIDUALXNOJ ZADA^I I,A DLQ MASSOWOJ ZADA^I, ILI PROBLEMY p, SOOTWETSTWU@]EJ MNOVESTWU INDIWIDUALXNYH ZADA^.fORMALXNO MASSOWAQ ZADA^A p OPREDELQETSQ10 OB]IM SPISKOM WSEH PARAMETROW ZADA^I (SWOBODNYH PARAMETROW, ZNA^ENIQ KOTORYH NE ZADANY),420 FORMULIROWKOJ SWOJSTW, KOTORYM DOLVEN UDOWLETWORQTX OTWET(RE[ENIE ZADA^I).iNDIWIDUALXNAQ ZADA^A I 2 p POLU^AETSQ IZ p, ESLI WSEM PARAMETRAM PRISWOITX KONKRETNYE ZNA^ENIQ.dLQ PRIMERA RASSMOTRIM ZADA^U KOMMIWOQVERA: NAJTI MINIMALXNYJ MAR[RUT OBHODA GRUPPY OB_EKTOW (USLOWNO GOWORQ, GORODOW)S WOZWRATOM W NA^ALXNU@ TO^KU.

dLQ p KOMMIWOQVERA WWEDEM10 WHODNYE PARAMETRY: ^ISLO GORODOW m ILI MNOVESTWO GORODOWC = fc1 ; : : : ; cm g I NABOR RASSTOQNIJ MEVDU GORODAMIfd(ci ; cj ) > 0 : ci ; cj 2 C; i 6= j g;20 TREBOWANIQ K RE[ENI@: [c(1); : : : ; c(m)] REALIZUETmin"mX1i=1#d(c(i) ; c(i+1) ) + d(c(m) ; c(1) ) ;GDE MINIMUM BERETSQ PO WSEM WOZMOVNYM PERESTANOWKAM NA MNOVESTWE INDEKSOW GORODOW. kONKRETIZIRUEM PARAMETRY 10 , ^TOBY POLU^ITX INDIWIDUALXNU@ ZADA^U I KOMMIWOQVERA: m = 4, d(c1 ; c2 ) = 10,d(c1 ; c3 )d(ci ; cj )= 5, d(c1; c4) = 9, d(c2; c4) = 9, d(c3; c4) = 3, d(c3 ; c2) = 6,= d(cj ; ci).

tOGDA W ZADA^E I OPTIMALXNYM OKAZYWAETSQMAR[RUT [c1 ; c2 ; c4 ; c3 ], REALIZU@]IJ PUTX MINIMALXNOJ DLINY 27.kROME PERWI^NYH PONQTIJ MASSOWOJ I INDIWIDUALXNOJ ZADA^I (pI I) MY BUDEM ISPOLXZOWATX TERMIN ALGORITM I OBOZNA^ENIE a DLQPO[AGOWOJ PROCEDURY (RE[ENIQ ZADA^I), W ^ASTNOSTI MA[INY tX@RINGA ILI PROGRAMMY DLQ |wm. bUDEM GOWORITX, ^TO ALGORITM aRE[AET MASSOWU@ ZADA^U p, ESLI DLQ L@BOJ INDIWIDUALXNOJ ZADA^II 2 p ALGORITM a PRIMENIM K I (T.E. OSTANAWLIWAETSQ ZA KONE^NOE^ISLO [AGOW) I 8I 2 p ALGORITM a DAET RE[ENIE ZADA^I I.

nAPRIMER, DLQ p KOMMIWOQVERA SU]ESTWUET ALGORITM, KOTORYJ RE[AET EENA OSNOWE POLNOGO PEREBORA WSEH MAR[RUTOW (PERESTANOWOK ).bOLX[INSTWO DISKRETNYH I KOMBINATORNYH ZADA^ DOPUSKAET RE[ENIE S POMO]X@ NEKOTOROGO PROCESSA PEREBORA WARIANTOW, ODNAKO^ISLO WOZMOVNYH WARIANTOW RASTET \KSPONENCIALXNO W ZAWISIMOSTIOT RAZMEROW ZADA^I (TAK, W ZADA^E KOMMIWOQVERA m! MAR[RUTOW).5pO\TOMU PEREBORNYE ALGORITMY RE[ENIQ MASSOWYH ZADA^ S^ITA@TSQ NE\FFEKTIWNYMI (MOGUT RE[ATX LI[X NEBOLX[IE INDIWIDUALXNYE ZADA^I). w OTLI^IE OT NIH \FFEKTIWNYMI NAZYWA@TSQ POLINOMIALXNYE ALGORITMY RE[ENIQ MASSOWOJ ZADA^I, T.E.

TAKIE, KOTORYERE[A@T PROIZWOLXNU@ I 2 p ZA WREMQ, OGRANI^ENNOE POLINOMOM OT\RAZMERA" I. nESMOTRQ NA OPREDELENNU@ USLOWNOSTX \TOGO RAZDELENIQ S TO^KI ZRENIQ PRAKTI^ESKOGO S^ETA, ONO OB_QSNQETSQ PREVDEWSEGO TEM, ^TO CENTRALXNYM DLQ DISKRETNOJ OPTIMIZACII QWLQETSQ WOPROS, MOVNO LI POSTROITX ALGORITM RE[ENIQ MASSOWOJ ZADA^I(T.E.

L@BOJ INDIWIDUALXNOJ), NE PEREBIRA@]IJ WSEH ILI PO^TI WSEHWARIANTOW EE RE[ENIQ. eSLI DLQ MASSOWOJ ZADA^I p SU]ESTWUET POLINOMIALXNYJ ALGORITM, EE RE[A@]IJ, ZNA^IT, EE MOVNO RE[ITXNE PUTEM PEREBORA | \FFEKTIWNO. uKAZANNYE ZADA^I p NAZYWA@TSQPOLINOMIALXNYMI. pEREJDEM K IH FORMALXNOMU OPREDELENI@.2. fORMALIZACIQ PROWODITSQ DLQ ZADA^ RASPOZNAWANIQ SWOJSTW.|TO | MASSOWYE ZADA^I, PREDPOLAGA@]IE OTWET \DA" ILI \NET" WKA^ESTWE RE[ENIQ. tAKIM OBRAZOM, W P.20 OPREDELENIQ p RASPOZNAWANIQ SWOJSTW STOIT NEKOTORYJ ALXTERNATIWNYJ WOPROS I RE[ENIEMKAVDOJ INDIWIDUALXNOJ ZADA^I I 2 p QWLQETSQ PRAWILXNOE RASPOZNAWANIE, PRINADLEVIT LI ONA K ZADA^AM S OTWETOM \DA".

pOSLEDNEEPODMNOVESTWO MNOVESTWA INDIWIDUALXNYH ZADA^ BUDEM OBOZNA^ATXY. tEPERX WWEDEM OBOZNA^ENIE D DLQ MNOVESTWA WSEH WOZMOVNYHZNA^ENIJ PARAMETROW, ZADANNYH W P.10 OPREDELENIQ p. o^EWIDNO,^TO NABOR [D(p),Y(p)] POLNOSTX@ HARAKTERIZUET SOOTWETSTWU@]U@ MASSOWU@ ZADA^U p RASPOZNAWANIQ SWOJSTW. nESMOTRQ NA SPECIFI^NOSTX POSTANOWKI, KLASS ZADA^ RASPOZNAWANIQ SWOJSTW QWLQETSQ DOSTATO^NO [IROKIM: PO KRAJNEJ MERE, DLQ L@BOJ ZADA^I DISKRETNOJ OPTIMIZACII MOVNO UKAZATX ANALOGI^NU@ p RASPOZNAWANIQSWOJSTW.

w ^ASTNOSTI, DLQ p KOMMIWOQVERA, ESLI WWESTI W P.10 E]EODIN PARAMETR B | DLINU MAR[RUTA, TO WOPROS W P.20 \SU]ESTWUET LI MAR[RUT DLINY, NE PREWY[A@]EJ B ?" DAET EE PEREFORMULIROWKU KAK ZADA^I RASPOZNAWANIQ SWOJSTW. pOLU^ENNAQ p KOMMIWOQVERA IMEET W LITERATURE OBOZNA^ENIE km (ILI zk [2]), DLQ NEED(km) = fC; fd(ci ; cj ) 2 Z+ j ci ; cj 2 C; i < j g; B 2 Z+ g:zDESX I DALEE Z+ | MNOVESTWO NATURALXNYH ^ISEL, Z | CELYH.dLQ FORMALIZACII \RAZMERA" INDIWIDUALXNOJ ZADA^I SWQVEM S6KAVDOJ PROBLEMOJ p OPREDELENNU@ SHEMU KODIROWANIQ (KODIROWKU).

wWEDEM KONE^NOE MNOVESTWO | ALFAWIT = fi g, NAPRIMER = f0; 1g, A TAKVE MNOVESTWO SLOW NAD ALFAWITOM | PROIZWOLXNYH KONE^NYH POSLEDOWATELXNOSTEJ, SOSTAWLENNYH IZ SIMWOLOWALFAWITA, WOZMOVNO POWTORQ@]IHSQ, = i i : : : in ; ij 2 8ij ;NAPRIMER, PUSTOE MNOVESTWO ; ILI 011000. ~ISLO n NAZYWAETSQ DLINOJ SLOWA I OBOZNA^AETSQ ZNAKOM MODULQ, n = jj. kODIROWKOJ ZADA^I p NAZOWEM TAKOE OTOBRAVENIE e: p! , STAWQ]EE W SOOTWETSTWIEL@BOJ INDIWIDUALXNOJ ZADA^E I 2 p EE KOD e(I) = 2 (SLOWO IZALFAWITA ), ^TO1 WOZMOVNOODNOZNA^NOE DEKODIROWANIE: 8I1 =6 I2 e(I1 ) 6= e(I2 );2 e; e 1 POLINOMIALXNOWY^ISLIMY: SU]ESTWUET ALGORITM, REALIZU@]IJ e; e 1 , I POLINOM p(), DLQ KOTOROGO 8I 2 p WREMQ OPREDELENIQ e(I) I e 1 (e(I)) NE PREWOSHODIT p(je(I)j);3 KODIROWKA NEIZBYTO^NA: DLQ L@BOJ DRUGOJ 0KODIROWKI e0, UDOWLETWORQ@]EJ USLOWIQM 1 ,2 , NAJDETSQ POLINOM p () TAKOJ, ^TO 8I 2p je(I)j < p0(je0(I)j).

nAPRIMER, DLQ ZAPISI CELYH ^ISEL NEIZBYTO^NOJ QWLQETSQ L@BAQ k-I^NAQ SISTEMA S^ISLENIQ S k > 1, KODIROWKA^ISEL TEM VE KOLI^ESTWOM PALO^EK (SLU^AJ k = 1) IZBYTO^NA.12upravnenie 1. pREDLOVITX NEIZBYTO^NU@ KODIROWKU I OCENITX PO PORQDKU DLINU WHODA ZADA^I KOMMIWOQVERA,SRAWNITX POLU^ENNU@ OCENKU S UKAZANNOJ W [1] NA S. 35:m + dlog2 B e + maxfdlog2 d(ci ; cj )ej ci ; cj 2 C g.zDESX I DALEE ZNAKOM de OBOZNA^AETSQ BLIVAJ[EE CELOE SWERHU K^ISLU W SKOBKAH, A bc | CELAQ ^ASTX ^ISLA.nA^INAQ S \TOGO MOMENTA, W xx 1{3 MY BUDEM, KAK PRAWILO, RASSMATRIWATX p RASPOZNAWANIQ SWOJSTW, OGOWARIWAQ DRUGIE SLU^AI OSOBO.pOSLE TOGO KAK DLQ MASSOWOJ ZADA^I p WWEDENA KODIROWKA, S L@BOJ INDIWIDUALXNOJ ZADA^EJ I 2 p BUDET SWQZANO NEKOTOROE SLOWO W ALFAWITE \TOJ KODIROWKI.

sLOWA, KOTORYE SOOTWETSTWU@T INDIWIDUALXNYM ZADA^AM RASPOZNAWANIQ SWOJSTW, IME@]IM OTWET \DA",USLOWIMSQ S^ITATX \PRAWILXNYMI" I MNOVESTWO PRAWILXNYH SLOW W NAZOWEM: QZYKOM. fORMALXNO, QZYK L(p,e) =: e(Y(p))=:= f 2 j | ALFAWIT e; = e(I); I 2 Y(p)g:s ALGORITMOM a RE[ENIQ ZADA^I p RASPOZNAWANIQ SWOJSTW BUDEM ASSOCIIROWATX MA[INU tX@RINGA (PROGRAMMU DLQ DETERMINI7ROWANNOJ MA[INY tX@RINGA) S WHODNYM ALFAWITOM I KONE^NYMISOSTOQNIQMI qY (\DA") I qN (\NET") I ANALOGI^NO NAZOWEM QZYKOMALGORITMA a MNOVESTWO SLOW, PRINIMAEMYH a (S KOTORYMI NA WHODEW SOSTOQNII qY | \DA"),a OSTANAWLIWAETSQL(a) =: f 2 j | ALFAWIT a, I a() = qY g:oPREDELENIE 1.

aLGORITM a RE[AET MASSOWU@ ZADA^U p S KODIROWKOJ e, ESLI L(a) = L(p,e) I 8 2 a OSTANAWLIWAETSQ.oBOZNA^IM ta () WREMQ RABOTY NAD SLOWOM 2 (^ISLO [AGOW)ALGORITMA a DO OSTANOWKI. wREMENNOJ SLOVNOSTX@ ALGORITMA aRE[ENIQ MASSOWOJ ZADA^I p NAZOWEM FUNKCI@ Ta (), OPREDELQEMU@KAKTa (n) = maxta () 8n 2 Z+ :2 : jj<n SLOVNOSTI ALGORITMOW MYtAKIM OBRAZOM, PRI OCENKE WREMENNOJRASS^ITYWAEM NA \HUD[U@" IZ WOZMOVNYH INDIWIDUALXNYH ZADA^(DANNOGO RAZMERA), POSKOLXKU ZARANEE NE IZWESTNO, S KAKOJ KONKRETNOJ ZADA^EJ PRIDETSQ RABOTATX.upravnenie 2.

dATX ALGORITM RASPOZNAWANIQ PROSTOTY ^ISLA, OCENITX WREMENNU@ SLOVNOSTX ALGORITMA.oPREDELENIE kLASS POLINOMIALXNO RAZRE[IMYH ZADA^P =: fL(p,e)j 9a, RE[A@]IJ p S KODIROWKOJ e; 9p() | POLINOM:Ta (n) < p(n) 8n 2 Z+ g:eSLI DLQ ZADA^I p SU]ESTWUET TAKAQ KODIROWKA e, ^TO L(p,e) 2P, TO BUDEM NAZYWATX ZADa^U p POLINOMIALXNO RAZRE[IMOJ ILIPROSTO POLINOMIALXNOJ I POLXZOWATXSQ OBOZNA^ENIEM p2P, OTOVDESTWLQQ MASSOWU@ ZADA^U I QZYK. (s U^ETOM USLOWIQ NEIZBYTO^NOSTIKODA UKAZANNAQ PROCEDURA KORREKTNA, IBO DLQ POLINOMIALXNOJ p POLU^AEM L(p,e) 2 P 8e.)pRIMEROM POLINOMIALXNOJ ZADA^I QWLQETSQ RASPOZNAWANIE ^ETNOSTI CELOGO ^ISLA. (s E]E ODNOJ POLINOMIALXNOJ ZADA^EJ MY WSTRETIMSQ W RAZD.2.) dLQ ZADA^I RASPOZNAWANIQ PROSTOTY ^ISLA (p~)WOPROS O EE POLINOMIALXNOSTI POKA OTKRYT.