В.Б. Алекссев - Сложные алгоритмы (1132790), страница 3
Текст из файла (страница 3)
pOLU^AEMOB]EE ^ISLO OPERACIJ, STOQ]EE W ( ) W FIGURNYH SKOBKAH. tEPERXOSTAETSQ ZAMETITX, ^TO DLQ MINIMIZACII OB]EGO ^ISLA UMNOVENIJDOSTATO^NO PEREBOROM WYBRATX OPTIMALXNOE MESTO DLQ POSLEDNEJ OPERACII. uTWERVDENIE DOKAZANO.bUDEM RE[ATX PODZADA^I Bij QRUSAMI, OTNOSQ K QRUSU t WSE PODZADA^I S j ; i = t. rASSMOTRIM POSLEDOWATELXNO t = 0; 1; 2; : : : ; n ; 1.pRI t = 0 POLU^IM PODZADA^I Bij , DLQ KOTORYH kii = 0 I SKOBKI WOOB]ENE NADO RASSTAWLQTX.
pRI RE[ENII O^EREDNOJ ZADA^I Bij S j ; i = tWOSPOLXZUEMSQ UTWERVDENIEM. pRI \TOM LEGKO WIDETX, ^TO SPRAWA W ( )BUDUT ISPOLXZOWATXSQ REZULXTATY PODZADA^ QRUSOW t1 < t, KOTORYE UVERE[ENY. tOGDA DLQ WY^ISLENIQ kij PO FORMULE ( ) DOSTATO^NO SDELATX2(j ; i) UMNOVENIJ, 2(j ; i) SLOVENIJ I j ; i ; 1 SRAWNENIJ. oB]EE^ISLO OPERACIJ DLQ WY^ISLENIQ ODNOGO kij NE PREWOSHODIT O(n), A DLQWY^ISLENIQ WSEH kij | NE PREWOSHODIT O(n3) (POSKOLXKU OB]EE ^ISLOPODZADA^ Bij ESTX O(n2)). pRI WY^ISLENII kij UKAZANNYM SPOSOBOM MYNAHODIM I TO s, DLQ KOTOROGO DOSTIGAETSQ MINIMUM W ( ). eSLI MYDLQ WSEH (i; j ) BUDEM FIKSIROWATX \TO s, TO SMOVEM BYSTRO OPTIMALXNORASSTAWITX SKOBKI W ZADA^E B1n (W ISHODNOJ ZADA^E), RAZBIWAQ KAVDOEPROIZWEDENIE POSLEDOWATELXNO OPTIMALXNYM OBRAZOM NA 2 PROIZWEDENIQ.
tEOREMA DOKAZANA.zADA^A O KRAT^AJ[IH PUTQH()-()..,,.10.pUSTX G |POLNYJ ORIENTIROWANNYJ GRAF S n WER[INAMIv1; v2; : : : ; vn : pUSTX KAVDOJ DUGE (vi ; vj ) SOPOSTAWLENO DEJSTWITELXNOE^ISLO dij > 0, LIBO dij = +1. ~ISLO dij TRAKTUETSQ KAK RASSTOQNIE IZ viW vj "NAPRQMU@". dLINA ORIENTIROWANNOGO PUTI IZ vi W vj OPREDELQETSQKAK SUMMA DLIN WSEH DUG \TOGO PUTI (ONA RAWNA +1, ESLI HOTQ BYODNO SLAGAEMOE RAWNO +1). kRAT^AJ[EE RASSTOQNIE dij IZ vi W vjOPREDELIM KAK MINIMUM DLIN PO WSEM ORIENTIROWANNYM PUTQM IZ vi Wvj . sOOTWETSTWU@]IJ PUTX BUDEM NAZYWATX KRAT^AJ[IM. rASSMOTRIMSLEDU@]U@ ZADA^U O KRAT^AJ[IH PUTQH.wHOD: MATRICA D = kdij k PORQDKA n (S^ITAEM, ^TO dii = 0 DLQ WSEHi).NIJ.tREBUETSQ: POSTROITX MATRICU D = kdij k KRAT^AJ[IH RASSTOQ-oTMETIM, ^TO ANALOGI^NU@ ZADA^U DLQ NEPOLNOGO GRAFA MOVNOSWESTI K ZADA^E O POLNOM GRAFE, POLOVIW dij = +1 DLQ NESU]ESTWU@]IH DUG.
eSLI dij = dji DLQ WSEH i; j , TO GRAF G MOVNO S^ITATXNEORIENTIROWANNYM.aLGORITM DLQ UKAZANNOJ ZADA^I, OSNOWANNYJ NA PEREBORE WSEHWOZMOVNYH PUTEJ, IMEET NE MENEE, ^EM \KSPONENCIALXNU@ SLOVNOSTX,POSKOLXKU IZ vi W vj SU]ESTWUET BOLEE (n ; 2)! PUTEJ BEZ POWTORQ@]IHSQWER[IN.tEOREMA. sU]ESTWUET ALGORITM DLQ ZADA^I O KRAT^AJ[IH PUTQH STROQ]IJ PO MATRICE D MATRICU D S ^ISLOM OPERACIJ ARIFMETI^ESKIH I SRAWNENIJ ^ISEL O(n3) GDE n ^ISLO WER[IN W GRAFEdOKAZATELXSTWO wWEDEM SLEDU@]IE (k)PODZADA^I: DLQ KAVDOJ PARY i; j I NATURALXNOGO k > 0 WY^ISLITX dij | MINIMALXNU@ DLINUSREDI WSEH ORIENTIROWANNYH PUTEJ IZ vi W vj , PROHODQ]IH, KROME vi Ivj , TOLXKO PO WER[INAM v1; v2; : : : ; vk (WOZMOVNO TOLXKO PO ^ASTI ILINAPRQMU@ IZ vi W vj ).
eSLI k = 0, TO RAZRE[AETSQ TOLXKO PEREHOD IZ(0)(n)vi W vj "NAPRQMU@". pUSTX D(k) = kd(k)ij k. tOGDA D = D I D = D.bUDEM POSLEDOWATELXNO WY^ISLQTX D(1); D(2); : : : ; D(n).uTWERVDENIE. dLQ L@BYH i; j I k > 0-,,),(|..(k;1) (k;1)(k;1)d(k)ij = min(dij ; dik + dkj ):dOKAZATELXSTWO wSE PUTI IZ vi W Vj , ISPOLXZU@]IE TOLXKO WER[INYv1; v2; : : : ; vk , RASPADA@TSQ NA 2 MNOVESTWA A I B | NE PROHODQ]IH^EREZvk I PROHODQ]IH ^EREZ vk . mINIMALXNAQ DLINA PUTEJ W A RAWNA(k;1)dij PO OPREDELENI@. kAVDYJ PUTX IZ B RAZBIWAETSQ NA 2 ^ASTI:PUTX B1 IZ vi W vk PO WER[INAM v1; v2; : : : ; vk;1 I PUTX B2 IZ vk Wvj PO WER[INAM v1; v2 ; : : : ; vk;1 .
mINIMALXNAQ DLINA PUTI W B1 RAWNA.11d(kik ;1), A W B2 | d(kkj;1). sRAWNIWAQ d(kij ;1) I d(kik ;1) + d(kkj;1) , POLU^AEM d(k)ij .uTWERVDENIE DOKAZANO.zAME^ANIE. wY^ISLQQ d(k)ij OPISANNYM SPOSOBOM, MY, W ^ASTNOSTI, UZNAEM, ISPOLXZOWATX vk ILI NET.tAKIM OBRAZOM, DLQ WY^ISLENIQ D(k) PO D(k;1) DOSTATO^NO n2 SLOVENIJ I n2 SRAWNENIJ ^ISEL, A DLQ WY^ISLENIQ D(1); D(2); : : : ; D(n) = DPO ZADANNOJ MATRICE D = D(0) DOSTATO^NO n3 SLOVENIJ I n3 SRAWNENIJ.tEOREMA DOKAZANA.12mETOD "RAZDELQJ I WLASTWUJ". tEOREMA OREKURRENTNOM NERAWENSTWE.dRUGOJ REKURRENTNYJ METOD POSTROENIQ BYSTRYH ALGORITMOW |\TO METOD, KOTORYJ NAZYWA@T "RAZDELQJ I WLASTWUJ".
w NEM TAKVERE[ENIE ZADA^I SWODITSQ K RE[ENI@ PODZADA^, NO, W OTLI^IE OT METODADINAMI^ESKOGO PROGRAMMIROWANIQ, RAZMERNOSTX PODZADA^ OTLI^AETSQOT RAZMERNOSTI ZADA^I NE NA KONSTANTU, A W KONSTANTU RAZ I PODZADA^IRE[A@TSQ NEZAWISIMO DRUG OT DRUGA. dLQ POLU^ENIQ OCENOK SLOVNOSTITAKIH ALGORITMOW ISPOLXZUETSQ SLEDU@]AQ TEOREMA.tEOREMA (O REKURRENTNOM NERAWENSTWE). pUSTX L(n) MONOTONNO NEUBYWA@]AQ FUNKCIQ NATURALXNOGO PARAMETRA n pUSTX cNATURALXNOE ^ISLO c > 2 I a; b; DEJSTWITELXNYE KONSTANTYPRI^EM a > 0 I PUSTX DLQ WSEH n = ck GDE k L@BOE NATURALXNOE^ISLO (k = 1; 2; 3; : : : ) WYPOLNQETSQ NERAWENSTWOL(n) 6 aL( nc ) + bn:(6)tOGDA PRI STREMLENII n K BESKONE^NOSTI DLQ WSEH n WYPOLNQETSQ8>ESLI > logc a<O (n );L(n) = >O(nlogc a); ESLI < logc a(7):O(n log n); ESLI = logc a|.,,-,-|,,-,,,.dOKAZATELXSTWO. pUSTX n = ck , GDE k = 1; 2; 3; : : : .
tOGDA, PRIMENQQNESKOLXKO RAZ (6), POLU^AEM nnL(n) 6 aL( c ) + bn 6 a(aL( c2 ) + b nc ) + bn =n + a2L n 6cc2 ann26 bn + b c n + a (aL c3 + b c2 ) =2 aa3= bn + bn + bn + a L n3 6ccck;1aank6 : : : 6 bn + bn c + : : : + bn c + a L ck :pUSTX d = max(b; L(1)). tAK KAK cnk = 1, TO2k;1 aaaL(n) 6 dn 1 + c + c + : : : + c+ dak == bn + ab132kaaa1+ + ++ :cccrASSMOTRIM 3 SLU^AQ:a1) logc a < =) < 1 =) L(n) 6 dn const = O(n);ca2) logc a > =) > 1 =)c!k c 2 kacc=)=) L(n) 6 dn 1+ +caa ++ a= dn(8)=) L(n) 6 dak const = O(alogc n) = O(nlogc a) (TAK KAK alogc n = nlogc a);3) logc a = =) a = c =) L(n) 6 dn(k + 1) = dn(1 + logc n) == O(n log n):pUSTX TEPERX n | L@BOE.
tOGDA SU]ESTWUET NATURALXNOE k, TAKOE,^TO ck < n 6 ck+1. rASSMOTRIM 3 SLU^AQ, U^ITYWAQ, ^TO PO USLOWI@L(n) | NEUBYWA@]AQ FUNKCIQ:1) > logc a =) L(n) 6 L(ck+1) 6 p(ck+1) = pc(ck ) 6 pc n == O(n);2) < logc a =) L(n) 6 L(ck+1) 6 p(ck+1)logc a = pclogc a(ck )logc a 66 panlogc a = O(nlogc a);(9)k+1k3) = logc a =) L(n) 6 L(c ) 6 pc 2k(c ) 6 pc 2n logc n == O(n) log n:tEOREMA DOKAZANA.{z|6const14}~ASTX 2.
sHEMYx 6. rEALIZACIQ NEKOTORYH \ARIFMETI^ESKIH"SISTEM fal W KLASSE sf|rASSMOTRIM TEPERX NEKOTORYE \ARIFMETI^ESKIE" SISTEMY falI POSTROIM REALIZU@]IE IH sf|.sISTEMY Sn, Mn I Wn , SOSTOQ]IE IZ (n + 1), 2n I n fal OT bpx = (x1; : : : ; xn); y = (y1; : : : ; yn) SOOTWETSTWENNO, TAKIE, ^TOjSn(x; y)j = jxj + jyj; jMn(x; y)j = jxj jyj;I, ESLI jxj > jyj, TOjWn(x; y)j = jxj ; jyj;NAZYWA@TSQ (FUNKCIONALXNYM) SUMMATOROM UMNOVITELEM I WY^ITATELEM PORQDKA n SOOTWETSTWENNO.sISTEMA Cn, SOSTOQ]AQ IZ (n + 1) fal OT bp x = (x1; : : : ; x2n ),TAKAQ, ^TO ZNA^ENIE jCn(x)j RAWNO ^ISLU EDINIC W NABORE x, NAZYWAETSQ(FUNKCIONALXNYM) S^ET^IKOM PORQDKA n.w [8] PRIWEDEN SUMMATOR PORQDKA n, IME@]IJ SLOVNOSTX 9n ; 5.mY POSTROIM TAKOJ VE SUMMATOR NESKOLXKO INA^E.tEOREMA 6.1.
sU]ESTWUET SHEMNYJ SUMMATOR PORQDKA n IME@]IJ SLOVOSTX 9n ; 5dOKAZATELXSTWO dLQ n = 1 SUMMATOR 1 POKAZAN NA RIS. 4.4. nARIS. 6.1.A POKAZANA sf| 0 SLOVNOSTI 9, KOTORAQ REALIZUET SISTEMUfal S 0 OT bp x; y I q0 TAKU@, ^TOjS 0 (x; y; q0 )j = x + y + q0 ;T. E. REALIZUET SLOVENIE TREH ODNORAZRQDNYH ^ISEL. dEJSTWITELXNO, NAWYHODE z2 sf| 0 REALIZUETSQ fal x y q0 , A NA WYHODE z1 EDINICAPOQWLQETSQ TOLXKO TOGDA, KOGDA LIBO x = y = 1, LIBO x y = q0 = 1,T.
E. NA WYHODE z1 W sf| 0 REALIZUETSQ falxy _ (x y)q0 = xy _ xq0 _ yq0:sHEMNYJ SUMMATOR n PORQDKA n S WHODNYMI bp x1; : : : ; xn; y1; : : : ; ynI WYHODNYMI bp z0; z1; : : : ; zn MOVNO POSTROITX IZ SUMMATORA n;1PORQDKA (n ; 1) S WHODNYMI bp x2; : : : ; xn; y2; : : : ; yn I WYHODNYMI bpz10 ; z2; : : : ; zn, A TAKVE ODNOJ sf| 0 TAK, KAK \TO POKAZANO NA RIS.
6.2.zAMETIM, ^TO PEREHOD OT SUMMATORA n;1 K SUMMATORU n MODELIRUET,-,..15-SLOVENIE n-RAZRQDNYH ^ISEL W DWA \TAPA: NA PERWOM \TAPE SKLADYWA@TSQ ^ISLA, OBRAZUEMYE (n ; 1) MLAD[IMI RAZRQDAMI, A NA WTOROM\TAPE SKLADYWA@TSQ STAR[IE RAZRQDY I PERENOS, WOZNIK[IJ NA PERWOM\TAPE. o^EWIDNO, ^TOL(n) = 9n ; 5:tEOREMA DOKAZANA.sLEDSTWIE.
L(Sn) 6 9n ; 5:tEOREMA 6.2. sU]ESTWUET SHEMNYJ WY^ITATELX PORQDKA nIME@]IJ SLOVNOSTX NE BOLX[E ^EM 11n ; 5dOKAZATELXSTWO zAMETIM, ^TOjxj = 2n ; 1 ; jxj;GDE x = (x1; : : : ; xn), x = (x1; : : : ; xn), I PO\TOMUWn(x; y) = jxj ; jyj = 2n ; 1 ; (2n ; 1 ; jxj + jyj) = S n(x; y)sLEDOWATELXNO, SHEMNYJ WY^ITATELX PORQDKA n MOVET BYTX POLU^ENIZ SHEMNOGO SUMMATORA PORQDKA n W REZULXTATE INWERTIROWANIQ WHODOWEGO PERWOGO SLAGAEMOGO, A TAKVE WSEH EGO WYHODOW, I IMEET SLOVNOSTXNE BOLX[E, ^EM 11n ; 5.tEOREMA DOKAZANA.rASSMOTRIM TEPERX SLOVNOSTX UMNOVITELQ Mn DLQ UMNOVENIQ DWUH NEOTRICATELXNYH n-RAZRQDNYH DWOI^NYH ^ISEL X =j(x1; x2; : : : ; xn )j I Y = j(y1; y2; : : : ; yn)j.
tAK KAK X < 2n I Y < 2n,TO XY < 22n I DLQ PREDSTAWLENIQ REZULXTATA TREBUETSQ NE BOLEE 2nWYHODOW. oBOZNA^IM ^EREZ LM (n) NAIMENX[EE WOZMOVNOE ^ISLO \LEMENTOW W UMNOVITELE Mn. o^EWIDNO, ^TO LM (1) = 1, TAK KAK UMNOVENIE1-RAZRQDNYH ^ISEL OSU]ESTWLQET \LEMENT KON_@NKCIQ.uTWERVDENIE. sU]ESTWUET sf| DLQ UMNOVENIQ n RAZRQDNOGO^ISLA X NA RAZRQDNOE ^ISLO y S ^ISLOM \LEMENTOW ndEJSTWITELXNO, ESLI X = j(x1; x2; : : : ; xn)j I Xy = Z =j(z1; z2; : : : ; zn )j, TO zi =xiy DLQ WSEH i = 1; 2; : : : ; n.pRI UMNOVENII DWUH n-RAZRQDNYH ^ISEL X I Y \W STOLBIK" NADOn RAZ UMNOVITX X NA 1-RAZRQDNOE ^ISLO (WSEGO n2 KON_@NKCIJ) I ZATEMn ; 1 RAZ SLOVITX ^ISLA DLINOJ NE BOLEE 2n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
