Modelele Markov de luare a deciziilor sunt generalizate în direcții diferite, în special, la caz Probleme de reconstrucție Markov. Cea mai utilă generalizare se obține atunci când se consideră timpi de tranziție inegali sau variabili. În modelele simple, se presupune că trecerea de la stare la stare și observarea stării sunt instantanee, iar intervalul de timp dintre tranzițiile de la stare la stare poate fi de lungime variabilă sau aleatorie.

Ori de câte ori se observă o stare, o soluție este selectată și nu poate fi schimbată până când procesul trece într-o stare nouă, unde este selectată o nouă soluție etc. Acest model este o combinație între teoria lanțului Markov și teoria restaurării; numit de obicei Problema reconstrucției Markov.

Întrebări de test pentru capitolul 6.

1. Din ce componente constă o rețea direcționată?

1. Cum este construită matricea capacității rețelei?

1. Cum se formează matricea fluxului rețelei?

1. De ce se scad matricele de capacitate și flux?

1. Ce este o diagramă de rețea și pentru ce este folosită?

1. Cum se determină orele de început devreme și de terminare timpurie a lucrărilor?

1. Care este flota totală pentru un anumit eveniment din diagrama rețelei?

1. Cum este determinată calea critică?

1. Ce se numește vectorul de stare al unui anumit sistem?

1. Care este traiectoria unui sistem în spațiul de stare?

1. Care este problema controlului optim?

1. Cum este formulat criteriul de optimitate?

1. Ce este programarea dinamică?

1. Formulați principiul optimității Bellman.

1. Care este esența algoritmilor de baleiaj înainte și înapoi atunci când căutați calea cea mai scurtă?

Opțiuni pentru teme pentru capitolul 6.

Pentru rețele în fiecare dintre opțiuni:

1) Aflați debitul maxim de la sursa (1) până la nodul final al rețelei - chiuveta, presupunând că unul dintre numerele din paranteze pentru fiecare arc (i, j) determină capacitatea arcului;

1) Presupunând că arcurile (1)®(2), (1)®(3), etc. definesc unele locuri de muncă, a căror durată minimă și maximă sunt date de numerele indicate sub arcurile corespunzătoare, găsiți calea critică de la evenimentul inițial (1) până la final;

1) Căutați cea mai scurtă cale de la nodul de început până la nodul final al rețelei. Se consideră distanțele dintre nodurile i, j date de unul dintre numerele dintre paranteze.

Să presupunem că există o problemă pe care am rezolvat-o deja prin programare dinamică, de exemplu, eternele numere Fibonacci.
Să o reformulăm puțin. Să avem un vector din care dorim să obținem un vector. Să extindem puțin asupra formulelor: . Puteți vedea că dintr-un vector puteți obține un vector prin înmulțirea cu vreo matrice, deoarece în vectorul final apar doar variabilele adăugate din primul vector. Această matrice este ușor de obținut, aici este: . Să-i numim matricea de tranziție.

Aceasta înseamnă că dacă luăm vectorul și o înmulțim cu matricea de tranziție n - de 1 ori, obținem un vector care conține fib[n] - răspunsul la problemă.

Acum, de ce sunt necesare toate acestea? Înmulțirea matriceală are proprietatea asociativității, adică (dar în același timp nu are comutativitate, ceea ce după părerea mea este surprinzător). Această proprietate ne dă dreptul de a face acest lucru: .

Acest lucru este bun pentru că acum puteți folosi metoda exponențiării rapide, care funcționează în . În total, am putut calcula al N-lea număr Fibonacci ca logaritm al operațiilor aritmetice.

Și acum un exemplu mai serios:

Exemplul #3: Secvența rampei

Soluţie

În primul rând, o soluție fără o matrice de tranziție:

1) Stare dinamică: dp[n] - numărul de secvențe din dinți de ferăstrău de lungime n care se termină cu numărul ultimul. Mai mult, dacă este mai mică == 0, atunci ultima cifră este mai mică decât penultima, iar dacă este mai mică == 1, atunci este mai mare.
2) Valorile inițiale:
pentru ultimul din interval (10): dp = 9 - ultimul dp = ultimul 3) Recalcularea dinamicii:
pentru prev în intervalul (10): dacă prev > last: dp[n] += dp dacă prev< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Răspunsul este suma dp[N] .

Acum trebuie să venim cu un vector inițial și o matrice de tranziție către acesta. Vectorul pare să apară rapid: toate stările indică lungimea secvenței N . Ei bine, matricea de tranziție este derivată analizând formulele de conversie.

Vector de tranziție și matrice

Dinamica pe subsegmente

Exemplul #4: împachetarea unui șir

Să definim un șir comprimat:
1) Un șir format numai din litere este un șir comprimat. Ea se strânge în sine.
2) Un șir care este concatenarea a două șiruri comprimate A și B. Este decomprimat într-o concatenare de șiruri decomprimate A și B.
3) Șirul D(X) , unde D este un număr întreg mai mare decât 1 și X este un șir comprimat. Este decomprimat într-o concatenare de șiruri D decomprimate din X .
Exemplu: „3(2(A)2(B))C” se extinde la „AABBAABBAABBC” .

Este necesar să aflați din șirul s lungimea celui mai scurt șir comprimat care se decomprimă în el.

Soluţie

Această problemă este rezolvată, așa cum probabil ați ghicit deja, prin dinamica în subsegmente.

1) Stare dinamică: d[l][r] - șir comprimat de lungime minimă, decomprimat în șir s
2) Stări inițiale: toate subșirurile de lungime 1 pot fi comprimate numai în sine.
3) Recalcularea dinamicii:
Cel mai bun răspuns are câteva ultima operatie compresie: fie este doar un șir de la litere mari, sau este concatenarea a două șiruri, sau compresia în sine. Deci haideți să trecem prin toate opțiunile și să o alegem pe cea mai bună.

Dp_len = r - l dp[l][r] = dp_len # Prima opțiune de compresie este doar un șir. pentru i în intervalul (l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Încercați să împărțiți la două subșiruri comprimate pentru cnt în interval (2, dp_len): if (dp_len % cnt == 0): # Dacă nu este divizibil, atunci nu are rost să încerci să împărțim bun = Adevărat pentru j în interval (1, ( dp_len / cnt) + 1 ): # Verificați dacă toate subșirurile cnt sunt aceleași bune &= s == s dacă sunt bune: # Încercați să împărțiți în cnt subșiruri identice și comprimați dp[l][r] = min(dp[l ][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Ordinea recalculării: lungimea substring ascendentă directă sau dinamică leneșă.
5) Răspunsul se află în d.

Exemplul #5:

Dinamica prin subarbori

Exemplul #6: Arborele logic

Este necesar să găsiți numărul minim de modificări în operațiile logice în nodurile interne, astfel încât valoarea de la rădăcină să se schimbe sau să raportați că acest lucru este imposibil.

Soluţie

1) Stare dinamică: d[v][x] - numărul de operații necesare pentru a obține valoarea x la vârful v. Dacă acest lucru nu este posibil, atunci valoarea stării este +inf .
2) Valori inițiale: pentru frunze este evident că valoarea ta poate fi obținută în zero modificări, dar este imposibil să schimbi valoarea, adică se poate, dar numai cu operații +inf.
3) Formula de conversie:
Dacă acest vârf are deja o valoare x , atunci zero. Dacă nu, atunci există două opțiuni: schimbați sau nu operația la vârful curent. Pentru amândoi trebuie să găsiți cea mai buna varianta si alege-l pe cel mai bun.

Dacă operația este „ȘI” și trebuie să obțineți „0”, atunci răspunsul este minimul valorilor d[i] , unde i este fiul lui v.
Dacă operația este „ȘI” și doriți să obțineți „1”, atunci răspunsul este suma tuturor valorilor d[i] , unde i este fiul lui v.
Dacă operația este „SAU” și doriți să obțineți „0”, atunci răspunsul este suma tuturor valorilor d[i] , unde i este fiul lui v .
Dacă operația este „SAU” și trebuie să obțineți „1”, atunci răspunsul este minimul valorilor d[i] , unde i este fiul lui v .

4) Ordinea de recalculare: cel mai simplu mod de a o implementa este leneș - sub forma unei căutări în profunzime de la rădăcină.
5) Răspunsul este d xor 1].

Dinamica pe subseturi

Exemplul #7: Ciclul hamiltonian al greutății minime sau problema vânzătorului ambulant

Soluţie

Deoarece căutăm un ciclu care trece prin toate vârfurile, putem alege orice vârf ca vârf „inițial”. Fie acesta să fie numărul de vârf 0.

1) Starea dinamicii: dp[v] - calea de greutate minimă de la vârful 0 la vârful v, trecând prin toate vârfurile aflate în mască și numai prin acestea.
2) Valori inițiale: dp = 0, toate celelalte stări sunt inițial +inf.
3) Formula de conversie: Dacă al-lea bit din mască este 1 și există o margine de la i la v, atunci:
dp[v] = min(dp[v], dp[i] + w[i][v]) Unde w[i][v] este greutatea muchiei de la i la v .
4) Procedura de recalculare: cea mai simplă și mod convenabil- aceasta este pentru a scrie dinamica leneșă, dar puteți deveni creativ și puteți scrie o enumerare a măștilor în ordinea creșterii numărului de biți de unitate din ea.
5) Răspunsul se află în d[(1<< N) - 1] .

Dinamica după profil

Aceste probleme pot fi rezolvate prin căutare exhaustivă în , unde a este numărul de opțiuni de tiling pentru o celulă. Dinamica după profil optimizează timpul de-a lungul uneia dintre dimensiuni la liniar, lăsând doar un coeficient în exponențial. Veți obține așa ceva: .

Un profil este reprezentat de k (adesea unul) stâlpi, care reprezintă limita dintre partea care a fost deja pavată și partea care nu a fost încă pavată. Acest chenar este doar parțial umplut. Foarte des face parte din starea dinamică.

Aproape întotdeauna statul este un profil și unde este acel profil. Iar tranziția mărește această locație cu unul. Puteți afla dacă este posibil să treceți de la un profil la altul într-un timp liniar față de dimensiunea profilului. Acest lucru poate fi verificat de fiecare dată în timpul recalculării, dar poate fi și precalculat. Vom precalcula o matrice bidimensională cutie - este posibil să trecem de la o mască la alta prin plasarea mai multor figuri, mărind poziția profilului cu una. Dacă precalculați, va dura mai puțin timp pentru finalizare și mai multă memorie.

Exemplul #8: Tigla de domino

Soluţie

Aici profilul este o singură coloană. Este convenabil să-l stocați sub forma unei măști binare: 0 - o celulă până la coloană, 1 - o celulă cu gresie. Adică profiluri totale.

0) Precalcul (opțional): parcurgeți toate perechile de profiluri și verificați dacă puteți trece de la unul la altul. În această problemă, acest lucru este verificat astfel:

Dacă în primul profil există un 1 pe locul următor, atunci în al doilea trebuie să existe un 0, deoarece nu vom putea acoperi această celulă cu nicio cifră.

Dacă în primul profil există un 0 pe locul următor, atunci există două opțiuni - fie în al doilea este 0 sau 1.
Dacă 0, aceasta înseamnă că trebuie să plasăm un domino vertical, ceea ce înseamnă că următoarea celulă poate fi considerată 1. Dacă 1, atunci plasăm un domino vertical și trecem la următoarea celulă.

Exemple de tranziții (din profilul de sus puteți merge la cele de jos și numai acolo):

După aceea, salvați totul din matricea can - 1 dacă puteți merge, 0 dacă nu puteți.
1) Stare dinamică: dp - numărul de tilinguri complete ale primei poziții - 1 coloane cu profilul masca.
2) Stare inițială: dp = 1 - marginea stângă a câmpului - perete drept.
3) Formula de conversie:
dp += dp * poate
4) Ordinea parcurgerii este în ordine crescătoare a poz.
5) Răspunsul este în dp.

Asimptoticele rezultate sunt .

Dinamica de-a lungul unui profil rupt

Acum, după ce ați adăugat o pauză la profil, puteți trece la următoarea stare, adăugând doar o cifră care acoperă celula din stânga a pauzei. Adică, prin creșterea numărului de stări de N ori (trebuie să ne amintim unde este punctul de întrerupere), am redus numărul de tranziții de la o stare la alta de la la . Asimptoticele s-au îmbunătățit de la la .

Tranziții în dinamică de-a lungul unui profil rupt folosind exemplul unei probleme despre placarea cu domino (exemplul nr. 8):

Recuperare răspuns

Fiecare problemă are propriul mod de a recupera răspunsul, dar cele mai frecvente sunt:

• Stocați răspunsul complet la subsarcină lângă valoarea stării dinamicii. Dacă răspunsul este ceva mare, poate necesita prea multă memorie, așa că dacă se poate folosi o altă metodă, de obicei se face.
• Reconstituiți răspunsul, cunoscând strămoșii stării date. Este adesea posibil să reconstruiți un răspuns știind doar cum a fost primit. În același „String Packing”, pentru a restabili răspunsul, puteți stoca doar tipul ultimei acțiuni și stările din care a fost primită.
• Există o modalitate care nu utilizează deloc memoria suplimentară - după recalcularea dinamicii, mergeți de la capăt pe calea cea mai bună și compuneți răspunsul pe parcurs.

Mici optimizări

Memorie

Timp

Înlocuirea statului

Exemplul #9: extinderea numărului

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Printre problemele rezolvate folosind programarea matematică, se poate distinge o clasă separată de probleme care necesită optimizarea proceselor în mai multe etape (mai multe etape). Astfel de probleme se disting prin posibilitatea împărțirii soluției în mai multe etape interconectate. Pentru a rezolva astfel de probleme, se folosește programarea dinamică sau, așa cum se mai numește, programarea în mai multe etape. Metodele sale sunt optimizate pentru a găsi soluția optimă la problemele cu mai multe etape care pot fi împărțite în mai multe etape, pași etc.

Originea termenului

Folosirea cuvântului „dinamic” în nume a implicat inițial că împărțirea în subsarcini ar avea loc în primul rând în timp. Atunci când se utilizează metode dinamice pentru a rezolva probleme de producție, economice și de altă natură în care apare factorul timp, împărțirea acestuia în etape separate nu este dificilă. Dar este posibil să se utilizeze tehnici de programare dinamică în sarcini în care etapele individuale nu sunt legate în timp. Într-o problemă cu mai mulți pași, puteți selecta oricând un parametru sau o proprietate care poate fi folosită pentru a o împărți în pași separati.

Algoritm (metodă) pentru rezolvarea problemelor în mai multe etape

Algoritmul sau metoda de programare dinamică se bazează pe principiul optimizării secvențiale a unei probleme, atunci când soluția unei probleme generale este împărțită într-un număr de soluții la subprobleme individuale și apoi combinată într-o singură soluție. Foarte des, subproblemele individuale se dovedesc a fi aceleași, iar o soluție generală reduce semnificativ timpul de calcul.

O caracteristică a metodei este autonomia de rezolvare a problemei în fiecare etapă individuală, adică indiferent de modul în care procesul a fost optimizat și rezolvat în etapa anterioară, în calculul curent sunt utilizați doar parametrii procesului care o caracterizează în prezent. De exemplu, un șofer care se deplasează de-a lungul drumului ia o decizie cu privire la virajul curent, indiferent de cât și cât timp a condus înainte.

Metoda de sus și metoda de jos

În ciuda faptului că, atunci când se calculează într-o etapă separată de rezolvare a unei probleme, sunt utilizați parametrii procesului în momentul actual, rezultatul optimizării din etapa anterioară afectează calculele etapelor ulterioare pentru a obține cel mai bun rezultat în ansamblu. Programarea dinamică numește acest principiu de soluție metoda optimității, care determină ca strategia optimă de rezolvare a unei probleme, indiferent de deciziile și condițiile inițiale, trebuie urmată de decizii ulterioare în toate etapele pentru a crea o strategie optimă în raport cu starea inițială. După cum putem vedea, procesul de rezolvare a unei probleme este o optimizare continuă a rezultatului în fiecare etapă individuală de la prima până la ultima. Această metodă se numește metoda de programare de sus în jos. Figura prezintă schematic algoritmul soluției de sus în jos. Dar există o clasă de probleme cu mai multe etape în care efectul maxim la ultima etapă este deja cunoscut, de exemplu, am ajuns deja de la punctul A la punctul B și acum vrem să aflăm dacă am condus corect la fiecare precedent stadiu sau dacă ceva ar fi putut fi făcut mai optim. Apare o succesiune recursivă de etape, adică mergem, parcă, „din direcția opusă”. Această metodă de soluție se numește „metoda de programare de jos în sus”.

Uz practic

Programarea dinamică poate fi utilizată în orice domeniu de activitate în care există procese care pot fi împărțite într-un număr de etape mici identice în funcție de un anumit parametru (timp, cantitate, temperatură etc.). Metodele de soluție dinamică sunt cele mai utilizate în teoria controlului și în dezvoltarea sistemelor informatice.

Găsirea căii optime

Folosind optimizarea dinamică, este posibil să se rezolve o clasă largă de probleme de găsire sau optimizare a căii celei mai scurte și alte probleme în care metoda „clasică” de enumerare a posibilelor opțiuni de soluție duce la o creștere a timpului de calcul și uneori este complet inacceptabilă. Problema clasică de programare dinamică este problema rucsacului: dat fiind un anumit număr de obiecte cu o anumită masă și cost, și este necesar să se selecteze un set de obiecte cu costul și masa maximă care să nu depășească volumul rucsacului. O căutare clasică a tuturor opțiunilor în căutarea soluției optime va dura considerabil, dar cu ajutorul metodelor dinamice problema este rezolvată într-un interval de timp acceptabil. Problemele de găsire a celei mai scurte căi pentru logistica transportului sunt de bază, iar metodele de soluții dinamice sunt optim potrivite pentru rezolvarea acestora. Cel mai simplu exemplu al unei astfel de sarcini este construirea celei mai scurte rute folosind un navigator GPS pentru mașină.

Productie

Programarea dinamică este utilizată pe scară largă în rezolvarea unei varietăți de probleme de producție, cum ar fi gestionarea stocurilor pentru a menține numărul necesar de componente la un moment dat, programarea procesului de producție, rutina și revizia echipamentelor, volumul de lucru uniform al personalului, cea mai eficientă distribuție. a fondurilor de investiții etc. Pentru a rezolva problemele de producție folosind metode de programare dinamică, au fost dezvoltate pachete speciale de software care sunt integrate în sistemele populare de management al întreprinderilor, cum ar fi SAP.

Domeniul stiintific

Metodele de programare dinamică sunt utilizate pe scară largă în diverse cercetări științifice. De exemplu, sunt utilizați cu succes în algoritmii de recunoaștere a vorbirii și a imaginilor, atunci când procesează cantități mari de date în sociologie și

Bună, Habrakhabr. În prezent lucrez la un manual despre programarea olimpiadelor, unul dintre paragrafele căruia este dedicat programării dinamice. Mai jos este un extras din acest paragraf. Încercând să explic cât mai simplu acest subiect, am încercat să însoțesc momentele complexe cu ilustrații. Sunt interesat de părerea dumneavoastră despre cât de clar este acest material. De asemenea, aș fi bucuros să primesc sfaturi despre ce alte sarcini ar trebui incluse în această secțiune.

În multe probleme de programare la olimpiade, rezolvarea folosind recursiunea sau căutarea exhaustivă necesită efectuarea unui număr foarte mare de operații. O încercare de a rezolva astfel de probleme, de exemplu, prin căutare exhaustivă, duce la depășirea timpului de execuție.

Cu toate acestea, printre căutarea exhaustivă și unele alte probleme, putem distinge o clasă de probleme care au o singură proprietate bună: a avea soluții la unele subprobleme (de exemplu, pentru un număr mai mic n), puteți găsi o soluție la problema inițială aproape fără a căuta.

Astfel de probleme sunt rezolvate folosind metoda de programare dinamică, iar prin programarea dinamică în sine înțelegem reducerea problemei la subsarcini.

Secvențe

Secvența Fibonacci F n este dat de formulele: F 1 = 1, F 2 = 1,
Fn = F n - 1 + F n- 2 la n> 1. Trebuie să găsiți F n după număr n.

O soluție care poate părea logică și eficientă este rezolvarea utilizând recursiunea:

Int F(int n) ( dacă (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Folosind o astfel de funcție, vom rezolva problema „de la sfârșit” - vom reduce pas cu pas n până ajungem la valori cunoscute.

Dar după cum puteți vedea, așa aparent program simplu deja la n= 40 funcționează vizibil mult timp. Acest lucru se datorează faptului că aceleași date intermediare sunt calculate de mai multe ori - numărul de operații crește cu aceeași viteză cu creșterea numerelor Fibonacci - exponențial.

O cale de ieșire din această situație este salvarea deja găsită rezultate intermediareîn scopul reutilizării lor:

Int F(int n) ( dacă (A[n] != -1) returnează A[n]; dacă (n< 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Soluția dată este corectă și eficientă. Dar pentru această problemă se aplică și o soluție mai simplă:

F = 1; F = 1; pentru (i = 2; i< n; i++) F[i] = F + F;
Această soluție poate fi numită o soluție „de la început” - mai întâi completăm valorile cunoscute, apoi găsim prima valoare necunoscută ( F 3), apoi următorul etc., până ajungem la cel dorit.

Aceasta este exact soluția clasică pentru programarea dinamică: am rezolvat mai întâi toate subproblemele (am găsit toate F i Pentru i < n), apoi, cunoscând soluțiile subproblemelor, am găsit răspunsul ( F n = F n - 1 + F n - 2 , F n- 1 și F n- 2 au fost deja găsite).

Programare dinamică unidimensională

Fie ca problema inițială să fie găsirea unui anumit număr T cu datele inițiale n 1 , n 2 , ..., n k. Adică putem vorbi despre funcție T(n 1 , n 2 , ..., n k), a cărui valoare este răspunsul de care avem nevoie. Apoi vom considera sarcinile ca fiind subsarcini
T(i 1 , i 2 , ..., i k) la i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

Următoarea problemă de programare dinamică unidimensională apare în diferite variații.

La n < 32 полный перебор потребует нескольких секунд, а при n= 64 căutarea exhaustivă nu este fezabilă în principiu. Pentru a rezolva problema folosind metoda de programare dinamică, reducem problema initiala la subsarcini.

La n = 1, n= 2 raspunsul este evident. Să presupunem că am găsit deja K n - 1 , K n- 2 — numărul de astfel de secvențe de lungime n- 1 și n - 2.

Să vedem cât poate fi lungimea secvenței n. Dacă ultimul său caracter este 0, atunci primul n- 1 — orice succesiune corectă de lungime
n- 1 (nu contează dacă se termină cu zero sau cu unu - 0 urmează). Există doar astfel de secvențe K n- 1 . Dacă ultimul caracter este egal cu 1, atunci penultimul caracter trebuie să fie egal cu 0 (altfel vor fi doi la rând), iar primul
n- 2 caractere - orice succesiune validă de lungime n- 2, numărul de astfel de secvențe este egal K n - 2 .

Prin urmare, K 1 = 2, K 2 = 3, K n = K n - 1 + K n- 2 la n> 2. Adică aceasta sarcina de fapt, se reduce la găsirea numerelor Fibonacci.

Programare dinamică 2D

Iată câteva formulări ale unor astfel de sarcini:

Sarcina 2. n*m celule. Puteți face pași dintr-o celulă spre dreapta sau în jos. Numărați câte moduri puteți ajunge din celula din stânga sus la celula din dreapta jos.

Sarcina 3. Având în vedere un câmp dreptunghiular de dimensiune n*m celule. Puteți face pași dintr-o celulă spre dreapta, în jos sau în diagonală spre dreapta și în jos. Fiecare celulă conține câteva numar natural. Trebuie să ajungeți din celula din stânga sus la celula din dreapta jos. Greutatea traseului este calculată ca suma numerelor din toate celulele vizitate. Este necesar să găsiți un traseu cu greutate minimă.

O trăsătură caracteristică a tuturor acestor probleme este că fiecare rută individuală nu poate trece prin aceeași celulă de două sau mai multe ori.

Să luăm în considerare sarcina 2 mai detaliat La o celulă cu coordonate (. i,j) poate veni doar de sus sau din stânga, adică din celule cu coordonate ( i - 1, j) Și ( i, j - 1):

Astfel, pentru o celulă ( i, j) numărul de rute A[i][j] va fi egal cu
A[j] + A[i], adică problema se reduce la două subsarcini. Această implementare folosește doi parametri − iȘi j- prin urmare, în raport cu această problemă vorbim de programare dinamică bidimensională.

Acum putem parcurge secvențial rândurile (sau coloanele) ale matricei A, găsind numărul de rute pentru celula curentă folosind formula de mai sus. Mai întâi trebuie să puneți numărul 1 în A.

În problema 3, într-o celulă cu coordonate ( i, j) putem obține din celule cu coordonate
(i- 1, j), ( i, j- 1) și ( i - 1, j- 1). Să presupunem că pentru fiecare dintre aceste trei celule am găsit deja traseul greutății minime și am plasat greutățile în sine în W[j], W[i],
W. Pentru a găsi greutatea minimă pentru ( i, j), trebuie să selectați minimul greutăților W[j], W[i], W și să adăugați la acesta numărul scris în celula curentă:

W[i][j] = min(W[j], W[i], W) + A[i][j];

Această sarcină este complicată de faptul că este necesar să se găsească nu numai greutatea minimă, ci și traseul în sine. Prin urmare, într-o altă matrice vom înregistra suplimentar pentru fiecare celulă din ce parte trebuie să o introducem.

Figura următoare prezintă un exemplu de date inițiale și unul dintre pașii algoritmului.

Exact o săgeată duce la fiecare dintre celulele deja trecute. Această săgeată arată din ce parte trebuie să veniți la această celulă pentru a obține greutatea minimă înregistrată în celulă.

După ce treceți întreaga matrice, va trebui să urmăriți traseul în sine din ultima celulă, urmând săgețile în direcția opusă.

Probleme ulterioare

Sarcina 4. Dată o succesiune de numere întregi. Este necesar să se găsească cea mai lungă succesiune strict crescătoare.

Să începem să rezolvăm problema de la început - vom căuta răspunsul, pornind de la primii termeni ai acestei secvențe. Pentru fiecare număr i vom căuta cea mai mare subsecvență crescătoare care se termină cu un element în poziție i. Lasă secvența originală să fie stocată în tabloul A. În tabloul L vom înregistra lungimile subsecvențelor maxime care se termină cu elementul curent. Să găsim toate L[i] pentru 1<= i <= k- 1. Acum puteți găsi L[k] după cum urmează. Căutăm prin toate elementele lui A[i] pentru 1<= i < k- 1. Dacă
A[i]< A[k], то k Al-lea element poate deveni o continuare a subsecvenței care se termină cu elementul A[i]. Lungimea subsecvenței rezultate va fi cu 1 mai mare decât L[i]. Pentru a găsi L[k], trebuie să parcurgeți toate i de la 1 la k - 1:
L[k] = max(L[i]) + 1, unde maximul este luat peste toate i astfel încât A[i]< A[k] и
1 <= i < k.

Aici, maximul setului gol va fi considerat egal cu 0. În acest caz, elementul curent va deveni singurul din secvența selectată și nu va fi o continuare a unuia dintre cele anterioare. După completarea matricei L, lungimea celei mai mari subsecvențe crescătoare va fi egală cu elementul maxim L.

Pentru a restabili subsecvența în sine, puteți stoca și numărul elementului selectat anterior pentru fiecare element, de exemplu, într-o matrice N.

Să luăm în considerare soluția acestei probleme folosind exemplul șirului 2, 8, 5, 9, 12, 6. Deoarece nu există niciun element înainte de 2, subsecvența maximă conține un singur element - L = 1 și nu există niciun element înainte de 2. it - N = 0. Mai mult,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Singurul element mai mic decât A = 5 este A = 2, deci 5 poate deveni o continuare a unei singure subsecvențe - cea care conține 2. Atunci
L = L + 1 = 2, N = 1, deoarece 2 este în poziția numărul 1. În mod similar, mai efectuăm trei pași ai algoritmului și obținem rezultatul final.

Acum selectăm elementul maxim din tabloul L și din tabloul N reconstruim subsecvența în sine 2, 5, 9, 12.

O altă problemă clasică de programare dinamică este problema palindromului.

Sarcina 5. Dat un șir de majuscule ale alfabetului latin. Trebuie să găsiți lungimea celui mai mare palindrom care poate fi obținut prin tăierea unor litere dintr-un șir dat.

Să notăm acest șir cu S și simbolurile sale cu S[i], 1<= i <= n. Vom lua în considerare posibilele subșiruri ale acestui șir cu i th j al-lea simbol, le notăm prin S(i, j). Vom scrie lungimile palindromurilor maxime pentru subșiruri într-o matrice pătrată L: L[i][j] este lungimea palindromului maxim care poate fi obținut din subșir. S(i, j).

Să începem să rezolvăm problema cu cele mai simple subșiruri. Pentru un singur șir de caractere (adică un subșir al formularului S(i, i)) răspunsul este evident - nu este nevoie să taiți nimic, un astfel de șir va fi un palindrom. Pentru un șir de două caractere S(i, i+ 1) sunt posibile două opțiuni: dacă caracterele sunt egale, atunci avem un palindrom, nu este nevoie să tăiați nimic. Dacă personajele nu sunt egale, atunci tăiați pe oricare.

Să ni se dea acum un subșir S(i, j). Dacă primul (S[i]) și ultimul (S[j]) caractere ale subșirului nu se potrivesc, atunci unul dintre ele trebuie șters. Apoi rămânem cu subșirul S(i, j- 1) sau S(i + 1, j) - adică reducem problema la o subsarcină: L[i][j] = max(L[i], L[j]). Dacă primul și ultimul caracter sunt egale, atunci le putem lăsa pe amândouă, dar trebuie să știm soluția problemei S(i + 1, j - 1):
L[i][j] = L + 2.

Să ne uităm la soluția folosind șirul ABACCBA ca exemplu. În primul rând, umplem diagonala matricei cu unități, acestea vor corespunde subșirurilor S(i, i) dintr-un personaj. Apoi începem să ne uităm la subșiruri de lungime doi. În toate subșirurile cu excepția S(4, 5), simbolurile sunt diferite, așa că scriem 1 în celulele corespunzătoare și 2 în L.

Se pare că vom umple matricea în diagonală, începând cu diagonala principală care duce din colțul din stânga sus spre dreapta jos. Pentru subșiruri de lungime 3, se obțin următoarele valori: într-un subșir ABA, prima și ultima literă sunt egale, deci
L = L + 2. În subșirurile rămase, prima și ultima literă sunt diferite.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

Dacă în sarcină este necesar să scoatem nu lungimea, ci palindromul în sine, atunci, pe lângă matricea de lungimi, trebuie să construim o matrice de tranziții - pentru fiecare celulă, amintiți-vă care dintre cazuri a fost implementat (pentru claritate, în figură, în loc de valorile numerice care codifică tranzițiile, sunt desenate săgețile corespunzătoare) .

Un exemplu de rezolvare a unei probleme utilizând metoda de programare dinamică……………………………………………………………..7

Lista surselor utilizate……………………………………………...11

1. Programare dinamică. Noțiuni de bază.

Programare dinamică (DP)în teoria sistemelor informatice, o modalitate de a rezolva probleme complexe prin împărțirea lor în subsarcini mai simple. Se aplică problemelor cu substructură optimă, care arată ca un set de subprobleme suprapuse a căror complexitate este puțin mai mică decât cea inițială. În acest caz, timpul de calcul, în comparație cu metodele „naive”, poate fi redus semnificativ.

Ideea cheie în programarea dinamică este destul de simplă. De regulă, pentru a rezolva o anumită problemă, este necesar să se rezolve părți individuale ale problemei (subsarcini) și apoi să se combine soluțiile subsarcinilor într-o singură soluție generală. Adesea, multe dintre aceste subsarcini sunt aceleași. Abordarea de programare dinamică este de a rezolva fiecare subproblemă o singură dată, reducând astfel numărul de calcule. Acest lucru este util în special în cazurile în care numărul de subsarcini repetate este exponențial mare.

Programarea dinamică este o tehnică matematică care abordează rezolvarea unei anumite clase de probleme, împărțindu-le în părți, probleme mai mici și mai puțin complexe. Totodată, o trăsătură distinctivă este soluţionarea problemelor în etape, la intervale fixe, perioade de timp, care au determinat apariţia termenului de programare dinamică. De remarcat că metodele de programare dinamică sunt folosite cu succes și la rezolvarea problemelor în care factorul timp nu este luat în considerare. În general, aparatul matematic poate fi reprezentat ca programare pas cu pas sau pas cu pas. Rezolvarea problemelor prin metode de programare dinamică se realizează pe baza principiului optimității formulat de R. E. Bellman: comportamentul optim are proprietatea că oricare ar fi starea inițială a sistemului și soluția inițială, soluția ulterioară trebuie să determine comportamentul optim. raportat la starea obţinută ca urmare a soluţiei iniţiale. De aici rezultă că planificarea fiecărei etape trebuie efectuată ținând cont de beneficiul general obținut la finalizarea întregului proces, ceea ce permite optimizarea rezultatului final în funcție de criteriul selectat.

Astfel, programarea dinamică în sens larg este controlul optim al unui proces prin modificarea parametrilor controlați la fiecare pas, și, prin urmare, influențând progresul procesului, modificând starea sistemului la fiecare pas. În general, programarea dinamică este o teorie armonioasă de înțeles și suficient de simplă pentru a fi utilizată în activități comerciale atunci când se rezolvă probleme atât liniare, cât și neliniare.

Programarea dinamică este una dintre ramurile programării optime. Se caracterizează prin metode și tehnici specifice aplicate operațiunilor în care procesul decizional este împărțit în etape (etape). Metodele de programare dinamică sunt utilizate pentru rezolvarea problemelor de optimizare a variantelor cu criterii de optimitate date, cu anumite legături între variabile și funcția obiectiv, exprimate printr-un sistem de ecuații sau inegalități. În acest caz, ca și în problemele rezolvate prin metode de programare liniară, restricțiile pot fi date sub formă de egalități sau inegalități. Totuși, dacă în problemele de programare liniară dependențele dintre funcția de criteriu și variabile sunt în mod necesar liniare, atunci în problemele de programare dinamică aceste dependențe pot fi și neliniare. Programarea dinamică poate fi utilizată atât pentru rezolvarea problemelor asociate cu dinamica unui proces sau sistem, cât și pentru probleme statice asociate, de exemplu, cu alocarea resurselor. Acest lucru extinde semnificativ domeniul de aplicare al programării dinamice pentru rezolvarea problemelor de control. Iar posibilitatea simplificării procesului de soluționare, care se realizează prin limitarea ariei și numărului examinate la trecerea la următoarea etapă de opțiuni, crește avantajele acestui set de metode.

Cu toate acestea, programarea dinamică are și dezavantaje. În primul rând, nu există o metodă unică de soluție universală. Aproape fiecare problemă rezolvată prin această metodă se caracterizează prin propriile caracteristici și necesită căutarea celui mai potrivit set de metode pentru a o rezolva. În plus, volumele mari și complexitatea rezolvării problemelor în mai multe etape cu multe stări duc la necesitatea de a selecta probleme de dimensiuni reduse sau de a utiliza informații comprimate. Acesta din urmă se realizează folosind metode de analiză a opțiunilor și procesarea listei de stări.

Pentru procesele în timp continuu, programarea dinamică este considerată o versiune limitativă a unei scheme de soluții discrete. Rezultatele obţinute în acest caz coincid practic cu cele obţinute prin metodele maxime ale lui L. S. Pontryagin sau Hamilton-Jacobi-Bellman.

Programarea dinamică este utilizată pentru a rezolva probleme în care căutarea unui optim este posibilă printr-o abordare pas cu pas, de exemplu, distribuția investițiilor de capital limitate între noi domenii de utilizare a acestora; elaborarea regulilor de gestionare a cererii sau a stocurilor care stabilesc momentul reaprovizionării și mărimea comenzii de reaprovizionare; elaborarea principiilor de programare a producției și de egalizare a ocupării forței de muncă în condiții de fluctuație a cererii de produse; întocmirea planurilor calendaristice pentru reparațiile curente și majore ale echipamentelor și înlocuirea acestora; cauta cele mai scurte distante de pe reteaua de transport; formarea secvenței de desfășurare a unei operațiuni comerciale etc.