فيبوناتشي والبرمجة الديناميكية

اطلب من الحاسوب عدد فيبوناتشي الأربعين بالطريقة البديهية، فيُجري أكثر من 331 مليون استدعاء. واطلبه منه باستخدام جدول، فيكفيه 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(3) من F(2) وF(1)، وهكذا حتى F(n). وفي الحالتين يُحسب كل حد مرة واحدة، فيكلّف F(n) عدد 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)؛ وفي طريق العودة إلى الأعلى، يجد كل استدعاء ثانٍ تقريبًا إجابته في الجدول مسبقًا.

من أين جاء الاسم

أطلق ريتشارد بيلمان اسم البرمجة الديناميكية في أوائل خمسينيات القرن العشرين أثناء عمله في مؤسسة RAND. وكتب لاحقًا أنه اختار كلمة programming بمعناها القديم، أي التخطيط، واختار dynamic لأنها تبدو مثيرة للإعجاب ويصعب الاعتراض عليها. والطريقة نفسها، أي حل المسألة من خلال إجابات نسخ أصغر منها، تعمل اليوم في المدققات الإملائية ومخططات المسارات ومقارنة الحمض النووي (DNA).

ريتشارد بيلمان عام 1962، بعدسة ألفريد آيزنستات. أطلق اسم البرمجة الديناميكية في أوائل خمسينيات القرن العشرين حين كان يعمل في مؤسسة راند.
ريتشارد بيلمان عام 1962، بعدسة ألفريد آيزنستات. أطلق اسم البرمجة الديناميكية في أوائل خمسينيات القرن العشرين حين كان يعمل في مؤسسة راند.

استكشفها بنفسك

افتح التطبيق واضغط «خطوة». في الطريقة من الأسفل إلى الأعلى، الخلية البرتقالية هي التي تُملأ، والخليتان الزرقاوان هما الحدان اللذان تجمعهما. انتقل إلى الطريقة من الأعلى إلى الأسفل وشاهد مكدس الاستدعاءات أسفل الجدول ينمو حتى 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 من الأعداد، لكن كل حد جديد لا يحتاج إلا إلى الحدين السابقين له، لذا فإن حلقة تحتفظ بعددين فقط تؤدي العمل نفسه بذاكرة ثابتة. والاحتفاظ بالجدول كله مفيد عندما تريد جميع الحدود، أو لترى كيف تعمل الطريقة.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب فيبوناتشي بالبرمجة الديناميكية