Datorită faptului că este una din cele mai complexe tehnici de programare, vom acorda o atenţie mărită acestei modalităţi de tratare a programelor, atenţie însoţită de un număr mare de exemple. Ele sunt în majoritate de facturi diferite, şi constituie un bun punct de pornire în formarea unei gândiri dinamice.
Datorită frecvenţei folosirii aceluiaşi termen, vom nota noţiunea de programare dinamică prin iniţialele PD.
PD este o tehnică de programare de nivel înalt în sens că necesită o îmbinare între intuiţie şi rigurozitate matematică. Expunem, într-un mod intuitiv, ideile acestei tehnici.
În general, termenul de "principiul optimalităţii" semnifică următoarele: atunci când vrem să obţinem o situaţie favorabilă dintr-un anumit punct de vedere, este bine ca ea să rezulte tot din spaţii favorabile. Un exemplu intuitiv este acel al distanţelor:
Într-un cartier sînt mai multe case, pe care le vom nota cu litere: A,….,Z. Dacă există un drum minim de la A la Z şi acest drum trece de exemplu prin D, atunci porţiunile din acest drum situate între A şi D, respectiv D şi Z sunt minime.
Pentru a justifica aceasta, să presupunem prin absurd că drumul A-α-D nu ar fi minim. Înseamnă că există alt traseu A-β-D mai scurt decât acesta; dacă luăm atunci drumul A- β - D - Z, el va fi evident mai scurt decât drumul A - α - D - Z, care este considerat ca fiind drum minim, contradicţie.
Deci, dacă traseul A-Z este optim, atunci orice subtraseu al său este optim.
Principiul optimalităţii are 3 variante:
s1, s2, …, si să fie optim.
De precizat că reciproca nu este adevărată totdeauna: din îmbinarea a două optime nu rezultă neapărat un optim; doar dacă avem un optim, putem fi siguri că el este compus din două optime. Deci trebuie să facem toate combinaţiile di soluţii parţiale optime pentru a găsi acea pereche de optime care alăturate conduc la un optim. Am folosit mai sus termenul de optim, dar nu am precizat în ce sens. Criteriul ales nu este valabil pentru orice problemă, ci va fi un criteriu specific problemei pe care o tratăm. În exemplu anterior criteriul era distanţa dintre două puncte (de exemplu A şi Z). Deci noţiunea abstractă cu care se lucra în problemă era ceia de distanţă, iar optim înseamnă lungimea ei, măsurată în anumite unităţi.
Dacă - spre exemplu - vom aborda o problemă care necesită să evaluăm ce preţ trebuie plătit pentru a duce un sistem dintr-o stare în alta, noţiunea cu care se va lucra este banul, iar optim va însemna cît mai puţini. După cum se poate intui, întotdeauna se va găsi o cuantificare a realităţii astfel în cît optimalitatea să se refere la numere.
Rezolvările folosind PD sunt în general bazate pe realizarea unei optimizări, de aflare a unui şir optim de transformări conform criteriului care ne intersectează.
Deficienţa acestei metode este că depinde de experienţa personală şi de capacitatea de a intui. Şi încă un lucru: să nu vă speriaţi; de obicei programele de PD sunt extrem de scurte şi neaşteptat de simple.
Programare dinamica
Niciun comentariu:
Trimiteți un comentariu