Н.М. Новикова - Курс лекций (1125270)
Текст из файла
n m nOWIKOWA..osnowy optimizacii(KURS LEKCIJ)moskwa11998oTWETSTWENNYJ REDAKTORAKADEMIK ran p s kRASNO]EKOWw SVATOJ FORME DAETSQ IZLOVENIE OSNOW TEORII SLOVNOSTILINEJNOGO PROGRAMMIROWANIQ lpS 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 GRANICrABOTA NAPISANA NA BAZE SEMESTROWOGO KURSA LEKCIJ ^ITAEMOGOAWTOROM STUDENTAM 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 ADRESUrABOTA ^ASTI^NO PODDERVANA GRANTOM rffi..,() |,-,-(-,,,),-.,4-,,.-,,,,-,.-nnovik@ccas.ruNo.96-01-00786.rECENZENTY s k zAWRIEWa w lOTOW:....,2n mc..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, KODIROWKA, ALGORITM RE[ENIQ MASSOWOJ ZADA^I, WREMENNAQSLOVNOSTXALGORITMA.
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 OPREDELQETSQ0 OB]IM SPISKOM WSEH PARAMETROW ZADA^I (SWOBODNYH PARAME1TROW, ZNA^ENIQ KOTORYH NE ZADANY),40 FORMULIROWKOJ SWOJSTW KOTORYM DOLVEN UDOWLETWORQTX OTWETRE[ENIE ZADA^IiNDIWIDUALXNAQ ZADA^A I 2 p POLU^AETSQ IZ p ESLI WSEM PARAMETRAM PRISWOITX KONKRETNYE ZNA^ENIQdLQ PRIMERA RASSMOTRIM ZADA^U KOMMIWOQVERA NAJTI MINIMALXNYJ MAR[RUT OBHODA GRUPPY OB_EKTOW USLOWNO GOWORQ GORODOWS WOZWRATOM W NA^ALXNU@ TO^KU dLQ p KOMMIWOQVERA WWEDEM0 WHODNYE PARAMETRY ^ISLO GORODOW m ILI MNOVESTWO GORODOWC fc1;:::;cmg I NABOR RASSTOQNIJ MEVDU GORODAMI2,().,-.:-(,).1=:fd ci;cj >ci;cj 2 C; i 6 j g0 TREBOWANIQ K RE[ENI@c(1);:::;c(m) REALIZUET(2)0 ::min"m 1X=[;]#d c(i);c(i+1) d c(m);c(1) ;(i=1)+()GDE MINIMUM BERETSQ PO WSEM WOZMOVNYM PERESTANOWKAM NA MNOVESTWE INDEKSOW GORODOW kONKRETIZIRUEM PARAMETRY 0 ^TOBY POLU^ITX INDIWIDUALXNU@ ZADA^U I KOMMIWOQVERA md c1;c2-.d c1;c3d ci;cj1 ,:= 4,(-) = 10,d c1;c4d c2;c4d c3;c4d c3;c2d cj ;ci tOGDA W ZADA^E I OPTIMALXNYM OKAZYWAETSQMAR[RUT c1 ;c2 ;c4 ;c3 REALIZU@]IJ PUTX MINIMALXNOJ DLINYkROME 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 () = 5,()=([() = 9,() = 9,() = 3,() = 6,).],27.()(),-.,,(.
.).,-,().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-,(,!5).pO\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 OTRAZMERA 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^IT 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 0 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 0 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 0 E]EODIN PARAMETR B DLINU MAR[RUTA TO WOPROS W P 0 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 zkDLQ NEE-(-).,.
.,,\".-,,-,(. .),.-,,|,.....|,\.,"\".2--,\"..,[.1,.,]-.-,-:.,,-,|.1,.2,\-?"-.-km fC; fd ci;cj 2 Z+j ci;cj 2 C; i < j g; B 2 Z+g:(D() =([2]),)zDESX I DALEE Z+ MNOVESTWO NATURALXNYH ^ISEL Z CELYHdLQ FORMALIZACII RAZMERA INDIWIDUALXNOJ ZADA^I SWQVEM S|,\"6|.KAVDOJ 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, = i1 i2 :::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 WOZMOVNO ODNOZNA^NOE DEKODIROWANIE: 8I1 6= I2 e(I1 ) 6= e(I2 );1 POLINOMIALXNO WY^ISLIMY: SU]ESTWUET ALGORITM, REA2 e; eLIZU@]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);03 KODIROWKA NEIZBYTO^NA: DLQ L@BOJ DRUGOJ KODIROWKI e , UDO0WLETWORQ@]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.upravnenie 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 d 2 Befd 2 d ci;cj ej ci;cj 2 C gzDESX I DALEE ZNAKOM de OBOZNA^AETSQ BLIVAJ[EE CELOE SWERHU K^ISLU W SKOBKAH A bc CELAQ ^ASTX ^ISLAnA^INAQ S \TOGO MOMENTA W xx MY BUDEM KAK PRAWILO RASSMATRIWATX p RASPOZNAWANIQ SWOJSTW OGOWARIWAQ DRUGIE SLU^AI OSOBOpOSLE 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 DAUSLOWIMSQ S^ITATX PRAWILXNYMI I MNOVESTWOPRAWILXNYH SLOW W NAZOWEM QZYKOM fORMALXNO QZYK L p e : e Y(p) :: f 2 jALFAWIT 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 DETERMINI+log,+ maxlog,1{3()|..,,-,.,.,-,\\",".=-,( |=, ) =( )()=()-(7-ROWANNOJ 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 qYDAa OSTANAWLIWAETSQALFAWIT a I a qY g:L a : f 2 joPREDELENIE 1.
aLGORITM a RE[AET MASSOWU@ ZADA^U p S KODIROWKOJ e ESLI L a L p e I 8 2 a OSTANAWLIWAETSQoBOZNA^IM ta WREMQ RABOTY NAD SLOWOM 2 ^ISLO [AGOWALGORITMA a DO OSTANOWKI wREMENNOJSLOVNOSTX@ ALGORITMA aRE[ENIQ MASSOWOJ ZADA^I p NAZOWEM FUNKCI@ Ta OPREDELQEMU@KAK)(\")(\"),(| \() ="), |,() =-,(() =(, ).)().( ),Ta n 2: jj<n ta 8n 2 Z+:() =max()tAKIM OBRAZOM PRI OCENKE WREMENNOJ SLOVNOSTI ALGORITMOW MYRASS^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.oPREDELENIE2. kLASS POLINOMIALXNO RAZRE[IMYH ZADA^: fL p e j 9a RE[A@]IJ p S KODIROWKOJ e; 9p POLINOMPTa 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 ZAD ^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=((), )(,( ) |:),,(, )a,-.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
