Exemple de control optim de programare dinamică. A fost scris în partea de sus despre un fel de dinamică bidimensională? Probleme aplicate de programare dinamică
Bună, Habrakhabr. ÎN în prezent Lucrez la ajutor didactic 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 acest subiect cât mai simplu posibil, am încercat momente dificileînsoțit de ilustrații. Sunt interesat de părerea ta 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.
In multe Probleme la olimpiadeîn programare, rezolvarea folosind recursiunea sau forța brută necesită foarte un numar mare operațiuni. 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ăutare și alte probleme, putem distinge o clasă de probleme care au una proprietate buna: având 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 programare dinamică, iar prin programarea dinamică în sine înțelegem reducerea unei sarcini 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, 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ă
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 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
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 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 coordonatele ( 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
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, 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. Să fie stocată secvența originală î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 preluat peste tot 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ă taiț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) .
Secțiunea Programare dinamică este reprezentată de următoarele calculatoare:
- Problemă de alocare a investițiilor. Pentru reconstrucția și modernizarea producției la patru întreprinderi au fost alocate fonduri C = 80 den. unitati Pentru fiecare întreprindere, este cunoscută posibila creștere f i (x) (i = 1, 4) a producției, în funcție de suma alocată.
În problemele de programare dinamică, procesul economic depinde de timp (sau de mai multe perioade de timp), astfel că se găsesc (secvenţial pentru fiecare etapă) o serie de soluţii optime care asigură desfăşurarea optimă a întregului proces în ansamblu. Programarea dinamică este un aparat matematic care permite planificarea optimă a proceselor controlate și a proceselor dependente de timp. Efectuarea optimizării pas cu pas se numește proces decizional în mai multe etape. Un proces economic se numește controlat dacă este posibil să influențeze cursul dezvoltării sale.
Metoda de programare dinamică (DP) se bazează pe principiul optimizării secvenţiale: soluţia problemei originale de optimizare dimensională înaltă este înlocuită cu soluţia unei secvenţe de probleme de optimizare dimensională mică. Condiția principală pentru aplicabilitatea metodei DP este posibilitatea împărțirii procesului decizional într-un număr de pași sau etape similare, fiecare dintre acestea fiind planificată separat, dar ținând cont de rezultatele obținute la alte etape. De exemplu, activitatea unei industrii de-a lungul unui număr de ani de activitate, sau o succesiune de teste utilizate în controlul echipamentelor etc. Unele procese (operații) sunt împărțite în etape în mod firesc, dar există operațiuni care trebuie împărțite în etapează artificial, de exemplu, procesul de ghidare a rachetelor la țintă.
Acest principiu asigură că controlul ales la orice pas nu este cel mai bun la nivel local, ci cel mai bun din punct de vedere al procesului în ansamblu, deoarece acest control este ales luând în considerare consecințele în etapele următoare.
Sa luam in considerare descrierea generală a problemei de programare dinamică.
Lăsați procesul de luare a deciziilor în mai multe etape să fie împărțit în n trepte. Să notăm cu ε 0 starea inițială a sistemului, cu ε 1, ε 2, … ε n– starea sistemului după primul, al doilea, n- al-lea pas. În general, statul
ε k– vector (ε k 1, …, ε k s).
managementîntr-un proces în mai multe etape, se numește un set de soluții (variabile de control). Regatul Unit = (Regatul Unit 1 , ..., u k r) luate la fiecare pas kși transferarea sistemului din starea ε k-1 = (ε k- 1 1 , …, ε k -1 s) pentru a afirma ε k = (ε k 1, …, ε k s).
În procesele economice, managementul constă în distribuirea și redistribuirea fondurilor în fiecare etapă. De exemplu, producția de produse de către orice întreprindere este un proces controlat, deoarece este determinat de modificări în compoziția echipamentelor, volumul livrărilor de materii prime, valoarea finanțării etc. Un set de decizii luate la început a anului, perioada de planificare, pentru a furniza întreprinderii cu materii prime, înlocuirea echipamentelor, precum și suma de finanțare etc este management. S-ar părea că pentru a obține volumul maxim de producție, cel mai simplu mod este să investești cea mai mare sumă posibilă de fonduri și să folosești echipamentul la capacitate maximă. Dar acest lucru ar duce la uzura rapidă a echipamentelor și, în consecință, la o scădere a producției. Prin urmare, eliberarea produsului trebuie planificată astfel încât să se evite efectele nedorite. Este necesar să se ia măsuri pentru a se asigura că echipamentul este completat pe măsură ce se uzează, adică pe perioade de timp. Acesta din urmă, deși duce la o scădere a volumului inițial al producției, oferă posibilitatea extinderii producției în viitor. Astfel, procesul economic de producție poate fi considerat a fi format din mai multe etape (etape), fiecare dintre acestea influențând dezvoltarea sa.
Începutul unei etape (pasului) unui proces controlat este considerat a fi momentul în care se ia o decizie (cu privire la valoarea investiției de capital, la înlocuirea echipamentelor de un anumit tip etc.). O etapă este de obicei înțeleasă ca un an de afaceri.
De obicei, pe control la fiecare pas Regatul Unit se aplică unele restricții. Se apelează controalele care îndeplinesc aceste restricții acceptabil.
Presupunând că indicatorul de performanță k a treia etapă a procesului depinde de starea inițială la acest pas k-1 și de la control la acest pas Regatul Unit, obținem funcția obiectivă a întregului proces în mai multe etape sub forma: 
.
Să formulăm acum problema de programare dinamică: „Determinați setul de controale admisibile ( u 1 , …, u n), transferând sistemul din starea inițială ε 0 în starea finală ε nși maximizarea sau minimizarea indicatorului de eficiență F».
Control care realizează maximul (minimul) funcției F numit control optim u * = (u 1* ,…, u n *).
Dacă variabilele de control Regatul Unit iau valori discrete, atunci se numește modelul DP discret. Dacă variabilele Regatul Unit se modifică continuu, apoi se numește modelul DP continuu.
În funcţie de numărul de parametri de stare sși numărul de variabile de control r diferențiați unidimensionalȘi multidimensionale Sarcini DP.
Numărul de pași dintr-o sarcină poate fi final sau fără sfârşit.
Probleme aplicate de programare dinamică
- problema de planificare a construcţiei de facilităţi.
Programare dinamică.
La modelarea structurilor de rețea, pe lângă problemele legate de existența fluxurilor în rețelele de transport, electrice, telefonice, de calculatoare și alte tipuri de rețele, apare o întreagă clasă de probleme care pot fi reduse la problema celui mai scurt drum. De exemplu, problema celei mai scurte căi este rezolvată de fiecare dată de un program de router atunci când un site este găsit după numele său pe Internet.
Problema cu calea cea mai scurtă într-o rețea direcționată este o problemă tipică de programare dinamică, prin urmare, deși programarea dinamică, precum planificarea rețelei, este asociată cu dezvoltarea proceselor în timp, a căror modelare este discutată mai detaliat în secțiunea următoare, vom va lua în considerare în această secțiune metoda de programare dinamică pe exemplu de găsire a căii celei mai scurte.
Conceptul de programare dinamică este strâns legat de procese în mai multe etape luarea deciziilor. Un proces de luare a deciziilor în mai multe etape poate fi definit ca procesul de luare a deciziilor succesive care vizează atingerea unui obiectiv dat. Procesele de luare a deciziilor în mai multe etape sunt întâlnite în mod constant într-o varietate de situații, de la repararea unei mașini într-un atelier de reparații auto până la controlul unei nave spațiale.
Programarea dinamică poate fi definită vag ca un set de proceduri matematice utilizate în analiza proceselor decizionale în mai multe etape. Fiecare proces de decizie în mai multe etape este o evoluție a următoarei probleme: găsirea celei mai scurte căi într-o rețea direcționată, aciclică.
Programarea dinamică poate fi considerată ca o teorie unificată datorită unui singur set de idei și tehnici care sunt utilizate în analiza matematică a diferitelor probleme. Aceste idei și tehnici sunt esența programării dinamice. Bellman a fost unul dintre primii care au înțeles esența principiului optimității și a început să-l aplice la multe probleme de optimizare apărute în matematică, inginerie, cercetare operațională și alte domenii.
Astfel, conceptul de programare dinamică este asociat cu un proces decizional în mai multe etape pentru atingerea unui obiectiv specific. De exemplu, transferul unei aeronave de pe o orbită pe alta este o problemă tipică de programare dinamică, cu condiția ca corectarea orbitei să fie efectuată prin aplicarea unui impuls la momente discrete și scopul să fie economisirea de combustibil.
Caracterizând programarea dinamică ca un set de proceduri matematice pentru controlul optim al unui sistem discret, în general, problema de control optim poate fi formulată după cum urmează. În momente discrete în timp t= 1, 2,..., N sistemul se află într-una din mulțimile s i de stări caracterizate de vectorul de stare x (t) . Tranziția între stări succesive se realizează folosind vectorul de control u (t) conform legii:
X (t) = g (t) (X (t) , u (t)) ; t= 1, 2,..., N
Controalele u (t) sunt selectate din setul de controale admisibile și formează o secvență de comenzi admisibile u (0) ,u (1) ,…,u (N) . Secvența controalelor admisibile pentru o stare inițială dată x (0) determină traiectoria sistemului x (0), x (1), x (2),…, x (N).
Fiecare traiectorie corespunde propriei valori a criteriului de optimitate F, sau funcției de control țintă, care este compusă din contribuții individuale la fiecare etapă de control:
Problema de control optim este de a găsi dintr-un set de secvențe de control una care atinge valoarea minimă a lui F. O astfel de secvență se numește secvență de control optimă și determină traiectoria optimă.
Programarea dinamică se bazează pe principiul optimității Bellman, care poate fi formulat după cum urmează. O strategie optimă are proprietatea că, indiferent de starea inițială și de decizia la momentul inițial, deciziile ulterioare trebuie să formuleze o strategie optimă în raport cu starea apărută după decizia inițială.
Sensul principiului optimității devine mai clar dacă avem în vedere că pentru o traiectorie optimă, fiecare secțiune dintre punctul final și orice punct intermediar este și ea o traiectorie optimă. Principiul optimității sau, altfel, metoda de programare dinamică, vă permite să găsiți strategia optimă în mai multe etape prin rezolvarea unui set de probleme de optimizare mai simple într-un singur pas.
Metoda de programare dinamică este bine ilustrată de exemplul găsirii celei mai scurte căi între nodurile extreme ale unei rețele orientate. Luați în considerare o rețea direcționată cu 12 noduri, care trebuie parcursă de la nodul de început (1) la nodul final (12) în patru pași, deplasându-se de la nod la nod cu fiecare pas.
Orez. 6.4.1. Parcurgerea unei rețele direcționate pe calea cea mai scurtă.
Numerele indicate la arce ( i,j) sunt egale cu lungimile arcurilor l ijîntre noduri iȘi j(în unități convenționale). Stările posibile ale sistemului s i în acest caz sunt asociate cu a fi în i Nodul, controlul u(t) este asociat cu alegerea direcției căii la fiecare pas de control. Patru trepte de control u (1),...,u (4) transferă secvenţial sistemul din starea iniţială s 1 în starea finală s 12 şi, astfel, formează o anumită traiectorie care trebuie găsită. Criteriul de optimitate F în acest caz este lungimea traiectoriei L, constând din lungimile arcurilor individuale:
Dacă căutarea celei mai scurte căi, adică traiectoria optimă, începe nu de la început, ci de la sfârșitul rețelei și se deplasează în direcția opusă începutului, atunci în acest caz avem un algoritm de „măturăre înapoi”. În acest caz, la implementarea algoritmului de baleiaj înapoi, mișcarea este efectuată de la starea finală s 12 la starea inițială s 1.
La începutul căutării celei mai scurte căi, este compilat un tabel de tranziție. Numărul de rânduri de tabel este egal cu numărul de pași de control, numărul de coloane este egal cu numărul de stări minus unu. Acest tabel va stoca pașii de control și valorile corespunzătoare ale criteriului de optimitate L t pentru toate stările posibile ale sistemului după fiecare pas.
Tabelul 6.4.1
| aceasta | s 1 | s 2 | s 3 | s 4 | s 5 | S 6 | s 7 | s 8 | s 9 | s 10 | s 11 |
| 12 | 12 6 | ||||||||||
| 10 | 11 10 | ||||||||||
| 5 | |||||||||||
| 1 |
Celulele umplute ale tabelului sunt împărțite în jumătate. Controlul u(t) este introdus în partea superioară a celulei umplute, adică, în acest caz, numărul nodului la care se face tranziția. Valoarea contribuției Lt la valoarea totală a criteriului de optimitate L, care a fost obținută în timpul trecerii de la nodul corespunzător acestei celule la nodul final, se introduce în partea inferioară a celulei umplute.
Completarea tabelului începe cu prima linie, unde sunt stocate informații despre ultimul pas al căii. Ultimul, în acest caz, al patrulea pas al căii este determinat în mod unic în timpul tranziției de la orice penultima stare, care poate fi oricare dintre cele trei posibile: s 9, s 10, s 11. Prin urmare, controlul optim la ultimul pas este evident. În funcție de penultima stare, contribuția la criteriul de optimitate este L 4 (9) = 12, L 4 (10) = 6 sau L 4 (11) = 7. Aceste valori de contribuție la L sunt scrise în partea de jos. a celulelor din primul rând al tabelului. 6.4.1.
Înainte de penultimul - în acest caz, al treilea - pas, setul de stări posibile ale sistemului este (s 5, s 6, s 7, s 8). Să aplicăm acum principiul lui Bellman pentru a determina traiectoria la al treilea și al patrulea pas. Constă în faptul că, indiferent de primii doi pași de control, segmentul de traiectorie din ultimii doi pași este el însuși o traiectorie optimă, adică. dă contribuţia minimă a lui L 3 la criteriul optimităţii.
Dacă starea sistemului înainte de penultimul pas este starea s 8, atunci la ultimii pași contribuția la L este determinată de relația
L 3 (s 5)=min( 
}.
Deoarece tranzițiile de la s 5 la s 9 și s 11 sunt posibile, adică:
g(s 5,9) = s 9; ; L 4 (s 9) = 12,
g(s 5,11) = s 11; ; L 4 (s 11) = 7,
L 3 (s 5) = min(6+12, 4+7) = 11 și u (3) = 11.
Aceasta înseamnă că, dacă sistemul este în starea s 5, atunci controlul optim constă în tranziția mai întâi la starea s 11, apoi la starea s 12. Lungimea arcului de la s 5 la s 12 se dovedește a fi egală cu 11 unități.
Calculând contribuția la L în mod similar pentru tranzițiile din stările s 6, s 7, s 8, obținem următoarele contribuții:
L3(s6)=min(7+12, 6+6)=12, u (3) =10;
L3(s7)=min(5+6, 3+7)=10, u (3) =11;
L3(s8)=min(10+6, 12+7)=16, u (3) =10;
Cele patru perechi de numere rezultate sunt scrise pe a doua linie a tabelului. 6.4.1.
La a doua etapă de control, contribuția la criteriul de optimitate în funcție de starea inițială este
L2 (s2) = min() = min(11+11, 14+10) = 22, u (2) = 5;
L 2 (s 3) = min( ) = min(7+11, 9+12) = 18, u (2) = 5;
L2 (s 4) = min( ) = min(2+16, 3+12, 6+10) = 15, u (2) = 6;
Cele trei perechi de numere rezultate sunt scrise în a treia linie a tabelului 6.4.1.
Starea inițială s 1 este determinată în mod unic, prin urmare, în ultimul rând al tabelului este completată singura celulă, unde valorile 3 și 24 sunt scrise deoarece:
L 1 (s 1) = min( 
) = min(5+22, 6+18, 11+15) = 24, u (1) = 3.
Acum putem determina în sfârșit secvența controlului optim în mai mulți pași. La prima etapă u (1) = 3, adică. de la nodul 1 mergem la nodul 3, la pasul al doilea u (2) = 5, i.e. mergem la nodul 5, apoi dupa controlul u (3) = 11 - la nodul 11 si, in final, la nodul 12. Obtinem in final ca cea mai scurta cale prin reteaua prezentata in Fig. 6.4.1, trece prin succesiunea stărilor s 1 →s 2 →s 5 →s 11 →s 12, iar lungimea sa este de 24 de unități convenționale.
Căutarea căii celei mai scurte poate fi efectuată și de la începutul rețelei, implementând în același timp un algoritm de baleiaj înainte, care efectuează în esență aceleași operațiuni de adăugare și comparare, dar într-o secvență ușor diferită.
Algoritmii de baleiaj înainte și înapoi, deși în esență diferiți, oferă o adăugare și o comparație pe arc. Prin urmare, ambii algoritmi au aceleași performanțe. Cu toate acestea, există o diferență importantă. Algoritmul de baleiaj înainte ia în considerare arcurile de ieșire dintre aceste noduri, cele mai scurte căi eu care sunt deja cunoscute.
Algoritmul de baleiaj înapoi ia în considerare arcurile Inbox spre acele noduri, cele mai scurte căi l j la care sunt încă necunoscute. Datorită acestei din urmă împrejurări, se preferă adesea algoritmul de măturare directă. Acest algoritm poate fi aplicat oricărei structuri a celui mai scurt set de căi.
Rezolvarea unei probleme simple cu calea cea mai scurtă ilustrează o serie de următoarele trăsături caracteristice care sunt inerente proceselor de luare a deciziilor mult mai complexe în mai multe etape:
1. Problema originală este cufundată în multe probleme de optimizare; în acest caz, fiecare nod își rezolvă propria problemă.
2. Setul de soluții la probleme de optimizare este descris de o ecuație funcțională, care este un sistem de ecuații care conectează mai multe probleme de optimizare. Într-un astfel de sistem, fiecare ecuație corespunde unui nod și de obicei conține operatori precum min, max sau minimax la dreapta semnului egal și variabile precum g i și g j pe ambele părți ale acestuia.
3. Soluția la multe probleme de optimizare poate fi găsită folosind un algoritm de baleiaj înapoi, care este echivalent cu o procedură ordonată pentru rezolvarea unei secvențe de ecuații funcționale.
Programarea dinamică este potrivită pentru rezolvarea problemelor asociate cu modelarea sistemelor de rețea care nu au o structură specială. Astfel, algoritmii de baleiaj înainte și înapoi sunt potriviți pentru efectuarea de calcule în rețele aciclice. Algoritmul de baleiaj înapoi poate fi generalizat și utilizat pentru a rezolva probleme în care există un element de aleatorie. Acest lucru nu se poate face pentru algoritmul de baleiaj înainte.
Conceptul de „stat” joacă un rol central în programarea dinamică, iar stările înseamnă următoarele. Tranziția se realizează de la o stare la o stare care conține întreaga istorie a procesului, adică starea este descrisă cu gradul de detaliu care permite calcularea (evaluarea) soluțiilor alternative curente.
Pentru modelul de rețea, stările sunt nodurile, iar arcele care ies dintr-un anumit nod reprezintă diferitele decizii care pot fi luate la acel nod (stare). Cu această interpretare, putem spune că trecerea are loc de la stat la stat, iar stările reprezintă puncte în care se iau deciziile. Declarația de mai sus înseamnă că arcele care părăsesc un nod nu au nicio legătură cu calea prin care a fost atins acest sau acel nod, adică nu depind de arcurile de intrare.
Elementele de stat sunt adesea numite variabile de stare.În modelele de programare dinamică, stările sunt uneori grupate în etape, iar tranziția se face de la o etapă la alta. De exemplu, în problema căii celei mai scurte există stări, dar nu există etape, deoarece este imposibil să grupați stările în mulțimi în așa fel încât să existe o tranziție de la o mulțime la alta.
Scufundarea într-o varietate de probleme de optimizare echivalează cu introducerea conceptului spaţiul de stat care reprezintă un ansamblu de stări. În ecuația funcțională, răspunsul optim este considerat ca o funcție a stării inițiale, iar principiul optimității stabilește relația dintre răspunsurile optime pentru diferite stări de plecare.
O multime de S sunt numite stări posibile (sau observabile). spațiu de stat,și element s din S definește un specific stat. Cu fiecare condiție s multe conectate D(s). Element d din multi D(s) se numește decizie. Se numește regula conform căreia se determină o soluție fezabilă pentru fiecare stare strategie d.
De fapt strategie d se potrivește cu fiecare stare s un element d( s) din multe D(s). Mulțimea tuturor acestor forme d spațiu de strategie D. Aceasta din urmă înseamnă că alegerea unei soluții într-o anumită stare nu constrânge alegerea în toate celelalte stări. În esență, D este un produs cartezian al mulțimilor D(s) De s.
Una dintre ideile programării dinamice este că fiecare strategie d trebuie să aibă așa-numita funcție de profit Vd(s), care poate fi obținut în funcție de stat sși utilizarea strategiei d. Conceptul de funcție de profit (sau venit) generalizează conceptul de contribuție L t la valoarea globală a criteriului de optimitate L luat în considerare la rezolvarea problemei celei mai scurte drumuri.
Expresia „folosirea strategiei d” înseamnă că ești capabil s solutia d( s); apoi se presupune că procesul a intrat în stare s„, adică statul este realizat s", în care soluția d( s"), etc. Funcția de profit are o structură destul de complexă, deoarece depinde de succesiunea stărilor și deciziilor, de recompensele care sunt asociate cu aceste stări și decizii, precum și de modul în care recompensele sunt agregate.
O stare este o descriere a istoriei unui proces cu un nivel de detaliu care permite o evaluare a soluțiilor alternative actuale. Principala proprietate a statelor este că statul este o scurtă înregistrare a istoriei procesului și gradul de detaliu ne permite să determinăm funcţia venitului local.Cu alte cuvinte, funcţia venitului local nu poate depinde decât de s, dȘi v.
Următorul capitol va analiza mai detaliat lanțurile Markov, care sunt de mare importanță pentru modelarea evoluției în timp a sistemelor de producție și tehnice. Există, de asemenea, modele de luare a deciziilor Markov în care statul s determinat de o pereche de numere (n,i) , soluția este funcția în funcție de ele k, iar funcția de venit local este determinată de o expresie ca h[(n, eu) , k, v] = R k i(n) + å j P k ij(n)v(n+ 1,j) (n
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 perioada de timp dintre tranzițiile de la stare la stare poate avea o 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.
X 4
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 analizăm 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 consecință 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-vă 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ă și, dacă da, o folosim. O matrice plină cu valori de steag poate fi utilizată ca structură de date. Dacă valoarea elementului la indicele N este egală cu valoarea steagului, atunci nu am calculat-o încă. Acest lucru creează anumite dificultăți, pentru că 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
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 la locul 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, atunci când căutăm cea mai scurtă cale, 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. 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 „în sus”, calculând secvenţial valorile din aceste argumente, în ordinea în care am notat-o. Dependența se calculează după cum urmează: LinkedList 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 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ă. Pentru o mai mare claritate, să luăm în considerare 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ă în jos. Mingea poate sări la pasul următor, cu un pas mai târziu sau cu 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.) Stabiliți numărul de posibile „ trasee” ale mingii de sus până la pământ. 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) . Primii trei pași vor fi considerați stările inițiale. 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 restului de împărțire cu 3 ne ajută să evităm o grămadă de declarații condiționate. Simplu, compact, elegant. 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ărați de câte moduri are un jucător pentru a intra în celula din dreapta jos. 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. 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); ) În concluzie, voi da o serie de probleme tipice pentru dinamica unidimensională și bidimensională; analizele sunt atașate. 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. 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. 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 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. 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. De exemplu, așa: Int Imax; //*introduceți numărul de pași de la tastatură* DP = new int; for(int i=0; i Există un calculator care efectuează trei operații: 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ț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. 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, dând jucătorul în colțul din dreapta jos.Crearea unei stive de indexuri
Bine, matematica este frumoasă. Dar sarcinile în care nu este dat totul?
Ideea de rezolvare
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);) 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
int dp = int nou; for(int i=0; i 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
int N; //Intrare de la tastatură int a = new int; a= 0; ( int min; for(int i=2; i Cel mai ieftin mod
