Esența metodelor de programare dinamică. Conceptul de programare dinamică

Majoritatea metodelor de cercetare operațională sunt asociate în primul rând cu sarcini cu un conținut foarte specific. Aparatul clasic al matematicii s-a dovedit a fi de puțin folos pentru rezolvarea multor probleme de optimizare care implică un număr mare de variabile și/sau constrângeri sub formă de inegalități. Nu există nicio îndoială că ideea de a împărți o problemă de dimensiuni mari în subprobleme de dimensiuni mai mici, incluzând doar câteva variabile, și apoi de a rezolva problema generală în părți este atractivă. Pe această idee se bazează metoda de programare dinamică.

Programarea dinamică (DP) este o metodă matematică a cărei creare și dezvoltare aparține în primul rând lui Bellman. Metoda poate fi utilizată pentru a rezolva o gamă foarte largă de probleme, inclusiv probleme de alocare a resurselor, de înlocuire și de gestionare a stocurilor și probleme de încărcare. Caracteristica programării dinamice este abordarea rezolvării unei probleme în etape, fiecare dintre acestea fiind asociată cu o variabilă controlată. Un set de proceduri de calcul recurente (reversibile, periodice) care conectează diferite etape asigură obținerea unei soluții optime acceptabile a problemei în ansamblu la atingerea ultimei etape.

Originea denumirii programare dinamică este probabil legată de utilizarea metodelor DP în probleme de luare a deciziilor la intervale fixe (de exemplu, în problemele de gestionare a stocurilor). Cu toate acestea, metodele DP sunt folosite cu succes și pentru a rezolva probleme în care factorul timp nu este luat în considerare. Din acest motiv, termenul de programare în mai multe etape pare mai adecvat, reflectând natura pas cu pas a procesului de rezolvare a unei probleme.

Principiul fundamental care stă la baza teoriei DP este principiul optimității. În esență, determină procedura pentru o soluție pas cu pas a unei probleme care permite descompunerea (aceasta este o modalitate mai acceptabilă decât rezolvarea directă a problemei în formularea originală) folosind proceduri de calcul recurente.

Programarea dinamică permite planificarea optimă a proceselor controlate. Prin „controlat” înțelegem procesele al căror curs îl putem influența într-o măsură sau alta.

Cerințe preliminare pentru programarea dinamică:

· Caracteristicile sistemului depind doar de starea dată a sistemului, și nu de modul în care sistemul a ajuns în această stare.
· Trecerea unui sistem de la o stare la alta durează un anumit număr finit de pași.
· Fiecare etapă (Alegerea unei soluții specifice) este asociată cu un anumit efect (efectul economic este înțeles ca valoarea funcției obiective a problemei). Efectul deciziei luate depinde de starea actuală în care se află obiectul de management și de decizia (impactul) de management luată.
· Efectul general pe mai multe etape este suma efectelor de la fiecare pas.

Substructura optimă în programarea dinamică înseamnă că soluția optimă pentru subprobleme mai mici poate fi utilizată pentru a rezolva problema inițială. De exemplu, calea cea mai scurtă dintr-un grafic de la un vârf (notat cu s) la altul (notat cu t) poate fi găsită după cum urmează: mai întâi, calculăm calea cea mai scurtă de la toate vârfurile adiacente lui s la t și apoi, luând ținând cont de greutățile muchiilor care leagă s cu vârfurile adiacente, alegeți cea mai bună cale către t (prin care vârf este cel mai bine să treceți). În general, putem rezolva o problemă care are o substructură optimă parcurgând următorii trei pași.

Împărțirea unei sarcini în subsarcini mai mici.

Găsirea soluției optime pentru subprobleme este recursivă, folosind același algoritm în trei pași.

Utilizarea soluției obținute la subprobleme pentru a construi o soluție la problema inițială.

Subsarcinile sunt rezolvate prin împărțirea lor în subsarcini de dimensiuni și mai mici etc., până când se ajunge la cazul banal al unei probleme care poate fi rezolvată în timp constant (răspunsul poate fi spus imediat). De exemplu, dacă trebuie să găsim n!, atunci sarcina banală ar fi 1! = 1 (sau 0! = 1).

Subprobleme suprapuse în programarea dinamică înseamnă subprobleme care sunt folosite pentru a rezolva un număr de probleme (nu doar una) de dimensiuni mai mari (adică facem același lucru de mai multe ori). Un exemplu izbitor este calculul șirului Fibonacci, $F_3 = F_2 + F_1$ Și $F_4 = F_3 + F_2$ -- chiar și într-un astfel de caz banal de calcul a doar două numere Fibonacci, am calculat deja $F_2$ de două ori. Dacă continuăm mai departe și numărăm $F_5$ , Acea $F_2$ va fi numărat încă de două ori, deoarece pentru a calcula $F_5$ va fi nevoie din nou $F_3$ Și $F_4$ . Ce se întâmplă este că o abordare recursivă simplă va pierde timpul calculând soluții la problemele pe care le-a rezolvat deja.

Pentru a evita un astfel de curs de evenimente, vom salva soluțiile la subproblemele pe care le-am rezolvat deja, iar când vom avea nevoie din nou de soluția subproblemei, în loc să o calculăm din nou, o vom recupera pur și simplu din memorie. Această abordare se numește caching. De asemenea, putem realiza optimizări suplimentare - de exemplu, dacă suntem absolut siguri că nu vom mai avea nevoie de soluția unei subsarcini, o putem arunca din memorie, eliberându-l pentru alte nevoi, sau dacă procesorul este inactiv și știți că soluția la unele subsarcini care nu au fost încă calculate, vom avea nevoie în viitor, le putem rezolva în avans.

Rezumând cele de mai sus, putem spune că programarea dinamică utilizează următoarele proprietăți ale problemei:

· subsarcini suprapuse;
· substructură optimă;
· capacitatea de a memora soluții la subsarcinile frecvent întâlnite.

Programarea dinamică urmează în general două abordări pentru rezolvarea problemelor:

· Programare dinamică de sus în jos: o problemă este împărțită în subprobleme mai mici, acestea sunt rezolvate și apoi combinate pentru a rezolva problema inițială. Memorarea este folosită pentru a rezolva subproblemele care apar frecvent.
· Programare dinamică de jos în sus: toate sarcinile secundare care vor fi necesare ulterior pentru a rezolva problema inițială sunt calculate în avans și apoi utilizate pentru a construi o soluție la problema inițială. Această metodă este mai bună decât programarea de sus în jos în ceea ce privește dimensiunea stivei necesare și numărul de apeluri de funcții, dar uneori nu este ușor să știm dinainte ce subprobleme va trebui să rezolvăm mai târziu.

Limbajele de programare își pot aminti rezultatul unui apel de funcție cu un set specific de argumente (memorizare) pentru a accelera „evaluarea după nume”. Unele limbi au această caracteristică încorporată (de exemplu, Scheme, Common Lisp, Perl), iar unele necesită extensii suplimentare (C++).

Există programarea dinamică în serie, care este inclusă în toate manualele de cercetare operațională, și programarea dinamică non-serială (NSDP), care în prezent este puțin cunoscută, deși a fost descoperită în anii 1960.

Programarea dinamică obișnuită este un caz special de programare dinamică non-serială, când graficul relațiilor variabile este doar o cale. NSDP, fiind o metodă naturală și generală de luare în considerare a structurii unei probleme de optimizare, consideră un set de constrângeri și/sau o funcție obiectivă ca o funcție computabilă recursiv. Acest lucru vă permite să găsiți o soluție în etape, la fiecare etapă folosind informațiile obținute în etapele anterioare, iar eficiența acestui algoritm depinde direct de structura graficului relațiilor dintre variabile. Dacă acest grafic este suficient de rar, atunci cantitatea de calcul în fiecare etapă poate fi menținută în limite rezonabile.

Una dintre principalele proprietăți ale problemelor rezolvate folosind programarea dinamică este aditivitatea. Problemele non-aditive sunt rezolvate prin alte metode. De exemplu, multe probleme de optimizare a investițiilor unei companii sunt non-aditive și sunt rezolvate prin compararea valorii companiei cu și fără investiții.

Programarea dinamică este un subiect căruia îi sunt dedicate destul de multe articole în RuNet, așa că am decis să o abordăm. Acest articol va analiza problemele clasice în secvențe, dinamică unidimensională și bidimensională, va oferi argumente pentru soluții și va descrie diferite abordări ale implementării lor. Tot codul dat în articol este scris în Java.

Despre ce vorbim? Ce este programarea dinamică?

O metodă de rezolvare a unei probleme prin împărțirea acesteia în mai multe subsarcini identice, interconectate în mod recurent. Cel mai simplu exemplu ar fi numerele Fibonacci - pentru a calcula un anumit număr din această secvență, trebuie să calculăm mai întâi al treilea număr adăugând primele două, apoi al patrulea. in acelasi fel bazat pe al doilea și al treilea și așa mai departe (da, am auzit de formula închisă).

Bine, cum să folosești asta?

Soluția unei probleme prin programare dinamică ar trebui să conțină următoarele:

Deci, trebuie să scriu o metodă recursivă pentru a rezolva această problemă? Am auzit că sunt lente.

Desigur, nu este necesar, există și alte abordări pentru implementarea dinamicii. Să le privim folosind următoarea problemă ca exemplu:

Calculați al n-lea termen al șirului dat de formulele:
a 2n = a n + a n-1 ,
a 2n+1 = a n - a n-1 ,
a 0 = a 1 = 1.

Ideea de rezolvare

Aici ni se oferă atât stările inițiale (a 0 = a 1 = 1) cât și dependențele. Singura dificultate care poate apărea este înțelegerea faptului că 2n este condiția egalității unui număr, iar 2n+1 este condiția imparității. Cu alte cuvinte, trebuie să verificăm dacă un număr este par și să-l numărăm în funcție de aceasta folosind diverse formule.

Solutie recursiva

Implementarea evidentă este să scrieți următoarea metodă:

Private static int f(int n)( if(n==0 || n==1) returnează 1; // Verificați valoarea inițială if(n%2==0)( //Verificați paritatea returnează f(n) /2)+f(n/2-1 // Calculați folosind formula pentru indici pare, // referindu-se la valorile anterioare)else( return f((n-1)/2)-f((n); -1) /2-1); // Calculați folosind formula pentru //indici impari, cu referire la valorile anterioare) )

Și funcționează grozav, dar există câteva nuanțe. Dacă dorim să calculăm f(12) , atunci metoda va calcula suma f(6)+f(5) . În același timp, f(6)=f(3)+f(2) și f(5)=f(2)-f(1), adică. vom calcula de două ori valoarea lui f(2). Există o soluție pentru aceasta - memorarea (memorizarea valorilor).

Soluție recursivă cu stocarea în cache a valorii

Ideea de memorare este foarte simplă - odată ce calculăm o valoare, o introducem într-un fel de structură de date. Înainte de fiecare calcul, verificăm dacă valoarea calculată se află în această structură, iar dacă da, o folosim. O matrice plină cu valori de steag poate fi utilizată ca structură de date. Dacă valoarea elementului de la indicele N este egală cu valoarea steagului, atunci nu am calculat-o încă. Acest lucru creează anumite dificultăți, deoarece valoarea steagului nu trebuie să aparțină setului de valori ale funcției, ceea ce nu este întotdeauna evident. Personal, prefer să folosesc un tabel hash - toate operațiunile din acesta sunt efectuate în O(1), ceea ce este foarte convenabil. Cu toate acestea, cu un număr mare de valori, două numere pot avea același hash, ceea ce în mod natural provoacă probleme. În acest caz, ar trebui să utilizați, de exemplu, lemn roșu-negru.

Pentru funcția deja scrisă f(int), valorile de stocare în cache vor arăta astfel:

HashMap static privat cache = nou HashMap (); private static int fcashe(int n)( if(!cache.containsKey(n)))(//Verificați dacă am găsit această valoare cache.put(n, f(n)); //Dacă nu, atunci găsiți și scrieți în table) return cache.get(n);

Nu prea greu, ești de acord? Dar acest lucru elimină un număr mare de operațiuni. Plătiți pentru asta cu un consum suplimentar de memorie.

Calcul secvenţial

Acum să ne întoarcem de unde am început - recursiunea este lentă. Nu atât de lent încât ar cauza probleme reale în viața reală, dar într-o competiție de programare sportivă, fiecare milisecundă contează.

Metoda de calcul secvenţial este potrivită numai dacă funcţia se referă exclusiv la elementele dinaintea ei - acesta este principalul său dezavantaj, dar nu singurul. Problema noastră îndeplinește această condiție.

Esența metodei este următoarea: creăm o matrice de N elemente și o umplem secvenţial cu valori. Probabil ați ghicit deja că în acest fel putem calcula și acele valori care nu sunt necesare pentru răspuns. Într-o parte semnificativă a problemelor de dinamică, acest fapt poate fi omis, deoarece toate valorile sunt adesea necesare pentru răspuns. De exemplu, când căutăm calea cea mai scurtă, nu putem să nu calculăm calea până la un punct, trebuie să reconsiderăm toate opțiunile; Dar în problema noastră trebuie să calculăm aproximativ log 2 (N) valori (în practică mai mult), pentru elementul 922337203685477580 (MaxLong/10) vom avea nevoie de 172 de calcule.

Private static int f(int n)( if(n<2) return 1; //Может, нам и вычислять ничего не нужно? int fs = int[n]; //Создаём массив для значений fs=fs=1; //Задаём начальные состояния for(int i=2; i

Un alt dezavantaj al acestei abordări este consumul relativ mare de memorie.

Crearea unei stive de indexuri

Acum trebuie să scriem, în esență, propria noastră recursivitate. Ideea este următoarea - mai întâi mergem „în jos” de la N la stările inițiale, amintindu-ne argumentele din care va trebui să calculăm funcția. Apoi revenim la „sus”, calculând succesiv valorile din aceste argumente, în ordinea în care am notat-o.

Dependența se calculează după cum urmează:

LinkedList stiva = noua Lista Linked (); stack.add(n); (LinkedList coada = noua Lista Linked (); //Stochează indecși pentru care dependențele nu au fost încă calculate queue.add(n); int dum; while(queue.size()>0)( //Atâta timp cât există ceva de calculat dum = queue.removeFirst(); if(dum%2==0)( //Verifică paritatea if(dum/2>1) )( // Dacă dependența calculată nu aparține stărilor inițiale stack.addLast(dum/2); //Adaugă la coada stivei.add(dum/2); //Salvează în //calculează alte dependențe ) dacă (dum/2-1>1)( //Verificați dacă aparține stărilor inițiale stack.addLast(dum/2-1); //Adăugați la coada stivei.add(dum/2-1); / /Salvare pentru //calculați alte dependențe ) )else( if((dum-1)/2>1)( //Verificați aparținând stărilor inițiale stack.addLast((dum-1)/2); //Adăugați coada .add((dum-1)/2) la stivă ; //Salvare în //calculați alte dependențe ) if((dum-1)/2-1>1)( //Verificați aparținând stivei de stări inițiale. addLast((dum-1)/2-1 / /Add to the stack queue.add((dum-1)/2-1 //Save to //calculate further dependencies ) ) /* Pentru aceasta sarcină, există o modalitate mai elegantă de a găsi toate dependențele, dar una destul de universală este afișată aici */ ) ).

Dimensiunea stivei rezultată este câte calcule trebuie să facem. Așa am obținut numărul 172 menționat mai sus.

Acum extragem indicii unul câte unul și calculăm valorile pentru ei folosind formule - este garantat că toate valorile necesare vor fi deja calculate. Îl vom stoca ca înainte - într-un tabel hash.

HashMap valori = nou HashMap (); valori.put(0,1); //Este important să adăugați stările inițiale //la tabelul de valori values.put(1,1); while(stack.size()>0)( int num = stack.removeLast(); if(!values.containsKey(num))( //Ar trebui să vă amintiți această construcție //din paragraful despre stocarea în cache if(num%2 = =0)( //Verificați valoarea de paritate int = values.get(num/2)+values.get(num/2-1); //Calculați valoarea values.add(num, value); //Place este în tabel )else( int value = values.get((num-1)/2)-values.get((num-1)/2-1); //Calculați valoarea values.add(num, value ); //Puneți-l în tabel) )

Toate valorile necesare au fost calculate, rămâne doar să scrieți

Valori returnate.get(n);

Desigur, această soluție necesită mult mai mult timp, dar merită.

Bine, matematica este frumoasă. Dar sarcinile în care nu este dat totul?

Pentru o mai mare claritate, să analizăm următoarea problemă pentru dinamica unidimensională:

În partea de sus a unei scări care conține N trepte se află o minge, care începe să sară din ele în jos. Mingea poate sări la pasul următor, un pas mai târziu, sau doi pași mai târziu (Adică, dacă mingea se află la pasul a 8-a, atunci se poate muta la a 5-a, a 6-a sau a 7-a.) Determinați numărul posibil. trasee” ale mingii de sus până la pământ.

Ideea de rezolvare

Puteți ajunge la primul pas într-un singur mod - făcând un salt cu o lungime egală cu unu. Puteți ajunge la a doua etapă făcând un salt de lungime 2, sau de la primul pas - doar 2 opțiuni. Poți ajunge la a treia treaptă făcând un salt de trei lungimi, de la prima sau trei trepte. Acestea. doar 4 opțiuni (0->3; 0->1->3; 0->2->3; 0->1->2->3). Acum să ne uităm la al patrulea pas. Puteți ajunge la el de la primul pas - câte un traseu pentru fiecare traseu înainte de acesta, de la al doilea sau de la al treilea - în mod similar. Cu alte cuvinte, numărul de căi către treapta a 4-a este suma traseelor către treptele 1, 2 și 3. Matematic vorbind, F(N) = F(N-1)+F(N-2)+F(N-3) . Vom considera primii trei pași ca fiind stările inițiale.

Implementare prin recursivitate

private static int f(int n)( if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; return f(n-1)+f(n -2)+f(n-3)

Nu este nimic complicat aici.

Pe baza faptului că, în mare, o soluție simplă pe o matrice de N elemente este evidentă, voi demonstra aici o soluție pe o matrice de numai trei.

Int vars = new int; vars=1;vars=2;vars=4; pentru(int i=3; i

Deoarece fiecare valoare ulterioară depinde doar de cele trei anterioare, nicio valoare sub indicele mai mică de i-3 nu ne-ar fi utilă. În codul de mai sus, scriem o nouă valoare în locul celei mai vechi, care nu mai este necesară. Ciclul pentru restul împărțirii cu 3 ne ajută să evităm o grămadă de declarații condiționate. Simplu, compact, elegant.

A fost scris în partea de sus despre un fel de dinamică bidimensională?...

Nu există caracteristici speciale asociate cu dinamica bidimensională, dar, pentru orice eventualitate, voi lua în considerare aici o problemă pentru aceasta.

În tabelul dreptunghiular NxM, la început jucătorul se află în celula din stânga sus. Într-o singură mișcare, i se permite să se deplaseze într-o celulă adiacentă fie la dreapta, fie în jos (este interzis să se deplaseze la stânga și în sus). Numără câte moduri are un jucător pentru a intra în celula din dreapta jos.

Ideea de rezolvare

Logica soluției este complet identică cu cea din problema despre minge și scară - doar acum poți ajunge la celula (x,y) din celule (x-1,y) sau (x, y-1). Total F(x,y) = F(x-1, y)+F(x,y-1) . În plus, puteți înțelege că toate celulele de forma (1,y) și (x,1) au o singură rută - direct în jos sau direct la dreapta.

Implementare prin recursivitate

Pentru numele lui Dumnezeu, nu faceți dinamică 2D prin recursivitate. S-a menționat deja că recursiunea este mai puțin eficientă decât o buclă în ceea ce privește performanța, așa că recursiunea bidimensională este și ea groaznică de citit. Doar într-un exemplu atât de simplu pare ușor și inofensiv.

Private static int f(int i, int j) ( if(i==1 || j==1) return 1; return f(i-1, j)+f(i, j-1); )

Implementare printr-o serie de valori

int dp = int nou; for(int i=0; i O soluție clasică folosind dinamica, nimic neobișnuit - verificăm dacă o celulă este o margine și îi setăm valoarea pe baza celulelor învecinate.

Super, înțeleg totul. Pe ce ar trebui să-mi testez abilitățile?

În concluzie, voi oferi o serie de probleme tipice pentru dinamica unidimensională și bidimensională.

Pericol de explozie

La prelucrarea materialelor radioactive sunt generate două tipuri de deșeuri - foarte periculoase (tip A) și nepericuloase (tip B). Aceleași recipiente sunt folosite pentru a le depozita. După depunerea deșeurilor în containere, acestea din urmă sunt stivuite vertical. O stivă este considerată explozivă dacă conține mai mult de un container de tip A la rând. O stivă este considerată sigură dacă nu este explozivă. Pentru un număr dat de containere N, determinați numărul de tipuri posibile de stive sigure.

Soluţie

Răspunsul este (N+1)-al-lea număr Fibonacci. S-a putut ghici prin simpla calculare a primelor 2-3 valori. S-a putut dovedi cu strictețe prin construirea unui arbore de construcții posibile.

Fiecare element principal este împărțit în două - principal (se termină cu B) și secundar (se termină cu A). Elementele laterale se transformă în cele principale într-o singură iterație (doar B poate fi adăugat la o secvență care se termină cu A). Acest lucru este tipic pentru numerele Fibonacci.

Implementarea

De exemplu, așa:

//Introducerea numărului N de la tastatură N+=2; BigInteger fib = nou BigInteger; fib=fib=BigInteger.ONE; pentru(int i=2; i

Urcând scările

Băiatul s-a apropiat de scările taxei. Pentru a păși pe orice treaptă, trebuie să plătiți suma indicată pe acesta. Băiatul știe să treacă la pasul următor sau să sară peste o treaptă. Trebuie să aflați care este cea mai mică sumă de care va avea nevoie băiatul pentru a ajunge la treapta de sus.

Soluţie

Evident, suma pe care o va da baiatul la treapta a N-a este suma pe care a dat-o inainte plus costul pasului in sine. „Suma pe care a dat-o înainte” depinde de ce pas pășește băiatul în al N-lea - de la (N-1) sau de la (N-2). Trebuie să-l alegi pe cel mai mic.

Implementarea

De exemplu, așa:

Int Imax; //*introduceți numărul de pași de la tastatură* DP = new int; pentru(int i=0; i

Calculator

Există un calculator care efectuează trei operații:
Adăugați unul la numărul X;
Înmulțiți numărul X cu 2;
Înmulțiți numărul X cu 3.

Determinați numărul minim de operații necesare pentru a obține numărul dat N din numărul 1. Tipăriți acest număr și, pe rândul următor, un set de operații executate de forma „111231”.

Soluţie

Soluția naivă este să împărțiți numărul la 3 cât mai lung posibil, în caz contrar la 2 dacă este posibil, în caz contrar scădeți unul și așa mai departe până devine unul. Aceasta este o decizie greșită, pentru că... elimină, de exemplu, posibilitatea de a scădea un număr cu unu și apoi de a împărți la trei, ceea ce ar provoca erori pe numere mari (cum ar fi 32718).

Soluția corectă este să găsim pentru fiecare număr de la 2 la N numărul minim de acțiuni pe baza elementelor anterioare, cu alte cuvinte: F(N) = min(F(N-1), F(N/2), F (N/3) ) + 1 . Trebuie amintit că toți indicii trebuie să fie numere întregi.

Pentru a recrea lista de acțiuni, trebuie să mergeți în direcția opusă și să căutați un indice i astfel încât F(i)=F(N), unde N este numărul elementului în cauză. Dacă i=N-1, scrieți 1 la începutul liniei, dacă i=N/2 - doi, în caz contrar - trei.

Implementarea

int N; //Intrare de la tastatură int a = new int; a= 0; ( int min; for(int i=2; i 1)( if(a[i]==a+1)( ret.insert(0, 1); i--; continua; ) if(i%2==0&&a[i]==a+1)( ret.insert(0, 2); ret.insert(0, 3); System.out.println(ret);

Cel mai ieftin mod

Fiecare celulă a tabelului dreptunghiular N*M conține un număr. Inițial, jucătorul se află în celula din stânga sus. Într-o singură mișcare, i se permite să se deplaseze într-o celulă adiacentă fie la dreapta, fie în jos (este interzis să se deplaseze la stânga și în sus). Când trece printr-o celulă, jucătorului i se iau atâtea kilograme de mâncare câte numărul scris în această celulă (mâncare este luată și pentru prima și ultima celulă din calea lui).
Trebuie să găsiți greutatea minimă a hranei în kilograme, ceea ce oferă jucătorului în colțul din dreapta jos.

Lecția va examina conceptul de programare dinamică și aspectul istoric al apariției sale. Sunt luate în considerare problemele de programare dinamică și câteva exemple de soluții ale acestora.

Conceptul de „programare dinamică” a fost folosit pentru prima dată în anii 1940 de Richard Bellman pentru a descrie procesul de găsire a unei soluții la o problemă în care răspunsul la o problemă poate fi obținut doar după rezolvarea unei alte probleme care o „precedă”.
Astfel, matematicianul american și unul dintre experții de frunte în domeniul matematicii și tehnologiei computerelor - Richard Ernst Bellman- a devenit părintele programării dinamice.

Mai târziu, formularea conceptului a fost rafinată și îmbunătățită la forma sa modernă de către Bellman însuși.

Cuvantul "programare"în contextul „programarii dinamice” se referă de fapt la înțelegerea clasică a programării (scrierea codului într-un limbaj de programare) nu are practic nimic de-a face cu asta. Cuvântul „programare” are același înțeles ca și în sintagma „programare matematică”, care este sinonim cu cuvântul „optimizare”.

De aceea programe va fi folosită ca succesiune optimă de acțiuni pentru a obține o soluție a problemei.

În general, pentru început, definiția informală a programării dinamice ar putea suna asa:

Programare dinamică este o tehnică sau metodă care vă permite să rezolvați unele probleme de combinatorie, optimizare și alte probleme care au o anumită proprietate (proprietatea de co-optimalitate pentru subsarcini).

Probleme de optimizare, de regulă, sunt asociate cu sarcina de a maximiza sau de a minimiza una sau alta funcție obiectivă (de exemplu, maximizarea probabilității ca sistemul să nu se rupă, maximizarea profitului așteptat etc.).

Probleme de combinatorie, de regulă, răspundeți la întrebarea câte obiecte sunt care au anumite proprietăți sau câte obiecte combinatorii sunt care au proprietăți date.

Adică, DP nu rezolvă toate problemele, ci doar unele, o anumită clasă de subsarcini. Dar această clasă de subsarcini este folosită în multe domenii ale cunoașterii: programare, matematică, lingvistică, statistică, teoria jocurilor, economie, informatică etc.

Problemele rezolvate folosind programarea dinamică trebuie să aibă proprietatea de co-optimalitate, care va fi discutat în lecțiile ulterioare.

O explicație informală a proprietății de optimitate a subproblemelor poate fi demonstrată folosind o diagramă:
Există o problemă pe care dorim să o rezolvăm folosind DP, adică. găsiți un plan pentru a o rezolva. Să spunem că această problemă este complexă și nu o putem rezolva imediat. Luăm o mică subproblemă și o rezolvăm mai întâi (pentru x1). Apoi folosind această mică soluție x1 și fără a schimba structura acestei soluții, rezolvăm următoarea problemă cu x1 și x2. etc.

Orez. 1.1. O explicație informală a proprietății de optimitate a subproblemelor

Explicația informală este discutată mai detaliat.

Exemple de probleme rezolvate folosind programarea dinamică

Mai întâi, luați în considerare problemele de optimizare (sarcinile 1-5):

Traseu de lungime optimă

Exemplu: Există o foaie de parcurs prezentată sub forma unui grafic. Scopul nostru: să ajungem de la punct A la punctul B. Acest lucru trebuie făcut în așa fel încât să se minimizeze distanța sau risipa de combustibil.

Funcție obiectivă aici este distanta de la A inainte de B. Acestea. scopul nostru este să minimizăm distanța.

Si ce este variabila de selectie? Pentru a găsi calea cea mai scurtă, trebuie să iei decizii de fiecare dată. Acestea. În fiecare punct sau la fiecare intersecție trebuie luate decizii: unde să cotiți sau să mergi drept.

Important: Din această problemă puteți vedea deja structura generală a problemelor rezolvate folosind programarea dinamică: Fiecare problemă are o funcție obiectiv și o variabilă de alegere.

Înlocuirea unei mașini (minimizarea costurilor)

Exemplu:În fiecare an luăm decizia dacă să conducem mașina veche încă un an și să suportăm costurile de întreținere și întreținere a mașinii vechi sau dacă să vindem mașina și să cumpărăm una nouă (și să suportăm costurile achiziției).

Funcție obiectivă: minimizarea costurilor (fie costurile de întreținere a unei mașini vechi, fie de achiziționarea uneia noi).

Variabila de selectie: luați o decizie în fiecare an să vindeți mașina sau să o păstrați.

Portofoliu de schimb

Exemplu: Joacă la bursă, cumpără acțiuni ale oricăror companii

Funcție obiectivă:

in medie

Variabila de selectie: ce fel de portofoliu de investiții va fi: câte acțiuni și ce companie trebuie să cumpărăm.

Intocmirea unui plan de productie optima (logistica)

Exemplu: Există o fabrică care face mobilă. Fabrica angajează un anumit număr de muncitori care pot produce cantitatea corespunzătoare din anumite mobilier (scaune, mese, dulapuri etc.)

Funcție obiectivă

Variabila de selectie: alegerea câte scaune sau mese trebuie făcute pentru a avea suficientă muncă.

Jocuri (probabilistice sau non probabilistice)

Exemplu: Participarea la diverse jocuri

Funcție obiectivă:

Variabila de selecție aici depinde de jocul specific.

Problemele 1 - 5 sunt exemple de probleme de optimizare.

Combinatorică:

Grafice și arbori

Exemplu: Problema este de a decide câți copaci sunt care au un anumit număr de frunze; sau câte grafice există pentru a rezolva cutare sau cutare sarcină etc.

Problemă de schimb de monede sau numărul de modalități de returnare a schimbului

Exemplu: Există monede de diferite valori, în ce moduri puteți returna schimbarea.

Aceasta este o scurtă descriere a problemelor de programare dinamică care va fi discutată în detaliu mai târziu.

Conceptul de programare dinamică

O explicație informală a optimității subproblemelor DP.

Sa luam in considerare informal idee DP.

Deci, să luăm exemplul unei fabrici de producție de mobilă.

Pentru Pentru a atinge obiectivul de maximizare a profitului, este necesar să se rezolve multe subsarcini:

câte scaune să producă - variabilă X1,
câte tabele să producă - variabila X2,
câți lucrători să angajezi - variabila X3,
... Xn.

Cu un număr mare de subprobleme, este dificil de înțeles cum să rezolvi o astfel de problemă. De obicei, rezolvarea unei probleme mici este mai ușor decât rezolvarea unei probleme mari format din mici.

Prin urmare, DP propune următoarele:

Luăm o subsarcină cu variabila X1 și uităm de subsarcinile rămase pentru moment.

De exemplu, o fabrică produce doar scaune. Directorul are sarcina de a obține profit maxim din vânzarea de scaune.

După ce găsim soluția optimă pentru prima subsarcină, luăm subsarcina pentru două variabile X1 și X2 și o rezolvăm folosind soluția deja găsită pentru prima subsarcină.
Obținem o soluție pentru o subsarcină mai mare, unde apar variabilele X1 și X2. Apoi, folosind soluția obținută, luăm subsarcini care acoperă X1, X2 și X3.
Și așa continuăm până când obținem o soluție pentru întreaga problemă generală.

Idee formală a DP

Adesea, atunci când se pune o problemă, soluția aparent optimă este încercând toate opțiunile posibile. Cu toate acestea, din cauza numărului foarte mare de astfel de opțiuni și, ca urmare, a supraîncărcării memoriei computerului, această metodă nu este întotdeauna acceptabilă.

În plus, poate apărea următoarea întrebare: pentru a găsi, de exemplu, minimul sau maximul, de ce nu găsim derivata? sau să nu folosești mulțimi La Grange sau alte metode de analiză matematică? De ce ai nevoie de DP dacă ai un arsenal mare de mijloace?

Adevărul este că:

Programarea dinamică se bazează pe ideea de a rezolva o anumită problemă prin împărțirea ei în părți separate (subsarcini, etape), rezolvarea acestor subsarcini și apoi combinând aceste soluții într-o singură soluție comună. Adesea, cele mai multe dintre sarcinile secundare sunt exact aceleași.

Este important ca atunci când rezolvăm o problemă mai complexă, să nu rezolvăm din nou o mică subproblemă, ci să folosim răspunsul deja rezolvat la această subproblemă.
Pe un grafic ar putea arăta astfel:

Important: Din acest motiv, împărțirea unei sarcini în subsarcini și rezolvarea acestor subprobleme o singură dată (!), reducând astfel numărul de calcule generale - o metodă mai optimă, care este inerentă programării dinamice

Când rezolvăm o problemă cu derivate, mulțimi La Grange etc., lucrăm cu funcții continue. Când rezolvăm problemele DP, vom lucra în principal cu funcții discrete, așa că este nepotrivit să vorbim aici despre utilizarea funcțiilor continue.
Din acest motiv, în multe probleme, dar nu în toate, utilizarea analizei matematice va fi inacceptabilă.

Un exemplu simplu de rezolvare a problemelor folosind DP

Să luăm în considerare opțiunea de a rezolva problema folosind programarea dinamică.

Exemplu: Este necesar să se calculeze suma n numere: 1 + 2 + 3 + ... + n

Care este presupusa „dificultate” a acestei probleme: că trebuie să luați un număr mare de numere deodată și să obțineți răspunsul.

Să încercăm să aplicăm ideile DP problemei și să o rezolvăm împărțind-o în subsarcini simple.
(În DP este întotdeauna necesar să se determine mai întâi condițiile sau condiția inițială)

Să începem cu suma primului element, adică. luați doar primul element:
F(1) = 1
Acum, folosind soluția pentru primul element, rezolvăm
F(2) = F(1) + 2 = 1 + 2 = 3, adică. trebuie să luați suma primului element și să adăugați al doilea element
F(3) = F(2) + 3 = 6
Continuăm prin analogie și obținem funcția obiectiv:
F(n) = F(n-1) + An

Așadar, ce am făcut: am stabilit ordinea și am identificat subsarcinile, apoi le-am rezolvat pe fiecare, pe baza soluției celei anterioare.

Un exemplu simplu, în care DP este încă folosit în mod nejustificat (artificial), demonstrează principiul ideilor DP.

Să ne uităm la un alt exemplu.

Exemplu: există o scară de n trepte, în fața căreia se află o persoană care se află în spate 1 Treapta poate fie să urce la treapta următoare, fie să sară peste o treaptă. Întrebare: în câte moduri poate ajunge la ultimul pas?

Soluţie:

Să luăm în considerare cele mai simple opțiuni (subsarcini):

Să ne uităm la un exemplu de i pași

Cum putem ajunge la pasul i:

de la pasul i-1 și am putea ajunge la pasul i-1 într-un mod i-1
de la pasul i-2 și am putea ajunge la pasul i-2 într-un mod i-2

De exemplu, cum să ajungi al 4-lea pas:

Acea., numărul total de căi ajunge la pasul i:
f(a i) = f(a i-1) + f(a i-2)

Să determinăm valorile inițiale, de la care să începeți rezolvarea problemei.
Dacă începeți cu 1, atunci formula corespunde găsirii șirului numerelor Fibonacci.

Vedem că problema este în esență combinatorie (adică numărul de moduri de a face ceva) a fost redusă la calcularea unei anumite secvențe recurente.

Exercitiul 1: implementați un exemplu pentru primii zece pași (în esență primele 10 numere din seria Fibonacci), folosind recursiunea.

Completează codul:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: întreg ; procedura getKolSposob(i, n: integer) ; începe scrieln (i+ n, " "); inc(c); if ... atunci getKolSposob(...,... ) end ; începe c: = 1 ; getKolSposob(0, 1); Sfârşit.

var c:intger; procedura getKolSposob(i,n: întreg); începe scrieln(i+n," "); inc(c); if ... atunci getKolSposob(...,...) end; începe c:=1; getKolSposob(0,1); Sfârşit.

Sarcina 2:
Rezolvarea celui de-al 15-lea tip de sarcini de examinare unificată de stat (Grafe. Găsirea numărului de căi).

Bună, Habrakhabr. În prezent lucrez la un manual despre olimpiadele de programare, 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 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

Problema secvenței clasice este următoarea.

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, un astfel de program aparent simplu este deja 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 modalitate de ieșire din această situație este salvarea rezultatelor intermediare deja găsite î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ă

Pentru a înțelege mai bine esența programării dinamice, mai întâi definim mai formal conceptele de sarcină și subsarcină.

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 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 inițială 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ă, această sarcină se reduce de fapt la găsirea numerelor Fibonacci.

Programare dinamică 2D

O problemă clasică în programarea dinamică bidimensională este problema rutelor pe un câmp dreptunghiular.
În diferite formulări, trebuie să numărați numărul de rute sau să găsiți o rută care este cea mai bună într-un anumit sens.

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 un număr 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 prin î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

Luați în considerare problema ulterioară în creștere.

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, începând 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, taiaț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) .

Esența metodei de programare dinamică……………..4

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

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

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 mai ales î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ărui pas 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ție, 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.

Esența metodelor de programare dinamică. Conceptul de programare dinamică

Despre ce vorbim? Ce este programarea dinamică?

Bine, cum să folosești asta?

Deci, trebuie să scriu o metodă recursivă pentru a rezolva această problemă? Am auzit că sunt lente.

Ideea de rezolvare

Solutie recursiva

Soluție recursivă cu stocarea în cache a valorii

Calcul secvenţial

Crearea unei stive de indexuri

Bine, matematica este frumoasă. Dar sarcinile în care nu este dat totul?

Ideea de rezolvare

Implementare prin recursivitate

A fost scris în partea de sus despre un fel de dinamică bidimensională?...

Ideea de rezolvare

Implementare prin recursivitate

Implementare printr-o serie de valori

Super, înțeleg totul. Pe ce ar trebui să-mi testez abilitățile?

Pericol de explozie

Soluţie

Implementarea

Urcând scările

Soluţie

Implementarea

Calculator

Soluţie

Implementarea

Cel mai ieftin mod

Exemple de probleme rezolvate folosind programarea dinamică

Conceptul de programare dinamică

Idee formală a DP

Un exemplu simplu de rezolvare a problemelor folosind DP

Secvențe

Programare dinamică unidimensională

Programare dinamică 2D

Probleme ulterioare

Esența metodei de programare dinamică……………..4

Programare dinamică. Noțiuni de bază.