फ़िबोनाची और गतिशील प्रोग्रामिंग

कंप्यूटर से सबसे सीधे तरीके से 40वीं फ़िबोनाची संख्या माँगें, तो वह 33 करोड़ से ज़्यादा कॉल करता है। टेबल के साथ माँगें, तो उसे 39 जोड़ चाहिए। यही फ़र्क गतिशील प्रोग्रामिंग है, और लगभग हर कोई इससे पहली बार फ़िबोनाची संख्याओं के ज़रिए ही मिलता है।

फ़िबोनाची संख्याओं वाले टेबल सेल की एक पंक्ति, जिसमें भरा जा रहा सेल नारंगी है और जिन दो सेल को वह जोड़ता है वे नीले हैं
फ़िबोनाची संख्याओं वाले टेबल सेल की एक पंक्ति, जिसमें भरा जा रहा सेल नारंगी है और जिन दो सेल को वह जोड़ता है वे नीले हैं

समस्या

फ़िबोनाची संख्याएँ 0, 1 से शुरू होती हैं, और बाद की हर संख्या अपने से पहले की दो संख्याओं का योग होती है: 0, 1, 1, 2, 3, 5, 8, 13, 21 वगैरह। नियम के रूप में लिखें तो F(0) = 0, F(1) = 1 और F(n) = F(n − 1) + F(n − 2)। यह नियम रिकर्सिव है, और इसे सीधे एक रिकर्सिव प्रोग्राम में बदलना आसान है, लेकिन वह प्रोग्राम बहुत धीमा निकलता है।

रिकर्शन ख़ुद को क्यों दोहराता है

F(5) निकालने के लिए प्रोग्राम F(4) और F(3) माँगता है। F(4) फिर F(3) और F(2) माँगता है, इसलिए F(3) दो बार, F(2) तीन बार और F(1) पाँच बार निकाला जाता है। ट्री के रूप में बनाएँ तो हर स्तर पर कॉल लगभग दोगुनी हो जाती हैं, और F(n) के लिए कुल 2·F(n + 1) − 1 कॉल होती हैं। छोटी समस्याएँ एक-दूसरे पर चढ़ी हैं: वही समस्याएँ बार-बार लौटती हैं। यही संकेत है कि गतिशील प्रोग्रामिंग काम आएगी।

याद रखने के दो तरीके

मेमोइज़ेशन रिकर्शन बनाए रखता है पर हर उत्तर टेबल में लिख देता है, और हर कॉल कोई भी काम करने से पहले टेबल में देखती है। टेबुलेशन टेबल को बॉटम-अप भरता है: पहले F(0) और F(1), फिर उनसे F(2), F(2) और F(1) से F(3), और इसी तरह F(n) तक। दोनों ही तरीकों में हर पद एक बार निकाला जाता है, इसलिए F(n) में घातांकी (exponential) संख्या में कॉल की जगह n − 1 जोड़ लगते हैं।

एक उदाहरण

F(7) के लिए बॉटम-अप: 0 और 1 से शुरू करें। फिर 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 और 5 + 8 = 13, इसलिए छह जोड़ के बाद F(7) = 13। यही उत्तर पाने के लिए सामान्य रिकर्शन 2·F(8) − 1 = 41 कॉल करता। टॉप-डाउन में, पहली कॉल ट्री के बाएँ किनारे से होते हुए सीधे F(1) तक नीचे जाती हैं; वापस ऊपर आते समय लगभग हर दूसरी कॉल को अपना उत्तर टेबल में पहले से मिल जाता है।

नाम कहाँ से आया

रिचर्ड बेलमैन ने 1950 के दशक की शुरुआत में RAND कॉर्पोरेशन में काम करते हुए गतिशील प्रोग्रामिंग को यह नाम दिया। बाद में उन्होंने लिखा कि उन्होंने programming शब्द उसके पुराने अर्थ, यानी योजना बनाने, के लिए चुना, और dynamic इसलिए कि यह प्रभावशाली लगता था और इस पर आपत्ति करना मुश्किल था। यह तरीका ख़ुद, यानी किसी समस्या को उसके छोटे रूपों के उत्तरों से हल करना, आज स्पेल चेकर, रूट प्लानर और DNA की तुलना में इस्तेमाल होता है।

1962 में रिचर्ड बेलमैन, अल्फ़्रेड आइज़ेनस्टाट द्वारा खींची गई तस्वीर। 1950 के दशक की शुरुआत में RAND कॉर्पोरेशन में काम करते हुए उन्होंने डायनेमिक प्रोग्रामिंग को यह नाम दिया।
1962 में रिचर्ड बेलमैन, अल्फ़्रेड आइज़ेनस्टाट द्वारा खींची गई तस्वीर। 1950 के दशक की शुरुआत में RAND कॉर्पोरेशन में काम करते हुए उन्होंने डायनेमिक प्रोग्रामिंग को यह नाम दिया।

ख़ुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। बॉटम-अप में, नारंगी सेल भरा जा रहा है और दो नीले सेल वे पद हैं जिन्हें वह जोड़ता है। टॉप-डाउन पर जाएँ और देखें कि टेबल के नीचे कॉल का स्टैक n तक बढ़ता है, फिर उत्तर लौटने के साथ छोटा होता जाता है; “जोड़” के नीचे का संकेत गिनता है कि कितनी कॉल का उत्तर सीधे टेबल से मिला।

अक्सर पूछे जाने वाले प्रश्न

ओवरलैपिंग सबप्रॉब्लम क्या होती हैं?

ऐसी छोटी समस्याएँ जिनकी किसी हल को एक से ज़्यादा बार ज़रूरत पड़ती है। F(n) और F(n − 1) दोनों को F(n − 2) चाहिए, इसलिए सामान्य रिकर्शन उसे दो बार निकालता है, और नीचे जाते-जाते यह बर्बादी और कई गुना हो जाती है। गतिशील प्रोग्रामिंग हर एक को एक बार हल करती है और उत्तर याद रखती है।

क्या मेमोइज़ेशन टेबुलेशन से तेज़ है?

दोनों वही जोड़ करते हैं। टेबुलेशन आम तौर पर थोड़ा तेज़ होता है क्योंकि यह कोई कॉल नहीं करता, और इसमें स्टैक की जगह ख़त्म नहीं हो सकती; मेमोइज़ेशन तब काम का है जब केवल कुछ छोटे उत्तरों की ज़रूरत हो, क्योंकि यह केवल उन्हीं को निकालता है।

क्या फ़िबोनाची संख्याएँ और भी तेज़ी से निकाली जा सकती हैं?

हाँ। F(2k) = F(k)·(2·F(k + 1) − F(k)) और F(2k + 1) = F(k)² + F(k + 1)² का इस्तेमाल करके, फ़ास्ट डबलिंग विधि को केवल लगभग log₂ n चरण चाहिए। स्वर्ण अनुपात वाला बिने का सूत्र भी वही संख्याएँ देता है, लेकिन राउंडिंग की गलतियों के कारण बड़े n के लिए उस पर भरोसा नहीं किया जा सकता।

टेबल को कितनी मेमोरी चाहिए?

पूरी टेबल में n + 1 संख्याएँ होती हैं, लेकिन हर नए पद को केवल अपने से पहले के दो पद चाहिए, इसलिए दो संख्याएँ रखने वाला लूप यही काम स्थिर (constant) मेमोरी में कर देता है। पूरी टेबल रखना तब उपयोगी है जब आपको सारे पद चाहिए हों, या यह देखना हो कि विधि कैसे काम करती है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

गतिशील प्रोग्रामिंग से फ़िबोनाची आज़माएँ