Dinamikong programming

Dinamikong Programming (DP; Ingles: dynamic programming, DP) — ito ay isang paraan ng paglutas ng mga kumplikadong problema sa optimisasyon, batay sa paghahati ng orihinal na problema sa isang pagkakasunod-sunod ng mas simpleng mga subproblema. Ang paraan ay inilalapat sa mga multi-hakbang na proseso ng paggawa ng desisyon, kung saan ang pinakamainam na solusyon sa buong problema ay maaaring itayo mula sa mga pinakamainam na solusyon ng mga subproblema nito.

Ang terminolohiya ay ipinakilala ng Amerikanong matematisyano si Richard Bellman noong dekada 1950. Sa kontekstong ito, ang salitang "programming" ay ginagamit sa kahulugang "pagpaplano" o "paggawa ng pinakamainam na plano ng aksyon", at hindi pagsulat ng computer code.

Mga Pangunahing Katangian at Teorema

Ang naaangkop na paggamit ng dinamikong programming sa isang problema ay natutukoy sa pamamagitan ng pagkakaroon nito ng dalawang pundamental na katangian.

Prinsipyo ng Optimalidad ni Bellman

Ang sentral na konsepto ng paraan ay ang prinsipyo ng optimalidad ni Bellman (Ingles: Bellman's principle of optimality). Sinasabi nito: anuman ang paunang estado at paunang desisyon, ang mga kasunod na desisyon ay dapat bumuo ng pinakamainam na estratehiya kaugnay ng estadong nakuha bilang resulta ng unang desisyon.

Sa madaling salita, anumang bahagi ng pinakamainam na landas ay sa sarili nito ay pinakamainam. Ang katangiang ito ay nagpapahintulot na hatiin ang pangkalahatang problema sa isang pagkakasunod-sunod ng mas simpleng mga subproblema at resolbahin ang mga ito nang rekursibo.

Nagsasapatong mga Subproblema - Overlapping Subproblems

Ang isang problema ay nagtataglay ng katangian ng nagsasapatong mga subproblema (Ingles: overlapping subproblems) kung sa rekursibong paglutas nito, ang parehong mga subproblema ay paulit-ulit na lumalabas. Pinapayagan ng DP na maiwasan ang paulit-ulit na pagkalkula sa pamamagitan ng pag-iimbak ng mga solusyon ng mga subproblemang natagpuan na (ang pamamaraang ito ay tinatawag na memoization o tabulation), na makabuluhang nagpapataas ng kahusayan kumpara sa simpleng rekursibong paghahanap.

Ekwasyon ni Bellman

Mula sa prinsipyo ng optimalidad ay lumalabas ang pangunahing rekurensyang relasyon ng paraan — ang ekwasyon ni Bellman. Iniuugnay nito ang "halaga" (pinakamainam na kita o gastos) ng kasalukuyang estado sa mga halaga ng mga kasunod na estado. Sa pangkalahatang anyo para sa isang determinado na multi-hakbang na proseso na may additive na objective function, ito ay may anyo:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

kung saan:

• $k$ — numero ng hakbang (mula $m$ hanggang 1);
• $x$ — estado ng sistema sa hakbang $k-1$;
• $y$ — kontroladong desisyon na ginagawa sa hakbang $k$;
• ${\phi }_k(x,y)$ — kita (o gastos) sa ika-k na hakbang;
• $f_k(x,y)$ — function na nagtatakda ng bagong estado ng sistema;
• $V_k(s)$ — pinakamainam na halaga ng objective function para sa subproblemang nagsisimula sa hakbang $k$ sa estado $s$.

Ang ekwasyon ay nireresolba nang sunud-sunod, karaniwan ay "mula sa dulo", na gumagalaw mula sa huling hakbang patungo sa una.

Mga Halimbawa ng Paggamit

• Problema sa pinakamaikling landas sa graph: Ang problemang ito ay nagtataglay ng katangian ng pinakamainam na substructure, dahil ang anumang bahagi ng pinakamaikling landas ay sa sarili nito ay pinakamaikli. Ang mga algorithm nina Bellman-Ford at Floyd-Warshall ay mga klasikong halimbawa ng paggamit ng DP upang resolbahin ang problemang ito.
• Problema sa mochila (knapsack): Problema sa pinakamainam na pagpuno ng mochila na may limitadong kapasidad gamit ang mga bagay na may iba't ibang halaga at timbang. Pinapayagan ng DP na resolbahin ang problemang ito sa pamamagitan ng sunud-sunod na pagsasaalang-alang ng mga bagay at pagkalkula sa bawat hakbang ng maximum na halaga para sa lahat ng posibleng natitirang kapasidad.
• Problema sa pamamahagi ng likas-kulay: Pamamahagi ng limitadong likas-kulay (halimbawa, mga pamumuhunan) sa pagitan ng ilang mga proyekto upang mapakinabangan ang kabuuang epekto.

Mga Limitasyon

Ang pangunahing limitasyon ng paraan ay ang sumpa ng dimensyon (Ingles: curse of dimensionality) — isang termino na ipinakilala ni Bellman upang tukuyin ang exponensyal na paglaki ng bilang ng mga estado at, bilang resulta, ang computational complexity, kapag nadaragdagan ang bilang ng mga variable na naglalarawan sa estado ng sistema. Nililimitahan nito ang praktikal na paggamit ng tumpak na DP para sa mga problema ng napakalaking dimensyon.

Mga Kaugnay na Konsepto

• Pananaliksik sa operasyon
• Teorya ng pinakamainam na kontrol
• Proseso ng desisyon ni Markov (stochastic na pangkalahatang anyo)
• Ekwasyon ni Hamilton–Jacobi–Bellman (katumbas para sa tuloy-tuloy na oras)

Mga Tala

</references>