गतिक प्रोग्रामिंग

Not to be confused with गतिक प्रोग्रामिंग भाषा or गतिक समस्या.

चित्रा 1. इष्टतम सबस्ट्रक्चर का उपयोग करके ग्राफ में सबसे छोटा रास्ता ढूँढना, सीधी रेखा किनारे को इंगित करती है, लहराती रेखा उन दो शीर्षों के बीच सबसे छोटा रास्ता दिखाती है जो इसे जोड़ता है (अन्य रास्तों के बीच, दिखाया नहीं गया है, वही दो कोने साझा करता है), बोल्ड लाइन प्रारंभ से लक्ष्य तक का सबसे छोटा रास्ता है।

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

इस प्रकार दोनों संदर्भों में इसके द्वारा जटिल समस्या को पुनरावर्ती विधियों से सरल उप-समस्याओं में तोड़कर सरल बनाने के लिए संदर्भित किया जाता है। जबकि कुछ निर्णय समस्याओं को इस प्रकार अलग नहीं किये जाते हैं, ऐसे निर्णय जो समय में कई बिंदुओं का प्रसार करते हैं, अधिकांशतः पुनरावर्ती रूप से अलग हो जाते हैं। इस प्रकार कंप्यूटर विज्ञान में, यदि किसी समस्या को उप-समस्याओं में तोड़कर और फिर पुनरावर्ती रूप से उप-समस्याओं का इष्टतम समाधान ढूंढकर हल किया जाता है, तो इसे 'इष्टतम उप-संरचना' कहा जाता है।

यदि उप-समस्याओं को पुनरावर्ती रूप से बड़ी समस्याओं के अंदर संयोजिक किया जा सकता है, जिससे कि गतिक प्रोग्रामिंग विधियों को उपयोग किया जा सके, तो बड़ी समस्या के मान और उप-समस्याओं के मानों के बीच संबंध होता है। अनुकूलन साहित्य में इस संबंध को बेलमैन समीकरण कहा जाता है।

अवलोकन

गणितीय अनुकूलन

गणितीय अनुकूलन के संदर्भ में, गतिक प्रोग्रामिंग सामान्यतः समय के साथ निर्णय चरणों के अनुक्रम में इसे तोड़कर निर्णय को सरल बनाने के लिए संदर्भित करता है। यह मूल्य कार्यों 'v₁' के अनुक्रम को परिभाषित करके किया जाता है, i₂, ..., i_n y को 1 से n तक के समय में प्रणाली के 'चर अवस्था' का प्रतिनिधित्व करने वाले तर्क के रूप में निर्दिष्ट किया जा सकता हैं। v_n (y) की परिभाषा के अंतिम समय पर स्थिति y में प्राप्त मान को निर्गत करना सरल होता हैं है। इस प्रकार v_i मान को पहले के समय में i = n −1, n − 2, ..., 2, 1 को बेलमैन समीकरण नामक पुनरावर्तन संबंध का उपयोग करके पीछे की ओर कार्य करके पाया जाता है। i = 2, ..., n, v_i−1 के लिए किसी भी अवस्था में y की गणना V_i द्वारा की जाती है इस प्रकार समय i − 1 और फ़ंक्शन V_i पर किसी निर्णय से होने वाले लाभ के साधारण फ़ंक्शन (सामान्यतः योग) को अधिकतम मान प्राप्त करके यदि यह निर्णय किया जाता है तो इस प्रणाली की नई स्थिति में इसे उपयोग किया जा सकता हैं। चूंकि v_i को पहले से ही आवश्यक स्थितियों के लिए गणना की जा चुकी है, उपरोक्त ऑपरेशन के उत्पाद के लिए v_i−1 इन स्थितियों के लिए सहायक हैं। इस प्रकार अंत में प्राप्त v₁ प्रणाली की प्रारंभिक अवस्था में इष्टतम समाधान का मान प्राप्त करता है। इसलिए पहले से की गई गणनाओं को वापस ट्रैक करके, निर्णय चर के इष्टतम मान को क्रमशः पुनर्प्राप्त किया जाता है।

नियंत्रण सिद्धांत

नियंत्रण सिद्धांत में, स्वीकार्य नियंत्रण खोजने के लिए सामान्य समस्या $\mathbf {u} ^{\ast }$है , जो ${\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)$ प्रणाली का कारण बनता है, इस प्रकार स्वीकार्य किए जाने वाले प्रक्षेपवक्र का पालन करने के लिए $\mathbf {x} ^{\ast }$ को निरंतर समय अंतराल पर $t_{0}\leq t\leq t_{1}$ जो हानि फंक्शन को कम करता रहता हैं

$J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t$

इस समस्या का समाधान इष्टतम नियंत्रण नियम या नीति के लिए सहयोगी होता है, $\mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)$, समीकरण के द्वारा इष्टतम प्रक्षेपवक्र $\mathbf {x} ^{\ast }$ को उत्पन्न किया जाता है और $J^{\ast }$ कॉस्ट-टू-गो फ़ंक्शन के उत्तरार्द्ध को गतिक प्रोग्रामिंग के मौलिक समीकरण का पालन करके उक्त समीकरण द्वारा प्राप्त किया जाता हैं:

$-J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}$

हैमिल्टन-जैकोबी-बेलमैन समीकरण के रूप में जाना जाने वाला आंशिक अंतर समीकरण, जिसमें $J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}$ और $J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}$. पाता है कि कम करना $\mathbf {u}$ के अनुसार $t$, $\mathbf {x}$, और अज्ञात फ़ंक्शन $J_{x}^{\ast }$ और फिर परिणाम को हैमिल्टन-जैकोबी-बेलमैन समीकरण में स्थानापन्न करता है जिससे कि आंशिक अंतर समीकरण को सीमा शर्त के साथ $J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)$ से प्राप्त मान को उपयोग किया जा सके, व्यवहारिक रूप से, सही अनुकूलन संबंध के लिए कुछ असतत सन्निकटन के लिए सामान्यतः संख्यात्मक आंशिक अंतर समीकरणों की आवश्यकता होती है।

वैकल्पिक रूप से, निरंतर प्रक्रिया को असतत प्रणाली द्वारा अनुमानित किया जाता हैं, जो हैमिल्टन-जैकोबी-बेलमैन समीकरण के अनुरूप निम्नलिखित पुनरावृत्ति संबंध की ओर जाता है:

$J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}$

इस प्रकार $k$-वाँ चरण $n$ समान दूरी पर असतत समय अंतराल के लिए ${\hat {f}}$ और ${\hat {\mathbf {g} }}$ असतत सन्निकटन को $f$ और $\mathbf {g}$ द्वारा निरूपित करता हैं, इस कार्यात्मक समीकरण को बेलमैन समीकरण के रूप में जाना जाता है, जिसे अनुकूलन समीकरण के असतत सन्निकटन के सही समाधान के लिए हल किया जाता है।

अर्थशास्त्र से उदाहरण: रैमसे की इष्टतम बचत की समस्या

See also: रैमसे-कैस-कूपमन्स मॉडल

अर्थशास्त्र में, उद्देश्य सामान्यतः कुछ गतिक सामाजिक कल्याण कार्य को अधिकतम (न्यूनतम करने के अतिरिक्त) करना है। रैमसे की समस्या में, यह फलन उपभोग की मात्रा को उपयोगिता के स्तरों से संबंधित करता है। ढीले ढंग से बोलते हुए, इस प्रकार समसामयिक खपत और भविष्य की खपत (उत्पादन में उपयोग की जाने वाली भौतिक पूंजी में निवेश के माध्यम से) के बीच व्यापार-बंद का सामना करता है, जिसे अंतरकालिक मान के रूप में जाना जाता है। भविष्य की खपत को स्थिर दर $\beta \in (0,1)$ पर छूट दी जाती है, इस प्रकार पूंजी के संक्रमण समीकरण के लिए असतत सन्निकटन द्वारा दिया गया है

$k_{t+1}={\hat {g}}\left(k_{t},c_{t}\right)=f(k_{t})-c_{t}$

जहाँ $c$ खपत है, $k$ पूंजी है, और $f$ इनडा स्थितियों को संतुष्ट करने वाला उत्पादन फलन है। प्रारंभिक पूंजी के स्टॉक $k_{0}>0$ को इस प्रकार अवलेखित किया जा सकता है।

$c_{t}$ की अवधि में खपत के लिए t, और उपभोक्ता से उपयोगिता $u(c_{t})=\ln(c_{t})$ प्राप्त होती है, और यह जब तक उपभोक्ता रहता है तब तक प्राप्त होती हैं। मान लें कि उपभोक्ता अधीर है, इसलिए वह भविष्य की उपयोगिता को कारक b द्वारा छूट देता है, प्रत्येक अवधि पर जहां $0<b<1$. को $k_{t}$ द्वारा प्रकट करते हैं, इसके लिए उपयुक्त अवधि में पूंजी (अर्थशास्त्र) को t से प्रकट करते हैं, यहाँ मान लें कि प्रारंभिक पूंजी दी गई राशि का मान $k_{0}>0$ है , तथा यहाँ पर मान लीजिए कि इस अवधि की पूंजी और खपत अगली अवधि की पूंजी $k_{t+1}=Ak_{t}^{a}-c_{t}$ के रूप में निर्धारित की जाती है , जहाँ A धनात्मक स्थिरांक $0<a<1$ है,और मान लें कि पूंजी ऋणात्मक नहीं हो सकती तब इस स्थिति में उपभोक्ता की निर्णय समस्या को इस प्रकार लिखा जा सकता है:

$\max \sum _{t=0}^{T}b^{t}\ln(c_{t})$ का विषय है $k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0$ सभी के लिए $t=0,1,2,\ldots ,T$

इस तरह से लिखा गया, समस्या जटिल दिखती है, क्योंकि इसमें सभी विकल्प चरों को हल करने के लिए $c_{0},c_{1},c_{2},\ldots ,c_{T}$ उक्त समीकरण दिया गया है, ($k_{0}$ विकल्प चर नहीं है - उपभोक्ता की प्रारंभिक पूंजी दी गई है।)

इस समस्या को हल करने के लिए गतिक प्रोग्रामिंग दृष्टिकोण में इसे छोटे निर्णयों के अनुक्रम में तोड़ना सम्मलित है। ऐसा करने के लिए, हम मूल्य कार्यों के अनुक्रम को परिभाषित करते हैं, $V_{t}(k)$ के लिए $t=0,1,2,\ldots ,T,T+1$ जो पूंजी की किसी भी राशि के होने के मूल्य का प्रतिनिधित्व करते हैं, तथा k के लिए समय t के बाद पूंजी होने से $V_{T+1}(k)=0$ (धारणा के अनुसार) कोई उपयोगिता नहीं है।

किसी भी समय पूंजी की किसी भी मात्रा के मूल्य की गणना बेलमैन समीकरण का उपयोग करके पीछे की ओर प्रेरण द्वारा की जा सकती है। इस समस्या में प्रत्येक के लिए $t=0,1,2,\ldots ,T$, बेलमैन समीकरण है

$V_{t}(k_{t})\,=\,\max \left(\ln(c_{t})+bV_{t+1}(k_{t+1})\right)$ का विषय है $k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0$

यह समस्या हमारे द्वारा पहले लिखी गई समस्या से कहीं अधिक सरल है, क्योंकि इसमें केवल दो निर्णय चर सम्मलित हैं, $c_{t}$ और $k_{t+1}$. सहज रूप से, जन्म के समय अपनी संपूर्ण जीवन भर की योजना चुनने के अतिरिक्त, उपभोक्ता बार में कदम उठा सकता है। समय t पर उनकी वर्तमान $k_{t}$ का मान दिया जाता है, और उसे केवल वर्तमान खपत $c_{t}$ और बचत $k_{t+1}$ को चुनने की आवश्यकता होती है।

वास्तव में इस समस्या को हल करने के लिए हम पीछे की ओर कार्य करते हैं। सरलता के लिए, पूँजी के वर्तमान स्तर को k. $V_{T+1}(k)$ रूप में निरूपित किया जाता है , जो पहले से ही ज्ञात होता है, इसलिए बेलमैन समीकरण का उपयोग करके हम $V_{T}(k)$ की गणना कर सकते हैं, और $V_{0}(k)$ के लिए इतने पर जब तक हम नहीं पहुंचते, जो पूरे जीवनकाल के लिए प्रारंभिक निर्णय समस्या का मान है। दूसरे शब्दों में हम $V_{T-j+1}(k)$ का मान प्राप्त कर लेते हैं, इस प्रकार हम $V_{T-j}(k)$ की गणना कर सकते हैं, जो कि अधिकतम है $\ln(c_{T-j})+bV_{T-j+1}(Ak^{a}-c_{T-j})$, जहाँ $c_{T-j}$ चर है और $Ak^{a}-c_{T-j}\geq 0$ के द्वारा कार्य करता हैं, यह दिखाया जा सकता है कि $t=T-j$ का मान समय पर निर्भर करता है।

$V_{T-j}(k)\,=\,a\sum _{i=0}^{j}a^{i}b^{i}\ln k+v_{T-j}$

जहां प्रत्येक $v_{T-j}$ का मान स्थिर रहता है, और समय पर उपभोग करने के लिए इष्टतम मान $t=T-j$ है

$c_{T-j}(k)\,=\,{\frac {1}{\sum _{i=0}^{j}a^{i}b^{i}}}Ak^{a}$

जिसे सरल बनाया जा सकता है

${\begin{aligned}c_{T}(k)&=Ak^{a}\\c_{T-1}(k)&={\frac {Ak^{a}}{1+ab}}\\c_{T-2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}}}\\&\dots \\c_{2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}}}\\c_{1}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}}\\c_{0}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^{T}b^{T}}}\end{aligned}}$

हम देखते हैं कि वर्तमान धन के बड़े हिस्से का उपभोग करना इष्टतम है क्योंकि वृद्ध हो जाता है, अंत में शेष सभी धन का उपभोग T समय की जीवन की अंतिम अवधि में होता है।

कंप्यूटर प्रोग्रामिंग

गतिक प्रोग्रामिंग को लागू करने के लिए समस्याओं में दो प्रमुख विशेषताएँ होनी चाहिए: इष्टतम सबस्ट्रक्चर और अतिव्यापी उपसमस्या याओवरलैपिंग सब-प्रोब्लम्स। यदि किसी समस्या को गैर-अतिव्यापी उप-समस्याओं के इष्टतम समाधानों के संयोजन से हल किया जाता है, तो रणनीति को विभाजित किया जाता हैं जिसे एल्गोरिथम कहा जाता है। यही कारण है कि मर्ज़ सॉर्ट और जल्दी से सुलझाएं को गतिक प्रोग्रामिंग समस्याओं के रूप में वर्गीकृत नहीं किया गया है।

इष्टतम उपसंरचना का अर्थ है कि किसी दी गई अनुकूलन समस्या का समाधान उसकी उप-समस्याओं के इष्टतम समाधानों के संयोजन से प्राप्त किया जाता है। इस तरह के इष्टतम अवसंरचनाओं को सामान्यतः पुनरावर्तन के माध्यम से वर्णित किया जाता है। उदाहरण के लिए, ग्राफ g = (v, e) दिया गया है, सबसे छोटा पथ पी शीर्ष यू से शीर्ष वी तक इष्टतम उपसंरचना प्रदर्शित करता है: इस सबसे छोटे पथ पी पर किसी भी मध्यवर्ती शीर्ष डब्ल्यू को लें। यदि p वास्तव में सबसे छोटा पथ है, तो इसे उप-पथ p₁ में विभाजित किया जा सकता है, u से w और p₂w से v तक ऐसे हैं कि, बदले में, ये वास्तव में संबंधित शीर्षों के बीच सबसे छोटा रास्ता हैं (एल्गोरिदम के परिचय में वर्णित सरल कट-एंड-पेस्ट तर्क द्वारा)। इसलिए, पुनरावर्ती विधियाँ से सबसे छोटा रास्ता खोजने के लिए आसानी से समाधान तैयार करता है, जो कि बेलमैन-फोर्ड एल्गोरिथम या फ्लोयड-वॉर्शल एल्गोरिथम करता है।

अतिव्यापी उप-समस्याओं का अर्थ है कि उप-समस्याओं का स्थान छोटा होना चाहिए, अर्थात, समस्या को हल करने वाले किसी भी पुनरावर्ती एल्गोरिथ्म को नई उप-समस्याओं को उत्पन्न करने के अतिरिक्त समान उप-समस्याओं को बार-बार हल करना चाहिए। उदाहरण के लिए, फाइबोनैचि श्रृंखला उत्पन्न करने के लिए पुनरावर्ती सूत्रीकरण पर विचार करें: F_i = F_i−1 + F_i−2, बेस केस F के साथ F₁= F₂= 1 तथा फिर F₄₃ = F₄₂+ F₄₁, और F₄₂ = F₄₁+ F₄₀ अब F₄₁ दोनों F₄₃ साथ ही F₄₂ की पुनरावर्ती इसके उप मानों के लिए हल करके प्राप्त किया जाता है, यदि उप-समस्याओं की कुल संख्या वास्तव में छोटी है (उनमें से केवल 43), यदि हम इस तरह के सरल पुनरावर्ती समाधान को अपनाते हैं, तो हम उन्हीं समस्याओं को बार-बार हल करते हैं। गतिक प्रोग्रामिंग इस तथ्य को ध्यान में रखता है और प्रत्येक उप-समस्या को केवल बार हल करता है।

चित्रा 2. फिबोनैकी अनुक्रम के लिए उप-समस्या ग्राफ। तथ्य यह है कि यह वृक्ष संरचना नहीं है, अतिव्यापी उप-समस्याओं को इंगित करता है।

इसे दो विधियों से प्राप्त किया जा सकता है:

• टॉप-डाउन और बॉटम-अप डिज़ाइन या टॉप-डाउन दृष्टिकोण: यह किसी भी समस्या के पुनरावर्ती सूत्रीकरण का प्रत्यक्ष पतन है। यदि किसी समस्या का समाधान उसकी उप-समस्याओं के समाधान का उपयोग करके पुनरावर्ती रूप से तैयार किया जाता है, और यदि उसकी उप-समस्याएं अतिव्याप्त हैं, तो सूची में उप-समस्याओं के समाधानों को आसानी से याद या संग्रहीत किया जाता है। जब भी हम नई उप-समस्या को हल करने का प्रयास करते हैं, तो हम पहले यह देखने के लिए सूची की जांच करते हैं कि क्या यह पहले से ही हल हो गई है। यदि कोई समाधान अंकित किया गया है, तो हम इसका सीधे उपयोग कर सकते हैं, अन्यथा हम उप-समस्या को हल करते हैं और सूची में उसका समाधान जोड़ते हैं।
• टॉप-डाउन और बॉटम-अप डिज़ाइन या बॉटम-अप दृष्टिकोण: बार जब हम किसी समस्या के समाधान को उसकी उप-समस्याओं के संदर्भ में पुनरावर्ती रूप से तैयार कर लेते हैं, तो हम समस्या को नीचे-ऊपर फैशन में सुधारने का प्रयास करते हैं: उप को हल करने का प्रयास करें -समस्याएं पहले और उनके समाधान का निर्माण करने के लिए उपयोग करें और बड़ी उप-समस्याओं के समाधान पर पहुंचता हैं। यह भी सामान्यतः छोटी उप-समस्याओं के समाधान का उपयोग करके बड़ी और बड़ी उप-समस्याओं के समाधान उत्पन्न करके सारणीबद्ध रूप में किया जाता है। उदाहरण के लिए, यदि हम पहले से ही F₄₁ और F₄₀ का मान जानते हैं, हम सीधे F₄₂ के मान की गणना करते हैं।

कॉल-बाय-नाम मूल्यांकन (इस तंत्र को कॉल-बाय-ज़रूरत के रूप में जाना जाता है) को गति देने के लिए, कुछ प्रोग्रामिंग लैंग्वेज स्वचालित रूप से तर्कों के विशेष सेट के साथ फ़ंक्शन कॉल के परिणाम को याद कर सकती हैं। कुछ भाषाएँ इसे पोर्टेबल रूप से संभव बनाती हैं, जैसे स्कीम (प्रोग्रामिंग लैंग्वेज), सामान्य लिस्प, पर्ल या डी (प्रोग्रामिंग भाषा) इत्यादि। कुछ भाषाओं में स्वचालित संस्मरण होता है जिसके लिए बिल्ट इन, जैसे कि टेबल्ड प्रोलॉग और j (प्रोग्रामिंग लैंग्वेज), जो m के लिए विशेषण करने के साथ संस्मरण का समर्थन करता है। किसी भी स्थिति में, यह केवल संदर्भित पारदर्शी कार्य करने के लिए ही संभव है। शब्द-पुनर्लेखन आधारित भाषाओं जैसे वोल्फ्राम भाषा के भीतर मेमोइज़ेशन को सरलता से सुलभ डिज़ाइन पैटर्न के रूप में भी देखा जाता है।

जैव सूचना विज्ञान

अनुक्रम संरेखण, प्रोटीन तह, आरएनए संरचना भविष्यवाणी और प्रोटीन-डीएनए बंधन जैसे कार्यों के लिए जैव सूचना विज्ञान में गतिक प्रोग्रामिंग का व्यापक रूप से उपयोग किया जाता है। प्रोटीन-डीएनए बाइंडिंग के लिए पहला गतिक प्रोग्रामिंग एल्गोरिदम 1970 के दशक में संयुक्त राज्य अमेरिका में चार्ल्स डेलीसी द्वारा तथा यूएसएसआर में जॉर्जी गुरस्की और अलेक्जेंडर ज़सेदातेलेव द्वारा स्वतंत्र रूप से विकसित किया गया था। हाल ही में ये एल्गोरिदम जैव सूचना विज्ञान और कम्प्यूटेशनल बायोलॉजी विज्ञान विशेष रूप से न्यूक्लियोसोम पोजिशनिंग और प्रतिलेखन कारक बाइंडिंग के अध्ययन में बहुत लोकप्रिय हो गए हैं।

उदाहरण: कंप्यूटर एल्गोरिदम

सबसे छोटी पथ समस्या के लिए दिज्क्स्ट्रा की एल्गोरिथ्म

गतिक प्रोग्रामिंग दृष्टिकोण से, सबसे छोटी पथ समस्या के लिए दिज्क्स्ट्रा का एल्गोरिथ्म क्रमिक सन्निकटन योजना है जो रीचिंग विधि द्वारा सबसे छोटी पथ समस्या के लिए गतिक प्रोग्रामिंग कार्यात्मक समीकरण को हल करती है।

वास्तव में, एल्गोरिथम के पीछे के तर्क की डिजस्ट्रा की व्याख्या, अर्थात्

Problem 2. Find the path of minimum total length between two given nodes $P$ and $Q$.

We use the fact that, if $R$ is a node on the minimal path from $P$ to $Q$, knowledge of the latter implies the knowledge of the minimal path from $P$ to $R$.

सबसे छोटी पथ समस्या के संदर्भ में रिचर्ड बेलमैन या बेलमैन के अनुकूलता के प्रसिद्ध सिद्धांत की व्याख्या है।

फाइबोनैचि अनुक्रम

फाइबोनैचि अनुक्रम के nवें सदस्य की गणना में गतिशील प्रोग्रामिंग का उपयोग करने से इसके प्रदर्शन में अधिक सुधार होता है। यहाँ गणितीय परिभाषा पर सीधे आधारित कार्यान्वयन है:

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

ध्यान दें कि यदि हम fib(5) कोकॉल करते हैं, तब हम कॉल ट्री बनाते हैं जो फ़ंक्शन को ही मान पर कई अलग-अलग बार कॉल करता है:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

विशेष रूप से, fib(2) स्क्रैच से तीन बार गणना की गई थी। बड़े उदाहरणों में, के कई और मान fib, या उप-समस्याओं की पुनर्गणना की जाती है, जिससे चरघातांकी समय एल्गोरिद्म तैयार होता है।

अब, मान लीजिए कि हमारे पास साधारण साहचर्य आव्यहु वस्तु है, m, जो प्रत्येक मान को मैप करता है fib इसके परिणाम के लिए पहले से ही इसकी गणना की जा चुकी है, और हम इसका उपयोग करने और इसे अपडेट करने के लिए अपने कार्य को संशोधित करते हैं। परिणामी फ़ंक्शन को घातीय समय के अतिरिक्त केवल बिग-ओ नोटेशन (एन) समय की आवश्यकता होती है (किन्तु बिग-ओ नोटेशन (एन) स्पेस की आवश्यकता होती है):

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

मूल्यों को सहेजने की यह विधि जिसकी गणना पहले ही की जा चुकी है, यह प्रक्रिया मेमोइज़ेशन कहलाती है, यह टॉप-डाउन दृष्टिकोण है, क्योंकि हम पहले समस्या को उप-समस्याओं में तोड़ते हैं और फिर मूल्यों की गणना और संग्रह करते हैं।

बॉटम-अप दृष्टिकोण में, हम के छोटे मानों की गणना fib करते हैं इसके बाद पहले उनसे बड़े मान बनाएँ जाते हैं। यह विधि O(n) समय का भी उपयोग करती है क्योंकि इसमें लूप होता है जो n - 1 बार दोहराता है, किन्तु यह केवल स्थिर (O(1)) स्थान लेता है, शीर्ष-डाउन दृष्टिकोण के विपरीत जिसके लिए O(n) स्थान की आवश्यकता होती है।

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
         return currentFib

दोनों उदाहरणों में, हम केवल गणना करते हैं fib(2) बार, और फिर दोनों की गणना करने के लिए fib(4) और fib(3) इसका उपयोग करते हैं, इसकी गणना करने के अतिरिक्त हर बार उनमें से किसी का मूल्यांकन किया जाता है।

संतुलित 0–1 आव्यहु

किसी की स्थिति के लिए, या तो शून्य या मान निर्दिष्ट करने की समस्या पर विचार करें n × n आव्यहु, के साथ n यहां तक ​​कि, जिससे कि प्रत्येक पंक्ति और प्रत्येक कॉलम n / 2 शून्य और n / 2 में बिल्कुल सम्मलित होती हैं । हम पूछते हैं कि दिए गए $n$ के लिए कितने अलग-अलग फंक्शन होते हैं, उदाहरण के लिए, जब n = 4, पांच संभावित समाधान हैं

${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.$

कम से कम तीन संभावित दृष्टिकोण हैं: -बल खोज, बैक ट्रैकिंग और गतिक प्रोग्रामिंग करता हैं।

इस बल में शून्य और के सभी असाइनमेंट की जाँच करना और संतुलित पंक्तियों और स्तंभों की गणना करना सम्मलित है (n / 2 शून्य और n / 2 वाले)। जैसे $2^{n^{2}}$है जो संभावित कार्य और ${\tbinom {n}{n/2}}^{n}$ असाइनमेंट करता हैं, यह रणनीति व्यावहारिक नहीं है जब तक $n=6$ के बराबर ना हो जाए।

इस समस्या के लिए बैकट्रैकिंग में आव्यहु तत्वों के कुछ क्रम को चुनना और पुनरावर्ती रूप से या शून्य को रखना सम्मलित है, जबकि यह जांचते हुए कि प्रत्येक पंक्ति और कॉलम में तत्वों की संख्या जिन्हें निर्दिष्ट नहीं किया गया है, साथ ही या शून्य की संख्या n / 2 दोनों कम से कम हैं, इस बल की तुलना में अधिक परिष्कृत होने के अतिरिक्त, यह दृष्टिकोण हर समाधान पर बार जाएगा, जिससे यह अव्यवहारिक हो जाएगा n छह से बड़ा, चूंकि समाधान की संख्या पहले से ही 116,963,796,250 है जिसके लिए n= 8 के मान पर रहता हैं।

गतिक प्रोग्रामिंग उन सभी का दौरा किए बिना समाधानों की संख्या की गणना करना संभव बनाता है। पहली पंक्ति के लिए बैकट्रैकिंग मानों की कल्पना करें - प्रत्येक पहली पंक्ति मान के लिए प्राप्त समाधानों की सटीक गणना करने में सक्षम होने के लिए हमें शेष पंक्तियों के बारे में क्या जानकारी चाहिए? k × n होने पर हमें विचार विमर्श करना है, इस प्रकार बोर्ड के मान को देखने पर यहाँ 1 ≤ k ≤ n, जिसके लिए $k$ पंक्तियाँ $n/2$ शून्य और $n/2$ के मान के लिए होती हैं। यहाँ फ़ंक्शन f जिस पर मेमोइज़ेशन लागू किया गया है, पूर्णांकों के n जोड़े के वैक्टर को स्वीकार्य बोर्डों (समाधान) की संख्या में मैप करता है। प्रत्येक कॉलम के लिए जोड़ी है, और इसके दो घटक क्रमशः शून्य की संख्या और उस कॉलम में अभी तक रखे जाने वाले लोगों को इंगित करते हैं। हम का मूल्य खोजते हैं $f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))$ ($n$ तर्क या वेक्टर $n$ तत्व)। उप-समस्याओं के निर्माण की प्रक्रिया में प्रत्येक पर पुनरावृति ${\tbinom {n}{n/2}}$ पर सम्मलित करता है, बोर्ड की शीर्ष पंक्ति के लिए संभावित असाइनमेंट, और प्रत्येक कॉलम के माध्यम से जाना, उस कॉलम के जोड़े के उपयुक्त तत्व से घटाना, इस पर निर्भर करता है कि शीर्ष पंक्ति के असाइनमेंट में शून्य है या इसकी परीलक्षित स्थिति में हैं। यदि कोई परिणाम ऋणात्मक है, तो असाइनमेंट अमान्य होगा और समाधान के सेट में योगदान नहीं करता है (पुनरावर्तन बंद हो जाता है)। अन्यथा, हमारे पास शीर्ष पंक्ति k × n के लिए असाइनमेंट उपलब्ध है जो बोर्ड और पुनरावर्ती रूप से शेष के (k − 1) × n संख्या की गणना करता हैं बोर्ड, शीर्ष पंक्ति के प्रत्येक स्वीकार्य असाइनमेंट के लिए समाधान की संख्या जोड़ना और योग वापस करना, जिसे याद किया जा रहा है। आधार स्थिति तुच्छ उपसमस्या है, जो a के लिए 1 × n मान प्रकट करता है। इस बोर्ड के समाधान की संख्या या तो शून्य या है, यह इस बात पर निर्भर करता है कि सदिश जिसका क्रमचय n / 2 $(0,1)$ और n / 2 $(1,0)$ जोड़े हैं या नहीं है।

उदाहरण के लिए ऊपर दिखाए गए पहले दो बोर्डों में सदिशों का क्रम होगा

((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) K = 4

 0 1 0 1 0 0 1 1

((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) K = 3

 1 0 1 0 0 0 1 1

((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) K = 2

 0 1 0 1 1 1 0 0

((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) K = 1

 1 0 1 0 1 1 0 0

((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0))

समाधान की संख्या (sequence A058527 in the OEIS) है

$1,\,2,\,90,\,297200,\,116963796250,\,6736218287430460752,\ldots$

गतिशील प्रोग्रामिंग दृष्टिकोण के मैपल कार्यान्वयन के लिंक बाहरी लिंक के बीच मिल सकते हैं।

चेकरबोर्ड

n × n वर्गों और लागत फंक्शन के साथ बिसात पर विचार करें c(i, j) जो वर्ग से जुड़ी लागत (i,j) (i पंक्ति होने के नाते, j स्तंभ होना) लौटाता है। उदाहरण के लिए (5 × 5 बिसात पर),

5	6	7	4	7	8
4	7	6	1	1	4
3	3	5	7	8	2
2	–	6	7	0	–
1	–	–	*5*	–	–
	1	2	3	4	5

इस प्रकार c(1, 3) = 5 मान लें कि चेकर था जो पहली रैंक (यानी, पंक्ति) पर किसी भी वर्ग से प्रारंभ हो सकता था और आप अंतिम रैंक तक पहुंचने के लिए सबसे छोटा रास्ता (प्रत्येक विज़िट की गई रैंक पर न्यूनतम लागत का योग) जानना चाहते थे, यह मानते हुए कि चेकर केवल तिरछे बाएँ आगे, तिरछे दाएँ आगे या सीधे आगे बढ़ सकता है। यानी चेकर ऑन (1,3) (2,2), (2,3) या (2,4) में जा सकते हैं

5
4
3
2		x	x	x
1			o
	1	2	3	4	5

यह समस्या इष्टतम सबस्ट्रक्चर प्रदर्शित करती है। अर्थात्, संपूर्ण समस्या का समाधान उप-समस्याओं के समाधान पर निर्भर करता है। आइए फ़ंक्शन को परिभाषित करें q(i, j) जैसा

q(i, j) = वर्ग (i, j) तक पहुँचने के लिए न्यूनतम लागत हैं।

रैंक से प्रारंभ n और रैंक पर उतरना 1, हम प्रत्येक क्रमिक रैंक पर सभी वर्गों के लिए इस फ़ंक्शन के मान की गणना करते हैं। प्रत्येक रैंक पर न्यूनतम मान रखने वाले वर्ग को चुनना हमें रैंक n और रैंक 1 के बीच सबसे छोटा रास्ता देता है।

फंक्शन q(i, j) इसके नीचे के तीन वर्गों में से किसी तक पहुंचने के लिए न्यूनतम लागत के बराबर है (चूंकि केवल वही वर्ग हैं जो इस तक पहुंच सकते हैं) प्लस c(i, j). उदाहरण के लिए:

5
4			A
3		B	C	D
2
1
	1	2	3	4	5

$q(A)=\min(q(B),q(C),q(D))+c(A)\,$

अब, परिभाषित करते हैं q(i, j) कुछ अधिक सामान्य शब्दों में:

$q(i,j)={\begin{cases}\infty &j<1{\text{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}$

इस समीकरण की पहली पंक्ति बोर्ड से संबंधित है जिसे वर्गों के रूप में अनुक्रमित किया गया है 1 सबसे कम सीमा पर और n उच्चतम सीमा पर। दूसरी पंक्ति निर्दिष्ट करती है कि पहली रैंक पर क्या होता है, आधार स्थिति प्रदान करना हैं। तीसरी पंक्ति, प्रत्यावर्तन, महत्वपूर्ण भाग है। यह प्रतिनिधित्व करता है उदाहरण के रूप में A,B,C,D इत्यादि। इस परिभाषा से हम सीधा पुनरावर्ती कोड प्राप्त कर सकते हैं q(i, j). निम्नलिखित स्यूडोकोड में, n बोर्ड का आकार है, c(i, j) लागत फंक्शन है, और min() कम से कम कई मान लौटाता है:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

यह फ़ंक्शन केवल पथ लागत की गणना करता है, जो वास्तविक पथ की नहीं हैं। हम नीचे वास्तविक पथ पर चर्चा करते हैं। यह, फाइबोनैचि-संख्या उदाहरण की तरह, बहुत धीमा है क्योंकि यह अतिव्यापी उप-समस्या विशेषता को भी प्रदर्शित करता है। यही है, यह ही पथ लागत को बार-बार पुनर्गणना करता है। हालाँकि, यदि हम दो-आयामी आव्यहु में पथ लागतों को संग्रहीत करते हैं, तो हम इसे नीचे-ऊपर फैशन में बहुत तेज़ी से गणना कर सकते हैं q[i, j] फ़ंक्शन का उपयोग करने के अतिरिक्त पाई जाती हैं। यह पुनर्गणना से बचा जाता है, आव्यहु के लिए आवश्यक सभी मान q[i, j] समय से पहले केवल बार गणना की जाती है। जिसके लिए पूर्व-गणना मान (i,j) जरूरत पड़ने पर बस ऊपर देखा जाता है।

हमें यह भी जानने की जरूरत है कि वास्तविक सबसे छोटा रास्ता क्या है। ऐसा करने के लिए, हम और आव्यहु का उपयोग करते हैं p[i, j], पूर्ववर्ती आव्यहु हैं। यह आव्यहु किसी भी वर्ग का पथ रिकॉर्ड करती है s. के पूर्ववर्ती s इंडेक्स के सापेक्ष ऑफ़सेट के रूप में मॉडलिंग किया गया है (में q[i, j]) की पूर्व-गणना पथ लागत की s. पूर्ण पथ का पुनर्निर्माण करने के लिए, हम इसके पूर्ववर्ती को देखते हैं s, फिर उस वर्ग का पूर्ववर्ती, फिर उस वर्ग का पूर्ववर्ती, और इसी प्रकार पुनरावर्ती रूप से, जब तक कि हम प्रारंभिक वर्ग तक नहीं पहुंच जाते हैं। निम्नलिखित स्यूडोकोड पर विचार करें:

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

अब शेष न्यूनतम खोजने और इसे प्रिंट करने की साधारण स्थिति है।

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if q[n, i] < min
            minIndex := i
            min := q[n, i]
    printPath(n, minIndex)

function printPath(y, x)
    print(x)
    print("<-")
    if y = 2
        print(x + p[y, x])
    else
        printPath(y-1, x + p[y, x])

अनुक्रम संरेखण

आनुवंशिकी में, अनुक्रम संरेखण महत्वपूर्ण अनुप्रयोग है जहां गतिशील प्रोग्रामिंग आवश्यक है। सामान्यतः, समस्या में तत्व को बदलने, डालने या हटाने वाले संपादन कार्यों का उपयोग करके अनुक्रम को दूसरे में परिवर्तित करना सम्मलित हैं। प्रत्येक ऑपरेशन की संबद्ध लागत होती है, और संपादन दूरी का पता लगाना है।

समस्या को स्वाभाविक रूप से पुनरावर्तन के रूप में कहा जा सकता है, अनुक्रम A को अनुक्रम B में या तो बेहतर रूप से संपादित किया जाता है:

1. B के पहले अक्षर को सम्मिलित करना, और A और B की इष्टतम संरेखण करना
2. A के पहले अक्षर को हटाना, और A और B की इष्टतम संरेखण करना
3. A के पहले अक्षर को B के पहले अक्षर से बदलना, और A और B की इष्टतम संरेखण का प्रदर्शन करना।

आंशिक संरेखण को आव्यहु में सारणीबद्ध किया जा सकता है, जहां सेल (i,j) में A[1..i] से B[1..j] के इष्टतम संरेखण की लागत सम्मलित है। सेल (i, j) में लागत की गणना संबंधित संचालन की लागत को उसके निकटतम सेल की लागत में जोड़कर और इष्टतम का चयन करके की जा सकती है।

विभिन्न संस्करण सम्मलित हैं, स्मिथ-वाटरमैन एल्गोरिथम और नीडलमैन-वुन्श एल्गोरिथम देखें।

हनोई पहेली का टॉवर

हनोई के टावर्स का मॉडल सेट (8 डिस्क के साथ)

'टी (4,3)' के लिए हनोई पहेली के टॉवर का एनिमेटेड समाधान।

हनोई की मीनार या हनोई की मीनारें गणितीय खेल या पहेली है। इसमें तीन छड़ें और विभिन्न आकारों की कई डिस्क होती हैं जो किसी भी छड़ पर स्लाइड कर सकती हैं। पहेली छड़ पर आकार के आरोही क्रम में साफ ढेर में डिस्क के साथ प्रारंभ होती है, जो शीर्ष पर सबसे छोटी होती है, इस प्रकार शंक्वाकार आकार बनाती है।

पहेली का उद्देश्य निम्नलिखित नियमों का पालन करते हुए पूरे ढेर को दूसरी छड़ पर ले जाना है:

• एक समय में केवल ही डिस्क को चलाया जा सकता है।
• प्रत्येक चाल में रॉड से ऊपरी डिस्क को लेना और दूसरी रॉड पर स्लाइड करना सम्मलित है, जो उस रॉड पर पहले से सम्मलित अन्य डिस्क के ऊपर हो सकती है।
• छोटी डिस्क के ऊपर कोई डिस्क नहीं रखी जा सकती है।

गतिशील प्रोग्रामिंग समाधान में बेलमैन समीकरण को हल करना सम्मलित है

S(n,h,t) = S(n-1,h, not(h,t)) , S(1,h,t) , S(n-1,not(h,t),t)

जहाँ n स्थानांतरित होने वाली डिस्क की संख्या को दर्शाता है, h होम रॉड को दर्शाता है, t लक्ष्य रॉड को दर्शाता है, not(h,t) तीसरी रॉड को दर्शाता है (न तो h और न ही t), संयोजन को दर्शाता है, और

S(n, h, t) := n डिस्क वाली समस्या का समाधान जिसे रॉड h से रॉड t में ले जाना है।

n = 1 के लिए समस्या तुच्छ है, अर्थात् S (1, h, t) = डिस्क को रॉड h से रॉड t तक ले जाएँ (केवल डिस्क शेष है)।

इस समाधान के लिए आवश्यक चालों की संख्या 2ⁿ − 1 है। यदि उद्देश्य चालों की संख्या को 'अधिकतम' करना है (बिना साइकिल चलाए) तो गतिशील प्रोग्रामिंग बेलमैन समीकरण थोड़ा अधिक जटिल है और 3ⁿ − 1 चालें आवश्यक हैं।

अंडे छोड़ने वाली पहेली

N = 2 अंडे और H = 36 मंजिलों वाली इमारत से जुड़ी इस प्रसिद्ध पहेली के उदाहरण का विवरण निम्नलिखित है: मान लीजिए कि हम जानना चाहते हैं कि 36 मंजिला इमारत में कौन सी मंजिल अंडे छोड़ने के लिए सुरक्षित है, और कौन से अंडे लैंडिंग पर टूट जाएंगे (यू.एस. अंग्रेजी शब्दावली का उपयोग करते हुए, जिसमें पहली मंजिल जमीनी स्तर पर है)। हम कुछ धारणाएँ बनाते हैं:

• जो अंडा गिरकर बच जाता है उसे फिर से उपयोग किया जाता है।
• टूटे हुए अंडे को फेंक देना चाहिए।
• गिरने का प्रभाव सभी अंडों पर जैसा होता है।
• यदि अंडा गिराने पर टूट जाता है तो ऊपर की खिड़की से गिराने पर टूट जाता है।
• यदि अंडा गिरने से बच जाता है, तो वह कम गिरने से बचेगा।
• इस बात से इंकार नहीं किया जाता है कि पहली मंजिल की खिड़कियां अंडे तोड़ती हैं, और न ही इस बात से इंकार किया जाता है कि अंडे 36 वीं मंजिल की खिड़कियों से बच सकते हैं।

यदि केवल अंडा उपलब्ध हो और हम सही परिणाम प्राप्त करना सुनिश्चित करना चाहते हैं, तो प्रयोग केवल ही विधियाँ से किया जा सकता है। पहली मंजिल की खिड़की से अंडा गिराओ, यदि यह बच जाता है, तो इसे दूसरी मंजिल की खिड़की से गिरा दें। इस प्रकार ऊपर की ओर से तब तक यह प्रक्रिया जारी रखते हैं जब तक कि यह टूट न जाए। सबसे खराब स्थिति में, इस विधि में 36 बूंदों की आवश्यकता हो सकती है। मान लीजिए 2 अंडे उपलब्ध हैं। अंडे की बूंदों की सबसे कम संख्या क्या है जो सभी मामलों में कार्य करने की गारंटी देती है?

इस पहेली के लिए गतिक प्रोग्रामिंग बेलमैन समीकरण प्राप्त करने के लिए, गतिक प्रोग्रामिंग मॉडल की स्थिति को जोड़ी s = (n, के) होने दें, जहां

n = उपलब्ध परीक्षण अंडों की संख्या, n = 0, 1, 2, 3, ..., N − 1।

k = (क्रमानुसार) मंजिलों की संख्या जिनका अभी परीक्षण किया जाना है, k = 0, 1, 2, ..., H − 1।

उदाहरण के लिए, s = (2,6) इंगित करता है कि दो परीक्षण अंडे उपलब्ध हैं और 6 (लगातार) मंजिलों का परीक्षण किया जाना बाकी है। प्रक्रिया की प्रारंभिक अवस्था s = (N,H) है जहाँ N प्रयोग के प्रारंभ में उपलब्ध परीक्षण अंडों की संख्या को दर्शाता है। यह प्रक्रिया या तो समाप्त हो जाती है या जब n = 0 होने पर या जब k = 0, जो भी पहले होता है तो इन्में से कोई और परीक्षण अंडे पर नहीं किया जाचा हैं। यदि समाप्ति स्थिति s = (0,k) और k > 0 पर होती है, तो परीक्षण विफल माना जाता हैं।

W(n,k) = सबसे बुरी स्थिति के अनुसार महत्वपूर्ण मंजिल के मूल्य की पहचान करने के लिए आवश्यक परीक्षणों की न्यूनतम संख्या यह देखते हुए कि प्रक्रिया s' = (n,k) की स्थिति में है '

तभी यह दिखाया जा सकता है

आव्युह श्रृंखला गुणन

Main article: मैट्रिक्स श्रृंखला गुणन

आव्युह श्रृंखला गुणन प्रसिद्ध उदाहरण है जो गतिक प्रोग्रामिंग की उपयोगिता को प्रदर्शित करता है। उदाहरण के लिए, अभियांत्रिकी अनुप्रयोगों को अधिकांशतः आव्यहु की श्रृंखला को गुणा करना पड़ता है। बड़े आयामों के आव्यूहों को खोजना आश्चर्यजनक नहीं है, उदाहरण के लिए 100×100 इत्यादि। इसलिए, हमारा कार्य आव्युह $A_{1},A_{2},....A_{n}$. को गुणा करना है, आव्युह गुणन विनिमेय नहीं है, किन्तु साहचर्य है, और हम समय में केवल दो आव्यूहों का ही गुणा कर सकते हैं। इसलिए, हम आव्युह की इस श्रृंखला को कई अलग-अलग विधियों से गुणा कर सकते हैं, उदाहरण के लिए:

((A₁ × A₂) × A₃) × ... A_n

A₁×(((A₂×A₃)× ... ) × A_n)

(A₁ × A₂) × (A₃ × ... A_n)

और इसी प्रकार आव्युह की इस श्रृंखला को गुणा करने के कई विधियाँ हैं। वे सभी ही अंतिम परिणाम देंगे, चूंकि उन्हें गणना करने में अधिक या कम समय लगेगा, जिसके आधार पर विशेष आव्युह को गुणा किया जाता है। यदि आव्युह A का आयाम m×n है और आव्युह B का आयाम n×q है, तो आव्युह C=A×B का आयाम m×q होगा, और इसके लिए m*n*q स्केलर गुणन की आवश्यकता होगी (उद्देश्यों के लिए सरलीकृत आव्युह गुणन एल्गोरिथ्म का उपयोग करके) चित्रण में दिखाया गया हैं।

उदाहरण के लिए, आइए आव्यूहों A, B और C का गुणा करें। मान लें कि उनकी विमाएँ क्रमशः m×n, n×p और p×s हैं। आव्युह A×B×C का आकार m×s होगा और इसकी गणना नीचे दिखाए गए दो विधियों से की जा सकती है:

1. x (b × c) आव्युह गुणा के इस क्रम में nps + mns स्केलर गुणा की आवश्यकता होगी।
2. (A×B)×C आव्युह गुणन के इस क्रम में mnp + mps स्केलर गणना की आवश्यकता होगी।

मान लें कि m = 10, n = 100, p = 10 और s = 1000 है। इसलिए, श्रृंखला को गुणा करने के पहले विधियाँ के लिए 1,000,000 + 1,000,000 गणनाओं की आवश्यकता होगी। दूसरे विधियाँ में केवल 10,000+100,000 गणनाओं की आवश्यकता होगी। प्रकट है, दूसरा विधि तेज है, और हमें कोष्ठक की उस व्यवस्था का उपयोग करके आव्युह को गुणा करना चाहिए।

इसलिए, हमारा निष्कर्ष यह है कि कोष्ठकों के क्रम में परिवर्तन ना हों, और हमारा कार्य कोष्ठकों के इष्टतम क्रम को खोजना है।

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

m[i,j] को आव्युह i से आव्युह j (अर्थात् A) में आव्युह की श्रृंखला को गुणा करने के लिए आवश्यक स्केलर गुणन की न्यूनतम संख्या कहते हैं। इस प्रकार ×_i .... × a_j, अर्थात i <= j) की श्रृंखला को कुछ आव्युह k पर विभाजित करते हैं, जैसे कि i <= k <j, और यह पता लगाने का प्रयास करें कि कौन सा संयोजन न्यूनतम m [i, j] उत्पन्न करता है।

सूत्र है:

          if i = j, m[i,j]= 0

       if i < j, m[i,j]= min over all possible values of k (m[i,k]+m[k+1,j] + ) 

• $p_{i-1}$ आव्युह i का पंक्ति आयाम है,
• $p_{k}$ आव्युह k का स्तंभ आयाम है,
• $p_{j}$ आव्युह j का स्तंभ आयाम है।

इस सूत्र को नीचे दिखाए अनुसार कोडित किया जा सकता है, जहां इनपुट पैरामीटर चेन आव्यहु की श्रृंखला है, अर्थात $A_{1},A_{2},...A_{n}$:

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + 
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update

                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

अब तक, हमने सभी संभव के लिए मूल्यों m[i, j] की गणना की है, आव्युह i से आव्युह j तक श्रृंखला को गुणा करने के लिए गणनाओं की न्यूनतम संख्या, और हमने संबंधित विभाजन बिंदु s[i, j] पर अंकित किया है। उदाहरण के लिए, यदि हम श्रृंखला को A₁×A₂×A₃×A₄ द्वारा गुणा कर रहे हैं, और इस प्रकार इसका मान m[1, 3] = 100 और s[1, 3] = 2 के रूप में प्राप्त होता हैं इसका मतलब है कि आव्युह 1 से 3 के लिए कोष्ठक का इष्टतम स्थान है $(A_{1}\times A_{2})\times A_{3}$ और उन आव्यूहों को गुणा करने के लिए 100 अदिश गणनाओं की आवश्यकता होगी।

यह एल्गोरिद्म टेबल m[, ] और s[, ] तैयार करेगा जिसमें i और j के सभी संभावित मानों की प्रविष्टियां होंगी। संपूर्ण श्रृंखला के लिए अंतिम समाधान m [1, n] है, जो s [1, n] पर संबंधित विभाजन के साथ है। समाधान को खोलना पुनरावर्ती होगा, ऊपर से प्रारंभ होकर तब तक जारी रहेगा जब तक हम आधार स्थिति तक नहीं पहुंच जाते, अर्थात एकल आव्युह का गुणन किया जाता हैं।

इसलिए अगला उद्देश्य वास्तव में श्रृंखला को विभाजित करना है, अर्थात कोष्ठक को वहां रखना है जहां वे इष्टतम रूप से संबंधित हैं। इस उद्देश्य के लिए हम निम्नलिखित एल्गोरिथम का उपयोग कर सकते हैं:

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 

        print ")"

यह एल्गोरिदम वास्तविक गुणा के लिए उपयोगी नहीं है। परिणाम कैसा दिखता है यह देखने के लिए यह एल्गोरिथ्म सिर्फ उपयोगकर्ता के अनुकूल विधि है।

वास्तव में उचित विभाजन का उपयोग करके आव्यहु को गुणा करने के लिए, हमें निम्नलिखित एल्गोरिथम की आवश्यकता है:

      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         LeftSide = OptimalMatrixMultiplication(s, i, s[i, j])
         RightSide = OptimalMatrixMultiplication(s, s[i, j] + 1, j)
         return MatrixMultiply(LeftSide, RightSide) 
      else if i = j
         return Ai   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 

          print "error, incompatible dimensions."  

इतिहास

गतिक प्रोग्रामिंग शब्द का उपयोग मूल रूप से 1940 के दशक में रिचर्ड बेलमैन द्वारा समस्याओं को हल करने की प्रक्रिया का वर्णन करने के लिए किया गया था, जहाँ बाद के सर्वश्रेष्ठ निर्णय खोजने की आवश्यकता होती है। 1953 तक, उन्होंने इसे आधुनिक अर्थ में परिष्कृत किया, विशेष रूप से बड़े निर्णयों के अंदर छोटी निर्णय समस्याओं को नेस्ट बनाने के लिए संदर्भित करते हुए, और उसके बाद क्षेत्र को IEEE द्वारा प्रणाली विश्लेषण और अभियांत्रिकी विषय के रूप में मान्यता दी गई। बेलमैन के योगदान को बेलमैन समीकरण के नाम से याद किया जाता है, जो गतिक प्रोग्रामिंग का केंद्रीय परिणाम है जो पुनरावर्तन (कंप्यूटर विज्ञान) रूप में अनुकूलन समस्या को पुनर्स्थापित करता है।

बेलमैन अपनी आत्मकथा, आई ऑफ द हरिकेन: एन ऑटोबायोग्राफी में गतिक प्रोग्रामिंग शब्द के पीछे तर्क बताते हैं:

मैंने फॉल क्वार्टर (1950 का) रैंड में बिताया। मेरा पहला कार्य मल्टीस्टेज डिसीजन प्रोसेस के लिए नाम खोजना था। एक रोचक सवाल है, "गतिक प्रोग्रामिंग नाम कहां से आया?" 1950 का दशक गणितीय शोध के लिए अच्छा वर्ष नहीं था। वाशिंगटन में हमारे एक बहुत ही रोचक सज्जन थे जिनका नाम विल्सन था। वह रक्षा सचिव थे, और उन्हें वास्तव में "अनुसंधान" शब्द का एक रोगात्मक भय और घृणा थी। मैं इस शब्द का हल्के में उपयोग नहीं कर रहा हूँ, मैं इसका सटीक उपयोग कर रहा हूं। अगर लोग उसके होने से शोध शब्द का उपयोग करते तो उसका चेहरा सूज जाता, वह लाल हो जाता और वह हिंसक हो जाता। आप कल्पना कर सकते हैं कि तब उन्हें गणितीय शब्द के बारे में कैसा लगा होगा। रैंड कार्पोरेशन को वायु सेना द्वारा नियोजित किया गया था, और वायु सेना के पास अनिवार्य रूप से विल्सन उसका बॉस था। इसलिए, मुझे लगा कि मुझे विल्सन और वायु सेना को इस तथ्य से बचाने के लिए कुछ करना होगा कि मैं वास्तव में रैंड कॉर्पोरेशन के अंदर गणित कर रहा था। मैं कौन सा शीर्षक, कौन सा नाम चुन सकता हूं? सबसे पहले तो मुझे योजना बनाने में, निर्णय लेने में, सोचने में रोचक थी। लेकिन नियोजन, विभिन्न कारणों से एक अच्छा शब्द नहीं है। इसलिए मैंने "प्रोग्रामिंग" शब्द का उपयोग करने का निर्णय लिया। मैं इस विचार के पार जाना चाहता था कि यह गतिशील था, यह बहुस्तरीय था, यह समय-भिन्न था। मैंने सोचा, चलो एक तीर से दो शिकार करते हैं। आइए एक ऐसा शब्द लें जिसका मौलिक भौतिक अर्थों में बिल्कुल सटीक अर्थ है, अर्थात् गतिशील। विशेषण के रूप में इसकी बहुत ही रोचक विशेषता है, और यह है कि डायनेमिक शब्द का उपयोग एक अपमानजनक अर्थ में करना असंभव है। कुछ संयोजन के बारे में सोचने का प्रयास करें जो संभवतः निंदनीय अर्थ देगा। यह नामुमकिन है। इस प्रकार, मैंने सोचा कि गतिशील प्रोग्रामिंग एक अच्छा नाम था। यह कुछ ऐसा था जिस पर कोई कांग्रेसी भी आपत्ति नहीं कर सकता था। इसलिए मैंने इसे अपनी गतिविधियों के लिए छतरी के रूप में उपयोग किया।

— रिचर्ड बेलमैन, आई ऑफ द हरिकेन: एन ऑटोबायोग्राफी (1984, पृष्ठ 159)

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

शब्द की उत्पत्ति की उपरोक्त व्याख्या में कमी है। जैसा कि रसेल और नॉर्विग ने अपनी किताब में उपरोक्त कहानी का प्रस्तुत करते हुए लिखा है: यह पूर्ण रूप से सच नहीं हो सकता, क्योंकि इस शब्द का उपयोग करने वाला उनका पहला पेपर (बेलमैन, 1952) 1953 में विल्सन के रक्षा सचिव बनने से पहले छपा था। साथ ही, हैराल्ड जे. कुश्नेरr के भाषण में टिप्पणी है, जहां उसे बेलमैन की याद आती है। बेलमैन के बारे में बोलते हुए कुश्नर को उद्धृत करते हुए: दूसरी ओर, जब मैंने उनसे वही सवाल पूछा, तो उन्होंने उत्तर दिया कि वह गतिक जोड़कर डेंटज़िग की रैखिक प्रोग्रामिंग को ऊपर उठाने का प्रयास कर रहे थे। संभवतः इसकी दोनों प्रेरणाएँ सही थीं।

गतिक प्रोग्रामिंग का उपयोग करने वाले एल्गोरिदम

• प्रोटीन-डीएनए बाइंडिंग के लिए जाली मॉडल का आवर्तक समाधान
• परिमित-क्षितिज असतत-समय गतिक अनुकूलन समस्याओं के लिए समाधान विधि के रूप में पिछड़ा प्रेरण
• अनंत-क्षितिज, असतत-समय, छूट, समय-अपरिवर्तनीय प्रणाली में बेलमैन समीकरण को हल करने के लिए अनिर्धारित गुणांक की विधि का उपयोग किया जा सकता है। समय-अपरिवर्तनीय गतिक अनुकूलन समस्याएं
• कई स्ट्रिंग (कंप्यूटर विज्ञान) एल्गोरिदम जिनमें सबसे लंबी सामान्य अनुवर्ती समस्या, सबसे लंबी बढ़ती अनुवर्ती समस्या, सबसे लंबी सामान्य सबस्ट्रिंग समस्या, लेवेनशेटिन दूरी (दूरी संपादित करें) सम्मलित हैं
• ग्राफ के पेड़ अपघटन पर गतिक प्रोग्रामिंग का उपयोग करके अप्रत्यक्ष ग्राफ पर कई एल्गोरिदमिक समस्याओं को बाध्य पेड़ की चौड़ाई या बाध्य क्लिक-चौड़ाई के ग्राफ के लिए कुशलतापूर्वक हल किया जा सकता है।
• CYK एल्गोरिथम या कॉके-यंगर-कसामी (CYK) एल्गोरिथम जो यह निर्धारित करता है कि दिए गए संदर्भ-मुक्त व्याकरण द्वारा दी गई स्ट्रिंग को कैसे और कैसे उत्पन्न किया जा सकता है
• वर्ड रैप या नुथ का वर्ड रैपिंग एल्गोरिथम जो वर्ड रैपिंग टेक्स्ट के समय रैग्डनेस को कम करता है
• कंप्यूटर शतरंज में ट्रांसपोजिशन टेबल और खंडन सूची का उपयोग
• Viterbi एल्गोरिथ्म (छुपे छिपा हुआ मार्कोव मॉडल के लिए उपयोग किया जाता है, और विशेष रूप से भाषण टैगिंग के भाग में)
• अर्ली एल्गोरिथम (एक प्रकार का चार्ट पार्सर)
• नीडलमैन-वुन्श एल्गोरिथम और जैव सूचना विज्ञान में उपयोग किए जाने वाले अन्य एल्गोरिदम, जिसमें अनुक्रम संरेखण, संरचनात्मक संरेखण, आरएनए संरचना सम्मलित है* फ्लोयड-वॉर्शल एल्गोरिथमयाफ्लोयड का ऑल-पेयर शॉर्टेस्ट पाथ एल्गोरिथम
• श्रृंखला आव्युह गुणन के क्रम का अनुकूलन
• सबसेट योग समस्या, नैपसैक समस्या और विभाजन समस्या समस्याओं के लिए छद्म-बहुपद समय एल्गोरिदम
• दो समय श्रृंखला के बीच वैश्विक दूरी की गणना के लिए गतिक समय वारिंग एल्गोरिदम
• रिलेशनल डेटाबेस क्वेरी ऑप्टिमाइज़ेशन के लिए पेट्रीसिया सेलिंगर (उर्फ आईबीएम प्रणाली आर) एल्गोरिथम
• बी-स्पलाइन वक्रों के मूल्यांकन के लिए दे बूर अल्गोरिथम
• क्रिकेट के खेल बाधित होने पर समस्या के समाधान के लिए डकवर्थ-लुईस पद्धति
• मार्कोव निर्णय प्रक्रियाओं को हल करने के लिए मूल्य पुनरावृत्ति विधि
• फोटोशॉप में चुंबक चयन उपकरण जैसे चयन विधियों के बाद कुछ ग्राफिक इमेज एज
• अंतराल समयबद्धन समस्याओं को हल करने के लिए कुछ विधियाँ
• ट्रैवलिंग सेल्समैन की समस्या को हल करने के कुछ विधियाँ, या तो बिल्कुल (घातीय समय में) या लगभग (जैसे बिटोनिक टूर के माध्यम से)
• रिकर्सिव कम से कम वर्ग विधि
• संगीत सूचना पुनर्प्राप्ति में बीट (संगीत) ट्रैकिंग
• कृत्रिम तंत्रिका नेटवर्क के लिए अनुकूली-आलोचक प्रशिक्षण रणनीति
• स्टीरियो विजन में उपयोग की जाने वाली पत्राचार समस्या को हल करने के लिए स्टीरियो एल्गोरिदम
• सीम नक्काशी (सामग्री-जागरूक छवि का आकार बदलना)
• बेलमैन-फोर्ड एल्गोरिथम ग्राफ में सबसे छोटी दूरी खोजने के लिए
• रैखिक खोज समस्या के लिए कुछ अनुमानित समाधान विधियाँ
• कडाने का एल्गोरिथम अधिकतम सबर्रे समस्या के लिए
• वीन ऑटोमैटिक प्रणाली प्लानिंग (WASP) पैकेज में बिजली उत्पादन विस्तार योजनाओं का अनुकूलन

यह भी देखें

• अर्थशास्त्र में उत्तलता
• लालची एल्गोरिदम
• गैर-उत्तलता (अर्थशास्त्र)
• स्टोकेस्टिक प्रोग्रामिंग – Framework for modeling optimization problems that involve uncertainty
• स्टोचैस्टिक गतिशील प्रोग्रामिंग
• सुदृढीकरण सीखना

अग्रिम पठन

• Adda, Jerome; Cooper, Russell (2003), Dynamic Economics, MIT Press, ISBN 9780262012010. An accessible introduction to dynamic programming in economics. MATLAB code for the book Archived 2020-10-09 at the Wayback Machine.
• Bellman, Richard (1954), "The theory of dynamic programming", Bulletin of the American Mathematical Society, 60 (6): 503–516, doi:10.1090/S0002-9904-1954-09848-8, MR 0067459. Includes an extensive bibliography of the literature in the area, up to the year 1954.
• Bellman, Richard (1957), Dynamic Programming, Princeton University Press. Dover paperback edition (2003), ISBN 0-486-42809-5.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 978-0-262-03293-3. Especially pp. 323–69.
• Dreyfus, Stuart E.; Law, Averill M. (1977), The Art and Theory of Dynamic Programming, Academic Press, ISBN 978-0-12-221860-6.
• Giegerich, R.; Meyer, C.; Steffen, P. (2004), "A Discipline of Dynamic Programming over Sequence Data" (PDF), Science of Computer Programming, 51 (3): 215–263, doi:10.1016/j.scico.2003.12.005.
• Meyn, Sean (2007), Control Techniques for Complex Networks, Cambridge University Press, ISBN 978-0-521-88441-9, archived from the original on 2010-06-19.
• Sritharan, S. S. (1991). "Dynamic Programming of the Navier-Stokes Equations". Systems and Control Letters. 16 (4): 299–307. doi:10.1016/0167-6911(91)90020-f.
• Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989), Recursive Methods in Economic Dynamics, Harvard Univ. Press, ISBN 978-0-674-75096-8.

बाहरी संबंध

• A Tutorial on Dynamic programming
• MIT course on algorithms - Includes 4 video lectures on DP, lectures 19-22
• Applied Mathematical Programming by Bradley, Hax, and Magnanti, Chapter 11
• More DP Notes
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." An introduction to dynamic programming as an important tool in economic theory.
• Dynamic Programming: from novice to advanced A TopCoder.com article by Dumitru on Dynamic Programming
• Algebraic Dynamic Programming – a formalized framework for dynamic programming, including an entry-level course to DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
• Dynamic programming tutorial
• A Gentle Introduction to Dynamic Programming and the Viterbi Algorithm
• Tabled Prolog BProlog, XSB, SWI-Prolog
• IFORS online interactive dynamic programming modules including, shortest path, traveling salesman, knapsack, false coin, egg dropping, bridge and torch, replacement, chained matrix products, and critical path problem.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}