Programare dinamică

În informatică , programarea dinamică este o tehnică de proiectare a algoritmilor bazată pe împărțirea problemei în subprobleme și pe utilizarea substructurilor optime .

Istorie

Termenul a fost folosit pentru prima dată în anii 1940 de matematicianul Richard Bellman pentru a descrie procesul de rezolvare a problemelor în care trebuie găsite cele mai bune soluții una după alta. În 1953 a rafinat termenul care și-a luat semnificația modernă. Această metodă a fost concepută pentru analiza sistemelor și scopurilor de inginerie recunoscute de IEEE .

Cuvântul programare din „programare dinamică” nu are nicio influență specială asupra programării computerizate . Inițial termenul de programare dinamică a fost aplicat doar la soluționarea unor tipuri de probleme operaționale în afara ariei computerului , exact ca în cazul programării liniare . Un program este pur și simplu planificarea acțiunii care va fi produsă. De exemplu, o listă vizată de evenimente, în cazul unei performanțe, este uneori numită program. În acest caz, planificarea înseamnă găsirea unui plan de acțiune acceptabil.

În general

Figura 1. Căutați cea mai scurtă cale într-un grafic folosind substructuri optime ; o linie ondulată indică cea mai scurtă cale între vârfurile pe care le conectează; liniile aldine indică calea completă minimă dintre vârful de pornire și cel de sosire.

Substructura optimă înseamnă că soluția optimă pentru subproblemă poate fi utilizată pentru a găsi soluția optimă pentru întreaga problemă. De exemplu, cea mai scurtă cale de la un vârf de pornire la un vârf de sfârșit într-un grafic aciclic poate fi găsită calculând mai întâi cea mai scurtă cale către punctul final de la toate vârfurile adiacente și apoi folosind-o pentru a găsi cea mai bună cale completă, așa cum se arată în Figura 1. În general, o problemă cu o substructură optimă poate fi rezolvată folosind un proces în trei pași:

împărțiți problema în subprobleme mai mici;
rezolvați aceste probleme în mod optim, utilizând acest proces în trei pași recursiv;
utilizați aceste soluții optime pentru a construi o soluție optimă la problema inițială.

La rândul lor, subproblemele sunt rezolvate împărțindu-le în subprobleme și așa mai departe, până când se ajung la unele cazuri ușor de rezolvat.

Figura 2. Graficul subproblemei pentru secvența Fibonacci. Faptul că nu este un copac, ci un DAG indică suprapuneri suprapuse.

A spune că o problemă are subprobleme suprapuse înseamnă a spune că aceleași subprobleme pot fi folosite pentru a rezolva mai multe probleme mai mari. De exemplu, în secvența Fibonacci , F ₃ = F ₁ + F ₂ și F ₄ = F ₂ + F ₃ , pentru calcularea ambelor numere este necesar să se calculeze F ₂ . Deoarece atât F _{3, cât} și F ₄ sunt necesare pentru calculul lui F ₅ , o abordare naivă a calculului lui F ₅ poate duce la calcularea lui F _{2 de} două sau mai multe ori. Acest lucru se aplică ori de câte ori apar probleme de suprapunere: o abordare naivă ar putea pierde timpul recalculând soluția optimă la subproblemele deja rezolvate.

Dimpotrivă, pentru a preveni acest lucru, este necesar să se salveze soluția problemelor deja rezolvate. Deci, dacă mai târziu trebuie să rezolvați aceeași problemă, puteți lua înapoi și reutiliza soluția deja calculată. Această abordare se numește memoizare (nu memorarea , deși acest termen poate fi adecvat). Dacă sunteți sigur că o anumită soluție nu va fi reutilizată, puteți scăpa de ea pentru a economisi spațiu. În unele cazuri, este posibil să se calculeze în avans soluții pentru subprobleme, știind că vor fi necesare mai târziu.

În esență, programarea dinamică folosește:

Programarea dinamică se bazează, în general, pe una dintre următoarele două abordări.

Top-down : derivă direct din formularea recursivă. Problema este împărțită în subprobleme, acestea sunt rezolvate și soluția este amintită, în cazul în care mai trebuie rezolvată. Este o combinație de recursivitate și memoizare.
De jos în sus : toate subproblemele care pot fi necesare sunt rezolvate mai întâi și apoi utilizate pentru a construi soluția la probleme mai mari. Această abordare este puțin mai bună în ceea ce privește dimensiunea stivei și numărul de apeluri funcționale, dar uneori nu este intuitiv să se prevadă toate subproblemele necesare pentru a rezolva o problemă dată.

Unele limbaje de programare pot fi stocate automat cu extensii speciale [1] Arhivat 2 septembrie 2006 la Internet Archive . rezultatul unui apel de funcție cu un anumit set de argumente, pentru a accelera evaluarea (cunoscut sub numele de apel-după-nevoie ). Acest lucru este posibil numai pentru funcțiile care nu au efecte secundare , ceea ce este întotdeauna adevărat în Haskell , dar rareori în limbile imperative.

Exemple

Secvența Fibonacci

O implementare naivă a unei funcții pe care o căutați membrul 'n -m al secvenței Fibonacci , bazat direct pe definiția matematică:

 funcție fib (n)
       dacă n = 0 sau n = 1
           retur n
       altceva
           return fib (n - 1) + fib (n - 2)

Rețineți că, dacă apelați fib(5) , acesta produce un arbore de apel care apelează aceeași funcție de mai multe ori pe aceeași valoare:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

În special, fib(2) fost calculat în întregime de două ori. În exemple mai mari, mult mai multe fib valori, sau subprobleme, sunt recalculate, ceea ce duce la un algoritm de timp exponențială.

Acum, să presupunem că aveți un obiect hartă simplu, m , care mapează fiecare valoare fib calculată la rezultatul său și modificați funcția pentru a o utiliza și actualiza. Funcția rezultată durează doar O ( n ) timp în loc de timp exponențial:

 var m: = hartă (0 → 1, 1 → 1)
   funcție fib (n)
       dacă harta m nu conține cheia n
           m [n]: = fib (n - 1) + fib (n - 2)
       return m [n]

Această tehnică de salvare a valorilor deja calculate se numește memoizare . Aceasta este abordarea desus în jos , deoarece mai întâi problema a fost împărțită în subprobleme, apoi valorile au fost calculate și salvate.

În cazulabordării de jos în fibsus , cea mai mică fib valoarea este mai întâi calculată, apoi cele mai mari valori sunt construite din ea. Această metodă necesită, de asemenea, O ( n ) timp, deoarece conține o buclă care se repetă de n - 1 ori:

 funcție fib (n)
       var previousFib: = 0, currentFib: = 1
       repetați de n - 1 ori
           var newFib: = previousFib + currentFib
           previousFib: = currentFib
           currentFib: = newFib
       returnează currentFib

În ambele exemple, fib(2) a fost calculat o singură dată și apoi utilizat pentru a calcula atât fib(4) și fib(3) , în loc să se calculeze de fiecare dată când sunt calculate aceste din urmă valori.

Tablă de şah

Luați în considerare o tablă de șah cu n × n cutii și o funcție de cost c ( i , j ) care returnează un cost asociat cu caseta i , j (cu i rândul și j coloana). De exemplu (pe o tablă de șah 5 × 5),

 + --- + --- + --- + --- + --- +
5 | 6 | 7 | 4 | 7 | 8 |
  + --- | --- | --- | --- | --- +
4 | 7 | 6 | 1 | 1 | 4 |
  + --- | --- | --- | --- | --- +
3 | 3 | 5 | 7 | 8 | 2 |
  + --- | --- | --- | --- | --- +
2 | 2 | 6 | 7 | 0 | 2 |
  + --- | --- | --- | --- | --- +
1 | 7 | 3 | 5 | 6 | 1 |
  + --- + --- + --- + --- + --- +
    1 2 3 4 5

astfel încât c (1, 3) = 5

Aveți un pion care poate începe în fiecare pătrat din primul nivel și că doriți să cunoașteți cea mai scurtă cale (suma costurilor pătratelor vizitate) pentru a ajunge la ultimul nivel, presupunând că pionul se poate deplasa doar înainte sau în diagonală spre stânga-înainte sau dreapta-înainte. Adică, un pion din (1,3) se poate deplasa la (2,2) (2,3) (2,4)

 + --- + --- + --- + --- + --- +
5 | | | | | |
  + --- | --- | --- | --- | --- +
4 | | | | | |
  + --- | --- | --- | --- | --- +
3 | | | | | |
  + --- | --- | --- | --- | --- +
2 | | x | x | x | |
  + --- | --- | --- | --- | --- +
1 | | | O | | |
  + --- + --- + --- + --- + --- +
    1 2 3 4 5

Această problemă are un subarborod optim : soluția la întreaga problemă constă în soluțiile subproblemelor. Definiți funcția q ( i , j ) ca

q ( i , j ) = costul minim pentru a ajunge la caseta ( i , j )

Dacă este posibil să găsiți valorile acestei funcții pentru toate casetele de la nivelul n , luați minimul și urmați calea inversă pentru a ajunge la calea cea mai scurtă.

Având în vedere orice casetă, este ușor de văzut că q ( i , j ) este egal cu costul minim pentru a ajunge la oricare dintre cele trei casete de mai jos, deoarece acestea sunt singurele din care se poate ajunge, plus c ( i , j ). De exemplu:

 + --- + --- + --- + --- + --- +
5 | | | | | |
  + --- | --- | --- | --- | --- +
4 | | | A | | |
  + --- | --- | --- | --- | --- +
3 | | B | C | D | |
  + --- | --- | --- | --- | --- +
2 | | | | | |
  + --- | --- | --- | --- | --- +
1 | | | | | |
  + --- + --- + --- + --- + --- +
    1 2 3 4 5

q(A)=\min(q(B),\;q(C),\;q(D))\;+\;c(A)

{\ displaystyle q (A) = \ min (q (B), \; q (C), \; q (D)) \; + \; c (A)}

{\ displaystyle q (A) = \ min (q (B), \; q (C), \; q (D)) \; + \; c (A)}

Acum definiți q ( i , j ) în termeni puțin mai generali:

q(i,j)=\left\{{\begin{matrix}\infty &j<1{\mbox{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\mbox{otherwise}}\end{matrix}}\right.

{\ displaystyle q (i, j) = \ left \ {{\ begin {matrix} \ infty & j <1 {\ mbox {or}} j> n \\ c (i, j) & i = 1 \\ \ min (q (i-1, j-1), q (i-1, j), q (i-1, j + 1)) + c (i, j) și {\ mbox {altfel}} \ end {matrix}} \ right.}

{\ displaystyle q (i, j) = \ left \ {{\ begin {matrix} \ infty & j <1 {\ mbox {or}} j> n \\ c (i, j) & i = 1 \\ \ min (q (i-1, j-1), q (i-1, j), q (i-1, j + 1)) + c (i, j) și {\ mbox {altfel}} \ end {matrix}} \ right.}

Această ecuație este destul de simplă. Prima linie este pur și simplu pentru a face recursiunea mai ușoară atunci când aveți de-a face cu unghiuri, astfel încât nu aveți nevoie decât de o singură recursiune. Cea de-a doua linie spune ce se întâmplă la primul nivel, deci aveți ceva de la care să începeți. A treia linie, recursivitatea, este partea importantă. Este practic același lucru ca în exemplul A, B, C, D. Din această definiție este posibil să se creeze un cod direct și recursiv pentru q ( i , j ). În următoarele pseudocoduri, n este dimensiunea plăcii, c(i, j) este funcția de cost, iar min() returnează cea mai mică dintre un număr de valori:

 funcția minCost (i, j)
    dacă j <1 SAU j> n
        întoarce infinitul
    altfel dacă i = 1
        returnează c (i, j)
    altceva    
        retur min (minCost (i-1, j-1), minCost (i-1, j), minCost (i-1, j + 1)) + c (i, j)

Această funcție calculează doar costul căii, nu calea în sine. În curând vom ajunge la cărare; în acest algoritm, ca și în exemplul numerelor Fibonacci, calculul căii este foarte lent, deoarece timpul este pierdut în recalcularea aceleiași căi scurte de mai multe ori. Cu toate acestea, este posibil să se calculeze calea mai repede în modul dejos însus , de exemplu, utilizând o matrice bidimensională q[i, j] în locul funcției anterioare. Acest lucru se datorează faptului că atunci când este utilizată o funcție, aceeași cale este recalculată și este posibil să alegeți în avans ce valoare să calculați.

De asemenea, este nevoie să știm care este calea reală. Problema căii poate fi rezolvată folosind un alt tablou p[i, j] , un tablou predecesor . Această matrice spune în esență din ce cale provine. Luați în considerare următorul cod:

 funcție computeShortestPathArrays ()
     pentru x de la 1 la n
         q [1, x]: = c (1, x)
     pentru y de la 1 la n
         q [y, 0]: = infinit
         q [y, n + 1]: = infinit
     pentru y de la 2 la n
         pentru x de la 1 la n
             m: = min (q [y-1, x-1], q [y-1, x], q [y-1, x + 1])
             q [y, x]: = m + c (y, x) 
             dacă m = q [y-1, x-1]
                 p [y, x]: = -1
             altfel dacă m = q [y-1, x]
                 p [y, x]: = 0
             altceva
                 p [y, x]: = 1

Acum problema este pur și simplu să localizați minimul și să îl imprimați.

 funcție computeShortestPath ()
     computeShortestPathArrays ()
     minIndex: = 1
     min: = q [n, 1] 
     pentru i de la 2 la n 
         dacă q [n, i] <min
             minIndex: = i
             min: = q [n, i]
     printPath (n, minIndex)

funcția printPath (y, x)
     print (x)
     print ("<-")
     dacă y = 2
         print (x + p [y, x])
     altceva
         printPath (y-1, x + p [y, x])

Controlul autorității	Tesauro BNCF 22135 · LCCN (EN) sh85040313 · GND (DE) 4125677-3 · BNF (FR) cb11978098s (dată) · BNE (ES) XX543843 (dată) · NDL (EN, JA) 00.571.739

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică