डायनेमिक प्रोग्रामिंग ब्लैक मैजिक नहीं है

डायनेमिक प्रोग्रामिंग जादू नहीं है

• डायनेमिक प्रोग्रामिंग एक ऐसी तकनीक है जिसका उपयोग जटिल समस्याओं को हल करने के लिए किया जाता है, जिसमें उन्हें छोटी समस्याओं में बाँटकर हल किया जाता है।
• यह तकनीक स्वाभाविक है, और कई सामान्य algorithms वास्तव में खास समस्याओं पर डायनेमिक प्रोग्रामिंग का ही अनुप्रयोग हैं।
• डायनेमिक प्रोग्रामिंग को समझने में मदद के लिए, यह एक आसान परिचय और विस्तृत व्याख्या प्रदान करता है।

शिकायत

• software engineering में naming अक्सर बहुत खराब होती है।
• 'bootstrap', 'daemon', 'cascading style sheets', 'cookie', 'artificial intelligence' जैसे शब्द अस्पष्ट या भ्रामक हो सकते हैं।
• 'डायनेमिक प्रोग्रामिंग' शब्द भी अपने आप में 'dynamic' से जुड़ा नहीं है; यह वास्तव में algorithm design में इस्तेमाल होने वाला एक विचार है।

बुनियादी caching

• जब आप किसी समस्या को छोटी समान समस्याओं में बाँटकर हल करने की कोशिश करते हैं, तो आपको वही छोटी समस्याएँ कई बार हल करनी पड़ सकती हैं।
• Fibonacci sequence के उदाहरण में, अगर इसे एक साधारण recursive function से लागू किया जाए, तो वही गणनाएँ बार-बार दोहराई जाती हैं।
• परिणामों को cache (या memoization) करके दोहराव वाली गणनाओं से बचा जा सकता है।

अनुकूलित caching

• memoization का उपयोग करने पर recursion बना रहता है, लेकिन जो चाहिए वही ज़रूरत पड़ने पर गणना की जाती है।
• इसके बजाय, आप जो कुछ भी चाहिए उसे पहले से गणना करने वाले तरीके से भी पहुँच सकते हैं।
• यह तरीका recursive calls के बिना समस्या हल करता है, और यही डायनेमिक प्रोग्रामिंग है।

edit distance

• दो strings के बीच edit distance वह न्यूनतम edits की संख्या है, जो एक string को दूसरी में बदलने के लिए चाहिए।
• edit distance को character replacement, insertion, और deletion शामिल करके निकाला जा सकता है, और इसे डायनेमिक प्रोग्रामिंग से कुशलतापूर्वक हल किया जा सकता है।
• आपको यह तरीका खोजना होता है कि छोटी समस्याओं के हल से पूरे समाधान तक कैसे पहुँचा जाए।

Advent of Code, Day 12

• 12 दिसंबर 2023 के Advent of Code प्रश्न में 1D nonogram को हल करना होता है।
• इसे brute force तरीके से हल किया जा सकता है, लेकिन इसकी complexity exponential होती है।
• इसके बजाय, डायनेमिक प्रोग्रामिंग लागू करके इसे कुशलतापूर्वक हल किया जा सकता है।

निष्कर्ष

• डायनेमिक प्रोग्रामिंग आसान नहीं है, लेकिन यह अधिकांश programmers की पहुँच से बाहर भी नहीं है।
• अगर आप समझ लें कि समस्या को छोटी समस्याओं में कैसे बाँटना है, तो आप कई स्थितियों में memoization का उपयोग कर सकते हैं, और यह naive implementation की तुलना में बड़ा सुधार होता है।
• डायनेमिक प्रोग्रामिंग में महारत हासिल करने से आप algorithms की एक पूरी class को समझ सकते हैं, trade-offs को बेहतर ढंग से समझ सकते हैं, और दूसरी optimizations को संभव बना सकते हैं।

GN⁺ की राय

• डायनेमिक प्रोग्रामिंग जटिल समस्याओं को कुशलतापूर्वक हल करने की एक महत्वपूर्ण तकनीक है, जो recursive approach की जगह छोटी समस्याओं के हल को cache करके दोहराव वाली गणनाओं को कम करती है और प्रदर्शन को काफी बेहतर बना सकती है।
• यह लेख उन शुरुआती software engineers के लिए बहुत उपयोगी है जो डायनेमिक प्रोग्रामिंग की बुनियादी अवधारणा को समझना चाहते हैं।
• Fibonacci sequence और edit distance के उदाहरण डायनेमिक प्रोग्रामिंग की अवधारणा समझने में मदद करते हैं और इसे वास्तविक समस्या-समाधान में लागू करने के लिए एक अच्छा शुरुआती बिंदु देते हैं।

[GN⁺]

Hacker News राय

• लेख में dynamic programming (DP) algorithm को recursion की caching के रूप में समझाना अच्छी बात है।

  • recursive solution खोजना, DP solution तक पहुँचने के लिए सबसे अच्छा शुरुआती बिंदु है।
  • recursive solution में memoization जोड़ने से speed में काफ़ी मदद मिल सकती है।
  • अहम बात यह है कि call tree में बहुत सारे subproblems होना ज़रूरी नहीं, बल्कि अपेक्षाकृत कम संख्या में unique subproblems होने चाहिए।

• यह पसंद आया कि लेख पहले समस्या को recursive तरीके से संभालता है, फिर धीरे-धीरे caching जोड़ता है, और उसके बाद उसे ज़रूरी cache size तक घटाता है।

  • dynamic programming solution को सीधे खोजने की कोशिश में पहले अटक चुका हूँ या बहुत ज़्यादा मेहनत लगी है।
  • आगे से मैं खुद को इसी क्रम में approach करने के लिए मजबूर करूँगा।

• dynamic programming का एक शानदार application nucleic acid/protein sequence की pairwise alignment है।

  • उदाहरण के लिए, sequence alignment, Needleman–Wunsch algorithm, Smith–Waterman algorithm आदि हैं।

• एक बेहद शानदार algorithms professor के बारे में अनुभव साझा किया गया।

  • professor ने UCLA में पढ़ाई की थी, और dynamic programming पर उनकी class बेहतरीन थी।
  • वे एक सरल लेकिन exponential complexity वाली problem से शुरू करते थे, फिर problem को छोटी problems में बाँटकर complexity को polynomial तक लाते थे, और उसके बाद memoization लगाकर उसे linear complexity तक गिरा देते थे।
  • काश, इस्तेमाल की गई problems याद होतीं।

• Dynamic Programming is not Black Magic नाम की पोस्ट का लिंक साझा किया गया।

  • उस पोस्ट तक पहुँचना बहुत ज़्यादा traffic की वजह से मुश्किल हो गया था (hug of death)।

• जो लोग ज़्यादातर self-taught तरीके से programming सीखते हैं, उनके लिए नौकरी ढूँढते समय अगर interview में dynamic programming इस्तेमाल करने को कहा जाता, तो शायद वे नहीं जानते होते कि यह क्या है।

  • ख़ुशक़िस्मती से ऐसा नहीं हुआ, और इस skill को जानने की वजह से कई interviews में इसका इस्तेमाल कर पाया।

• "dynamic programming" नाम ऐसा लग सकता है जैसे इसका संबंध programming field से हो।

  • असल में इसका संबंध optimization से है, और यह discrete time के decision problems को हल करने का एक तरीका है।
  • dynamic programming, value function V* को define करके optimization problem की dimension को काफ़ी कम करने की विधि है।

• यह सवाल उठाया गया कि "dynamic programming" सुनते ही सिर्फ़ "memoization" के बारे में सोचना क्या ग़लत है।

  • शायद इसमें जो बात छूट जाती है, वह यह है कि memoization को प्रभावी बनाने के लिए problem को चतुराई से divide करना पड़ता है।

• dynamic programming black magic नहीं है, लेकिन यह साबित करना कि किसी चीज़ को dynamic programming से हल किया जा सकता है और उसकी correctness को सिद्ध करना कठिन है।

  • greedy algorithms की तरह यहाँ भी mathematical induction का उपयोग करके formal proof की ज़रूरत होती है।

• dynamic programming में mastery पाने के लिए DPV algorithms book और Georgia Tech का Udacity course recommend किया गया।

  • problems हल करने की practice के ज़रिए dynamic programming सीखी जा सकती है।