Dynamic programming — गतिशील प्रोग्रामिंग

गतिशील प्रोग्रामिंग (DP; अंग्रेज़ी: dynamic programming, DP) — यह जटिल अनुकूलन समस्याओं को हल करने की एक विधि है, जो मूल समस्या को क्रमिक सरल उपसमस्याओं में विभाजित करने पर आधारित है। यह विधि बहु-चरणीय निर्णय प्रक्रियाओं पर लागू होती है, जहाँ संपूर्ण समस्या का इष्टतम समाधान उसकी उपसमस्याओं के इष्टतम समाधानों से निर्मित किया जा सकता है।

यह शब्द अमेरिकी गणितज्ञ रिचर्ड बेलमैन द्वारा 1950 के दशक में प्रस्तुत किया गया था। इस संदर्भ में «प्रोग्रामिंग» शब्द का अर्थ «नियोजन» या «इष्टतम कार्य योजना बनाना» है, न कि कंप्यूटर कोड लिखना।

मुख्य गुण और प्रमेय

किसी समस्या पर गतिशील प्रोग्रामिंग की लागूता उसमें दो मूलभूत गुणों की उपस्थिति से निर्धारित होती है।

बेलमैन का इष्टतमता का सिद्धांत

इस विधि की केंद्रीय अवधारणा बेलमैन का इष्टतमता का सिद्धांत (अंग्रेज़ी: Bellman's principle of optimality) है। यह सिद्धांत कहता है: प्रारंभिक अवस्था और प्रारंभिक निर्णय चाहे जो भी हों, आगे के निर्णय पहले निर्णय के परिणामस्वरूप प्राप्त अवस्था के सापेक्ष एक इष्टतम रणनीति का निर्माण करने चाहिए।

दूसरे शब्दों में, इष्टतम पथ का कोई भी भाग स्वयं में इष्टतम होता है। यह गुण समग्र समस्या को क्रमिक सरल उपसमस्याओं में विभाजित करने और उन्हें पुनरावर्ती रूप से हल करने की अनुमति देता है।

परस्पर अतिव्यापी उपसमस्याएँ

कोई समस्या परस्पर अतिव्यापी उपसमस्याओं (अंग्रेज़ी: overlapping subproblems) का गुण रखती है, यदि उसके पुनरावर्ती समाधान में एक ही उपसमस्याएँ बार-बार उत्पन्न होती हैं। DP पहले से हल की गई उपसमस्याओं के समाधानों को संग्रहीत करके (इस तकनीक को memoization या tabulation कहा जाता है) पुनरावर्ती गणनाओं से बचाती है, जो साधारण पुनरावर्ती खोज की तुलना में दक्षता को उल्लेखनीय रूप से बढ़ाती है।

बेलमैन का समीकरण

इष्टतमता के सिद्धांत से विधि का मूल पुनरावर्ती संबंध — बेलमैन का समीकरण — निकलता है। यह वर्तमान अवस्था के «मूल्य» (इष्टतम लाभ या लागत) को आगामी अवस्थाओं के मूल्यों से जोड़ता है। योगात्मक लक्ष्य फलन वाली नियतात्मक बहु-चरणीय प्रक्रिया के लिए इसका सामान्य रूप इस प्रकार है:

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

जहाँ:

• $k$ — चरण संख्या ($m$ से 1 तक);
• $x$ — चरण $k-1$ पर प्रणाली की अवस्था;
• $y$ — चरण $k$ पर लिया जाने वाला नियंत्रित निर्णय;
• ${\phi }_k(x,y)$ — k-वें चरण पर लाभ (या लागत);
• $f_k(x,y)$ — प्रणाली की नई अवस्था निर्धारित करने वाला फलन;
• $V_k(s)$ — चरण $k$ पर अवस्था $s$ से प्रारंभ होने वाली उपसमस्या के लिए लक्ष्य फलन का इष्टतम मान।

समीकरण को क्रमिक रूप से हल किया जाता है, सामान्यतः «अंत से», अंतिम चरण से पहले चरण की ओर बढ़ते हुए।

उपयोग के उदाहरण

• ग्राफ में सबसे छोटे पथ की समस्या: इस समस्या में इष्टतम उपसंरचना का गुण है, क्योंकि सबसे छोटे पथ का कोई भी खंड स्वयं सबसे छोटा होता है। Bellman-Ford और Floyd-Warshall एल्गोरिदम इस समस्या को हल करने के लिए DP के उपयोग के क्लासिक उदाहरण हैं।
• रुकसैक की समस्या: भिन्न मूल्य और भार वाली वस्तुओं से सीमित क्षमता के रुकसैक को इष्टतम रूप से भरने की समस्या। DP वस्तुओं पर क्रमिक रूप से विचार करके और प्रत्येक चरण पर शेष क्षमता के सभी संभावित मानों के लिए अधिकतम मूल्य की गणना करके इस समस्या को हल करती है।
• संसाधन वितरण की समस्या: कुल प्रभाव को अधिकतम करने के लिए सीमित संसाधन (उदाहरण के लिए, निवेश) को कई परियोजनाओं में वितरित करना।

सीमाएँ

इस विधि की मुख्य सीमा आयामिता का अभिशाप (अंग्रेज़ी: curse of dimensionality) है — यह शब्द बेलमैन द्वारा प्रणाली की अवस्था का वर्णन करने वाले चरों की संख्या बढ़ने पर अवस्थाओं की संख्या और परिणामस्वरूप गणनात्मक जटिलता की घातीय वृद्धि को दर्शाने के लिए प्रस्तुत किया गया था। यह बहुत बड़े आयाम वाली समस्याओं के लिए सटीक DP के व्यावहारिक उपयोग को सीमित करता है।

संबंधित अवधारणाएँ

• संचालन अनुसंधान
• इष्टतम नियंत्रण का सिद्धांत
• Markov निर्णय प्रक्रिया (स्टोकास्टिक सामान्यीकरण)
• Hamilton — Jacobi — Bellman समीकरण (सतत समय के लिए समतुल्य)

टिप्पणियाँ

</references>