البرمجة الديناميكية

في مجال التحسين الرياضي، تشير البرمجة الديناميكية عادةً إلى تبسيط القرار عن طريق تقسيمه إلى سلسلة من خطوات القرار عبر الزمن. ^{[ 2 ]}

يتم ذلك عن طريق تحديد سلسلة من دوال القيمة V ₁ ، V ₂ ، ... ، V _n مع أخذ y كوسيط يمثل حالة النظام في الأوقات i من 1 إلى n .

تعريف V _n ( y ) هو القيمة التي تم الحصول عليها في الحالة y في آخر وقت n .

يمكن إيجاد قيم 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} لتلك الحالات.

وأخيرًا، _تمثل V1 في الحالة الابتدائية للنظام قيمة الحل الأمثل. ويمكن استعادة القيم المثلى لمتغيرات القرار، واحدًا تلو الآخر، من خلال تتبع الحسابات التي تم إجراؤها مسبقًا.

في نظرية التحكم ، تتمثل إحدى المشكلات النموذجية في إيجاد تحكم مقبول${\displaystyle \mathbf {u} ^{\ast }}$مما يتسبب في النظام${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$اتباع مسار مقبول${\displaystyle \mathbf {x} ^{\ast }}$على فترة زمنية مستمرة${\displaystyle t_{0}\leq t\leq t_{1}}$الذي يقلل دالة التكلفة

${\displaystyle 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}$

يتمثل حل هذه المشكلة في قانون أو سياسة تحكم مثلى${\displaystyle \mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)}$، مما ينتج عنه مسار مثالي${\displaystyle \mathbf {x} ^{\ast }}$ووظيفة تكلفة الوصول${\displaystyle J^{\ast }}$ويخضع هذا الأخير للمعادلة الأساسية للبرمجة الديناميكية:

$// {u} (ر)،t\يمين)\يمين\}}$

معادلة تفاضلية جزئية تُعرف باسم معادلة هاميلتون-جاكوبي-بيلمان ، والتي${\displaystyle 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}}}$و${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$يجد المرء أن التقليل من${\displaystyle \mathbf {u} }$من ناحية${\displaystyle t}$،${\displaystyle \mathbf {x} }$والدالة المجهولة${\displaystyle J_{x}^{\ast }}$ثم يعوض النتيجة في معادلة هاميلتون-جاكوبي-بيلمان للحصول على المعادلة التفاضلية الجزئية التي يجب حلها مع شرط الحدود${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$[ ^{3 ] من الناحية} العملية، يتطلب هذا بشكل عام تقنيات عددية لبعض التقريب المنفصل لعلاقة التحسين الدقيقة.

بدلاً من ذلك، يمكن تقريب العملية المستمرة بنظام منفصل، مما يؤدي إلى علاقة تكرارية مماثلة لمعادلة هاميلتون-جاكوبي-بيلمان:

$// }\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{nk},\mathbf {u} _{nk}\right)\right)\right\}}$

في${\displaystyle k}$المرحلة الثالثة من${\displaystyle n}$فترات زمنية منفصلة متساوية التباعد، وحيث${\displaystyle {\hat {f}}}$و${\displaystyle {\hat {\mathbf {g} }}}$تشير إلى تقريبات منفصلة لـ${\displaystyle f}$و${\displaystyle \mathbf {g} }$تُعرف هذه المعادلة الوظيفية باسم معادلة بيلمان ، والتي يمكن حلها للحصول على حل دقيق للتقريب المتقطع لمعادلة التحسين. ^{[ 4 ]}

هناك سمتان أساسيتان يجب أن تتوافرا في أي مشكلة حتى يكون البرمجة الديناميكية قابلة للتطبيق: البنية الفرعية المثلى والمشكلات الفرعية المتداخلة . إذا أمكن حل مشكلة ما بدمج الحلول المثلى لمشكلات فرعية غير متداخلة ، تُسمى هذه الاستراتيجية " فرق تسد ". ^{[ 1 ]} ولهذا السبب، لا تُصنف خوارزميتا فرز الدمج والفرز السريع ضمن مسائل البرمجة الديناميكية.

تعني البنية الفرعية المثلى إمكانية الحصول على حل لمسألة تحسين معينة من خلال دمج الحلول المثلى لمسائلها الفرعية. وعادةً ما تُوصف هذه البنى الفرعية المثلى باستخدام الاستدعاء الذاتي . على سبيل المثال، إذا كان لدينا رسم بياني G=(V,E) ، فإن أقصر مسار p من الرأس u إلى الرأس v يُظهر بنية فرعية مثلى: خذ أي رأس وسيط w على هذا المسار p . إذا كان p هو أقصر مسار بالفعل، فيمكن تقسيمه إلى مسارين فرعيين p1 من u إلى _w و p2 من w إلى v، _بحيث يكون هذان المساران بدورهما أقصر مسارين بين الرأسين المتناظرين (باستخدام حجة القص واللصق البسيطة الموضحة في مقدمة الخوارزميات ). وبالتالي، يمكن صياغة حل إيجاد أقصر المسارات بسهولة بطريقة استدعائية، وهو ما تفعله خوارزمية بيلمان-فورد أو خوارزمية فلويد-وارشال .

يعني تداخل المسائل الفرعية أن فضاء المسائل الفرعية يجب أن يكون صغيرًا، أي أن أي خوارزمية تكرارية لحل المسألة يجب أن تحل نفس المسائل الفرعية مرارًا وتكرارًا، بدلًا من توليد مسائل فرعية جديدة. على سبيل المثال، لننظر إلى الصيغة التكرارية لتوليد متتالية فيبوناتشي: F _{_i} = F_{_{i - 1}} + F _{_{i - 2}} ، مع حالة الأساس F _₁  = F _₂ = 1. عندئذٍ F _₄₃ = F _₄₂ + F _₄₁ ، و F _₄₂ = F _₄₁ + F _₄₀. الآن، يتم حل F _₄₁ في الأشجار الفرعية التكرارية لكل من F _₄₃ و F _₄₂ . على الرغم من أن العدد الإجمالي للمسائل الفرعية صغير فعليًا (43 مسألة فقط)، إلا أننا ننتهي بحل نفس المسائل مرارًا وتكرارًا إذا اعتمدنا حلًا تكراريًا بسيطًا كهذا. تأخذ البرمجة الديناميكية هذه الحقيقة في الحسبان، وتحل كل مسألة فرعية مرة واحدة فقط.         

يمكن تحقيق ذلك بإحدى الطريقتين التاليتين: ^{[ 5 ]}

• النهج التنازلي : هذا النهج هو النتيجة المباشرة للصياغة التكرارية لأي مسألة. إذا أمكن صياغة حل أي مسألة بشكل تكراري باستخدام حلول مسائلها الفرعية، وكانت هذه المسائل الفرعية متداخلة، فيمكن بسهولة تخزين حلولها في جدول (غالبًا ما يكون مصفوفة أو جدول تجزئة عمليًا). عند محاولة حل مسألة فرعية جديدة، نتحقق أولًا من الجدول لمعرفة ما إذا كانت قد حُلت بالفعل. إذا كان الحل مسجلًا، يمكننا استخدامه مباشرةً، وإلا نحل المسألة الفرعية ونضيف حلها إلى الجدول.
• النهج التصاعدي : بعد صياغة حل المسألة بشكل تكراري بدلالة مسائلها الفرعية، يمكننا محاولة إعادة صياغة المسألة بطريقة تصاعدية: نبدأ بحل المسائل الفرعية ثم نستخدم حلولها للبناء عليها والوصول إلى حلول للمسائل الفرعية الأكبر. ويتم ذلك عادةً في شكل جدولي من خلال توليد حلول متكررة لمسائل فرعية أكبر فأكبر باستخدام حلول المسائل الفرعية الأصغر. على سبيل المثال، إذا كنا نعرف قيم _F41 و _F40 ، فيمكننا حسابقيمة F42 مباشرةً _.

تستطيع بعض لغات البرمجة تخزين نتيجة استدعاء دالة تلقائيًا باستخدام مجموعة محددة من الوسائط، وذلك لتسريع عملية التقييم بالاسم (وتُعرف هذه الآلية بالتقييم عند الحاجة ). وتتيح بعض اللغات هذه الميزة بشكل قابل للنقل (مثل Scheme و Common Lisp و Perl و D ). كما تتضمن بعض اللغات خاصية التخزين التلقائي ، مثل Prolog و J ، التي تدعم التخزين باستخدام الظرف M. ^{[ 6 ]} . على أي حال، لا يُمكن تطبيق هذه الخاصية إلا على الدوال الشفافة مرجعيًا . ويُعدّ التخزين أيضًا نمط تصميم سهل الاستخدام في اللغات التي تعتمد على إعادة كتابة المصطلحات، مثل Wolfram Language .

تُستخدم البرمجة الديناميكية على نطاق واسع في المعلوماتية الحيوية لمهام مثل محاذاة التسلسلات ، وطَيّ البروتينات ، والتنبؤ ببنية الحمض النووي الريبي (RNA)، وارتباط البروتين بالحمض النووي (DNA). طُوّرت أولى خوارزميات البرمجة الديناميكية لارتباط البروتين بالحمض النووي في سبعينيات القرن الماضي بشكل مستقل من قِبَل تشارلز ديليسي في الولايات المتحدة ^{[ 7 ]} ، وجورجي جورسكي وألكسندر زاسيداتيليف في الاتحاد السوفيتي ^{[ 8 ]} . وقد اكتسبت هذه الخوارزميات مؤخرًا شعبية كبيرة في المعلوماتية الحيوية وعلم الأحياء الحاسوبي ، لا سيما في دراسات تحديد مواقع النيوكليوسومات وارتباط عوامل النسخ .

من منظور البرمجة الديناميكية، تُعد خوارزمية ديكسترا لمسألة أقصر مسار مخطط تقريبي متتابع يحل معادلة الدالة للبرمجة الديناميكية لمسألة أقصر مسار باستخدام طريقة الوصول . ^{[ 9 ] [ 10 ] [ 11 ]}

في الواقع، شرح ديكسترا للمنطق الكامن وراء الخوارزمية، ^{[ 12 ]} وهو

المسألة 2. أوجد المسار ذو أقصر طول إجمالي بين عقدتين معطيتين${\displaystyle P}$و${\displaystyle Q}$.

نستفيد من حقيقة أنه، إذا${\displaystyle R}$هي عقدة على المسار الأدنى من${\displaystyle P}$ل${\displaystyle Q}$إن معرفة الأخير تستلزم معرفة المسار الأدنى من${\displaystyle P}$ل${\displaystyle R}$.

هو إعادة صياغة لمبدأ بيلمان الشهير للأمثلية في سياق مشكلة أقصر مسار .

يُحسّن استخدام البرمجة الديناميكية في حساب العنصر النوني من متتالية فيبوناتشي الأداء بشكل كبير. إليك تطبيقًا بسيطًا، يعتمد مباشرةً على التعريف الرياضي:

دالة fib(n) إذا كان n <= 1 تُرجع n تُرجع 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المحسوبة مسبقًا بنتيجتها، ونقوم بتعديل دالتنا لاستخدامها وتحديثها. تتطلب الدالة الناتجة وقتًا قدره O ( n ) فقط بدلًا من وقت أسي (لكنها تتطلب مساحة قدرها O( n )).

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) أعد m[n]

تُسمى هذه التقنية لحفظ القيم التي تم حسابها بالفعل بالتخزين المؤقت ؛ وهذا هو النهج من أعلى إلى أسفل، حيث نقوم أولاً بتقسيم المشكلة إلى مشاكل فرعية ثم نقوم بحساب القيم وتخزينها.

في المنهج التصاعدي ، نحسب القيم الأصغر fibأولاً، ثم نبني القيم الأكبر انطلاقاً منها. يستخدم هذا الأسلوب أيضاً زمناً قدره O( n ) لأنه يحتوي على حلقة تكرارية تتكرر n − 1 مرة، ولكنه لا يتطلب سوى مساحة ثابتة (O(1))، على عكس المنهج التنازلي الذي يتطلب مساحة O( n ) لتخزين الخريطة.

دالة fib(n) إذا كان n = 0، تُرجع 0، وإلا تُرجع 0. متغير previousFib := 0، ​​متغير currentFib := 1. تُكرر هذه العملية n - 1 مرة // يتم تخطي الحلقة إذا كان n = 1. متغير newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib إرجاع فيبوناتشي الحالية

في كلا المثالين، نقوم بالحساب fib(2)مرة واحدة فقط، ثم نستخدمه لحساب كل من fib(4)و fib(3)، بدلاً من حسابه في كل مرة يتم فيها تقييم أي منهما.

لنفترض مسألة إسناد قيم، إما صفر أو واحد، إلى مواضع مصفوفة من الرتبة n × n ، حيث n عدد زوجي، بحيث يحتوي كل صف وكل عمود على n /2 من الأصفار و n /2 من الواحدات بالضبط. نسأل: كم عدد الإسنادات المختلفة الممكنة لقيمة n معينة ؟ على سبيل المثال، عندما n = 4 ، يكون هناك خمسة حلول ممكنة.

${\displaystyle {\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}}.}$

هناك ثلاثة مناهج محتملة على الأقل: القوة الغاشمة ، والتراجع ، والبرمجة الديناميكية.

تعتمد طريقة البحث الشامل على فحص جميع قيم الأصفار والآحاد، وحساب القيم التي تحتوي على صفوف وأعمدة متوازنة ( نصف عدد الأصفار ونصف عدد الآحاد ).${\displaystyle 2^{n^{2}}}$المهام المحتملة و${\displaystyle {\tbinom {n}{n/2}}^{n}}$في حالة التخصيصات المعقولة، فإن هذه الاستراتيجية غير عملية بالنسبة للقيم الكبيرة بشكل تعسفي لـ${\displaystyle n}$.

تعتمد طريقة التراجع في هذه المسألة على اختيار ترتيب معين لعناصر المصفوفة، ثم وضع القيم 1 أو 0 بشكل متكرر، مع التحقق من أن مجموع عدد العناصر غير المُخصصة وعدد القيم 1 أو 0 في كل صف وعمود يساوي على الأقل n /2 . ورغم أن هذه الطريقة أكثر تعقيدًا من طريقة البحث الشامل، إلا أنها ستزور كل حل مرة واحدة، مما يجعلها غير عملية عندما يكون n أكبر من ستة، لأن عدد الحلول يكون كبيرًا بالفعل.116 963 796 250 لـ n  =  8، كما سنرى.

تُمكّن البرمجة الديناميكية من حساب عدد الحلول دون الحاجة إلى زيارتها جميعًا. تخيّل التراجع عن قيم الصف الأول - ما المعلومات التي نحتاجها حول الصفوف المتبقية، لكي نتمكن من حساب الحلول التي تم الحصول عليها لكل قيمة من قيم الصف الأول بدقة؟ لنفترض وجود لوحات k × n ، حيث 1 ≤ k ≤ n ، وتحتوي صفوفها k على${\displaystyle n/2}$أصفار و${\displaystyle n/2}$تُطبَّق عملية التخزين المؤقت على الدالة f، التي تُحوِّل متجهاتٍ من n زوجًا من الأعداد الصحيحة إلى عدد الألواح (الحلول) الممكنة. يوجد زوج واحد لكل عمود، ويشير مُكوِّناه على التوالي إلى عدد الأصفار والآحاد التي لم تُضَف بعد إلى ذلك العمود. نبحث عن قيمة${\displaystyle f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))}$( عدد n من الوسائط أو متجه واحد مكون من n عنصرًا). تتضمن عملية إنشاء المسألة الفرعية التكرار على كل واحد من ${\displaystyle {\tbinom {n}{n/2}}}$يتم تحديد القيم الممكنة للصف العلوي من اللوحة، ثم يتم المرور على كل عمود، وطرح واحد من العنصر المناسب في الزوج الخاص بذلك العمود، وذلك بناءً على ما إذا كانت القيمة المُحددة للصف العلوي تحتوي على صفر أو واحد في ذلك الموضع. إذا كانت أي من النتائج سالبة، فإن القيمة غير صالحة ولا تُساهم في مجموعة الحلول (يتوقف التكرار). وإلا، يتم تحديد قيمة للصف العلوي من اللوحة k × n ، ثم يتم حساب عدد الحلول للوحة المتبقية ( k - 1) × n بشكل تكراري ، وذلك بجمع أعداد الحلول لكل قيمة مقبولة للصف العلوي، وإرجاع المجموع الذي يتم تخزينه مؤقتًا. الحالة الأساسية هي المسألة الفرعية البسيطة، والتي تحدث للوحة 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)) 

عدد الحلول (التسلسل A058527 في OEIS ) هو

1، 2، 90،297 200 ،116 963 796 250 ،6 736 218 287 430 460 752 ، ...

يمكن العثور على روابط لتطبيق MAPLE لنهج البرمجة الديناميكية ضمن الروابط الخارجية .

لنفترض رقعة شطرنج مكونة من n × n مربعًا ودالة تكلفة c(i, j)تُعيد التكلفة المرتبطة بكل مربع (i,j)( iحيث n هو الصف، jوn هو العمود). على سبيل المثال (على رقعة شطرنج 5 × 5)،

هكذاc(1, 3) = 5

لنفترض أن هناك قطعة شطرنج يمكنها أن تبدأ من أي مربع في الصف الأول (أي الصف الأول)، وتريد معرفة أقصر مسار (مجموع أقل التكاليف عند كل صف تمت زيارته) للوصول إلى الصف الأخير؛ بافتراض أن قطعة الشطرنج لا يمكنها التحرك إلا قطريًا إلى اليسار للأمام، أو قطريًا إلى اليمين للأمام، أو بشكل مستقيم للأمام. أي أن قطعة الشطرنج في الصف الأول (1,3)يمكنها التحرك إلى أي من المربعات (2,2)الثلاثة .(2,3)(2,4)

تُظهر هذه المسألة بنيةً فرعيةً مثلى . أي أن حل المسألة بأكملها يعتمد على حلول المسائل الفرعية. لنُعرّف دالة q(i, j)على النحو التالي:

q ( ​​i , j ) = الحد الأدنى للتكلفة للوصول إلى المربع ( i , j ).

بدءًا من الرتبة الأولى nوصولًا إلى الرتبة الثانية 1، نحسب قيمة هذه الدالة لجميع المربعات في كل رتبة متتالية. باختيار المربع الذي يحمل أقل قيمة في كل رتبة، نحصل على أقصر مسار بين الرتبة الأولى nوالرتبة الثانية 1.

الدالة q(i, j)تساوي أقل تكلفة للوصول إلى أي من المربعات الثلاثة الموجودة أسفلها (لأنها المربعات الوحيدة التي يمكن الوصول إليها) زائد c(i, j). على سبيل المثال:

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

والآن، دعونا نحدد ذلك q(i, j)بعبارات أكثر عمومية:

${\displaystyle 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)nc(i, j)min()

دالة minCost(i, j) إذا كان j < 1 أو j > n تُرجع قيمة لانهائية ، وإلا إذا كان i = 1 تُرجع c(i, j)، وإلا تُرجع القيمة الدنيا ( 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، ثم سلف ذلك المربع، ثم سلف ذلك المربع، وهكذا بشكل متكرر، حتى نصل إلى مربع البداية. انظر إلى الشفرة الزائفة التالية:

دالة حساب أقصر مسار للمصفوفات () لـ x من 1 إلى n q[1, x] := c(1, x) لكل y من 1 إلى n q[y, 0] := ∞ q[y, n + 1] := ∞ لكل y من 2 إلى n، ولكل x من 1 إلى n m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x] := m + c(y, x) إذا كان m = q[y-1, x-1] p[y, x] := -1 وإلا إذا كان m = q[y-1, x] p[y, x] := 0 وإلا فإن p[y, x] := 1

أما الباقي فهو مسألة بسيطة تتمثل في إيجاد الحد الأدنى وطباعته.

دالة حساب أقصر مسار computeShortestPathArrays() minIndex := 1 min := q[n, 1] لكل i من 2 إلى n إذا كان q[n, i] < min minIndex := i min := q[n, i] printpath(n, minIndex)

دالة printPath(y, x) تطبع (x) تطبع (" < -") إذا كانت y = 2 تطبع (x + p[y, x]) وإلا تطبع printPath(y-1, x + p[y, x])

في علم الوراثة ، يُعدّ محاذاة التسلسل تطبيقًا هامًا حيث تُعدّ البرمجة الديناميكية أساسية. ^{[ 13 ]} عادةً، تتلخص المشكلة في تحويل تسلسل إلى آخر باستخدام عمليات التحرير التي تستبدل أو تُضيف أو تُزيل عنصرًا. لكل عملية تكلفة مُرتبطة بها، والهدف هو إيجاد تسلسل التحرير ذي أقل تكلفة إجمالية .

يمكن صياغة المشكلة بشكل طبيعي على أنها تكرار، حيث يتم تعديل التسلسل 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) عن طريق جمع تكلفة العمليات ذات الصلة مع تكلفة الخلايا المجاورة لها، ثم اختيار القيمة المثلى.

توجد متغيرات مختلفة، انظر خوارزمية سميث-واترمان وخوارزمية نيدلمان-وونش .

برج هانوي أو أبراج هانوي هي لعبة أو لغز رياضي . تتكون من ثلاثة قضبان، وعدد من الأقراص بأحجام مختلفة يمكن انزلاقها على أي قضيب. يبدأ اللغز بوضع الأقراص في كومة مرتبة بشكل منظم تصاعديًا حسب الحجم على أحد القضبان، بحيث يكون أصغرها في الأعلى، مما يشكل شكلًا مخروطيًا.

الهدف من اللغز هو نقل المجموعة بأكملها إلى قضيب آخر، مع مراعاة القواعد التالية:

• لا يمكن نقل سوى قرص واحد في كل مرة.
• تتكون كل حركة من أخذ القرص العلوي من أحد القضبان وإدخاله على قضيب آخر، فوق الأقراص الأخرى التي قد تكون موجودة بالفعل على ذلك القضيب.
• لا يجوز وضع أي قرص فوق قرص أصغر منه.

يتكون حل البرمجة الديناميكية من حل المعادلة الوظيفية

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" (لم يتبق سوى قرص واحد).

عدد الحركات المطلوبة لهذا الحل هو ²ⁿ - 1. إذا كان الهدف هو زيادة عدد الحركات إلى أقصى حد (دون تكرار)، فإن معادلة البرمجة الديناميكية تصبح أكثر تعقيدًا بعض الشيء، ويتطلب الأمر 3n - 1 ^حركة . ^{[ 14 ]}    

تتعلق إحدى الألغاز الشهيرة بإسقاط بيض من مبنى لتحديد الارتفاع الذي يبدأ عنده البيض بالانكسار. فيما يلي وصف يتضمن بيضتين (N=2) ومبنى مكون من 36 طابقًا (H=36): ^{[ 15 ]}

لنفترض أننا نريد معرفة أي الطوابق في مبنى مكون من 36 طابقًا آمنة لإسقاط البيض منها، وأيها سيؤدي إلى كسر البيض عند الهبوط (باستخدام المصطلحات الإنجليزية الأمريكية ، حيث يكون الطابق الأول هو مستوى الأرض). نفترض بعض الافتراضات:

• يمكن استخدام البيضة التي تنجو من السقوط مرة أخرى.
• يجب التخلص من البيضة المكسورة.
• يكون تأثير السقوط هو نفسه بالنسبة لجميع البيض.
• إذا انكسرت البيضة عند سقوطها، فإنها ستنكسر أيضاً إذا سقطت من نافذة أعلى.
• إذا نجت البيضة من السقوط، فستنجو من سقوط أقصر.
• لا يُستبعد أن تتسبب نوافذ الطابق الأول في كسر البيض، كما لا يُستبعد أن يتمكن البيض من البقاء على قيد الحياة من خلال نوافذ الطابق السادس والثلاثين.

إذا توفرت بيضة واحدة فقط، وأردنا التأكد من الحصول على النتيجة الصحيحة، فلا يمكن إجراء التجربة إلا بطريقة واحدة. أسقط البيضة من نافذة الطابق الأول؛ إذا نجت، أسقطها من نافذة الطابق الثاني. استمر في الصعود حتى تنكسر. في أسوأ الأحوال، قد تتطلب هذه الطريقة 36 محاولة. لنفترض أن لدينا بيضتين. ما هو أقل عدد من محاولات إسقاط البيض التي تضمن نجاح التجربة في جميع الحالات؟

لاستنتاج معادلة وظيفية للبرمجة الديناميكية لهذا اللغز، لنفترض أن حالة نموذج البرمجة الديناميكية هي زوج s = (n,k)، حيث

n = عدد بيض الاختبار المتاح، n = 0، 1، 2، 3، ...، N − 1.  

k = عدد الطوابق (المتتالية) التي لم يتم اختبارها بعد، k = 0، 1، 2، ...، H − 1.  

على سبيل المثال، تشير s = (2,6) إلى توفر بيضتين للاختبار، وأن ستة طوابق (متتالية) لم تُختبر بعد. الحالة الابتدائية للعملية هي s = ( N , H )، حيث N يُمثل عدد بيض الاختبار المتاح عند بدء التجربة. تنتهي العملية إما عند نفاد بيض الاختبار ( n = 0) أو عند k = 0، أيهما يحدث أولاً. إذا انتهت العملية عند الحالة s = (0, k ) وكان k  >  0، فإن الاختبار يكون قد فشل.

والآن، لنبدأ

W ( n , k ) = الحد الأدنى لعدد التجارب المطلوبة لتحديد قيمة الحد الأدنى الحرج في أسوأ سيناريو مع الأخذ في الاعتبار أن العملية في الحالة s = ( n , k ).

ثم يمكن إثبات أن ^{[ 16 ]}

W ( n , k ) = 1 + min{max( W ( n − 1, x − 1), W ( n , k − x )): x = 1, 2, ..., k }

حيث W ( n ,0) = 0 لجميع قيم n  >  0 و W (1, k ) = k لجميع قيم k . من السهل حل هذه المعادلة تكراريًا عن طريق زيادة قيم n و k بشكل منهجي .  

يُعدّ ضرب سلسلة المصفوفات مثالًا معروفًا يُبيّن فائدة البرمجة الديناميكية. فعلى سبيل المثال، غالبًا ما تتطلب التطبيقات الهندسية ضرب سلسلة من المصفوفات. وليس من المستغرب وجود مصفوفات ذات أبعاد كبيرة، مثل 100×100. لذا، فإن مهمتنا هي ضرب المصفوفات .${\displaystyle A_{1},A_{2},....A_{n}}$عملية ضرب المصفوفات ليست تبديلية، بل تجميعية؛ ولا يمكننا ضرب أكثر من مصفوفتين في الوقت نفسه. لذا ، يمكننا ضرب هذه السلسلة من المصفوفات بطرق عديدة ومختلفة، على سبيل المثال:

( ₍ A1 _× A2 ₎ × A3 ₎ × ... أن

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

( A1 _× A2 ₎ × ( A3 _× ... An ₎​

وهكذا دواليك. توجد طرق عديدة لضرب هذه السلسلة من المصفوفات. جميعها تُنتج نفس النتيجة النهائية، إلا أن وقت الحساب يختلف باختلاف المصفوفات المراد ضربها. فإذا كانت أبعاد المصفوفة 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. Ax(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].

الصيغة هي:

إذا كان i = j، فإن m[i,j] = 0. إذا كان i < j، فإن m[i,j] = القيمة الصغرى لجميع القيم الممكنة لـ k (m[i,k] + m[k+1,j] +${\displaystyle p_{i-1}*p_{k}*p_{j}}$)

حيث تتراوح قيمة k من i إلى j − 1.  

• ⁠${\displaystyle p_{i-1}}$يمثل بُعد الصف للمصفوفة i،
• ⁠${\displaystyle p_{k}}$يمثل بُعد العمود للمصفوفة k،
• ⁠${\displaystyle p_{j}}$يمثل بُعد العمود للمصفوفة j.

يمكن ترميز هذه الصيغة كما هو موضح أدناه، حيث يمثل مُدخل "chain" سلسلة المصفوفات، أي${\displaystyle A_{1},A_{2},...A_{n}}$⁠ :

دالة OptimalMatrixChainParenthesis(chain) n = طول (السلسلة) لـ i = 1، n m[i,i] = 0 // بما أنه لا يتطلب أي عمليات حسابية لضرب مصفوفة واحدة، وذلك لـ len = 2 و n، ولـ i = 1 و n - len + 1 j = i + len -1 m[i,j] = ∞ // بحيث يتم تحديث الحساب الأول لـ k = i, j-1 q = m[i, k] + m[k+1, j] +${\displaystyle p_{i-1}*p_{k}*p_{j}}$إذا كان q < m[i, j] // الترتيب الجديد للأقواس أفضل من السابق m[i, j] = q // تحديث s[i, j] = k // تسجيل قيمة k التي سيتم التقسيم بناءً عليها، أي مكان وضع الأقواس

حتى الآن، قمنا بحساب قيم جميع القيم الممكنة لـ m [ i , j ] ، وهو الحد الأدنى لعدد العمليات الحسابية اللازمة لضرب سلسلة من المصفوفة i إلى المصفوفة j ، وسجلنا "نقطة الفصل" المقابلة s [ i , j ] . على سبيل المثال، إذا كنا نضرب السلسلة A1 _× A2 × _A3 × A4 _، وتبين أن m [1,3] = 100 و s [1,3] = 2 ، فهذا يعني أن الموضع الأمثل للأقواس للمصفوفات من 1 إلى ₃ هو${\displaystyle (A_{1}\times A_{2})\times A_{3}}$وضرب تلك المصفوفات سيتطلب 100 عملية حسابية قياسية.

ستُنتج هذه الخوارزمية جدولين m [, ] و s [, ] يحتويان على مدخلات لجميع القيم الممكنة لـ i و j. الحل النهائي للسلسلة بأكملها هو m[1, n]، مع تقسيم مُقابل عند s[1, n]. سيكون فكّ الحل عملية تكرارية، تبدأ من الأعلى وتستمر حتى نصل إلى الحالة الأساسية، أي ضرب المصفوفات المفردة.

لذا، تتمثل الخطوة التالية في تقسيم السلسلة فعلياً، أي وضع الأقواس في مكانها الأمثل. ولتحقيق هذا الغرض، يمكننا استخدام الخوارزمية التالية:

دالة PrintOptimalParenthesis(s, i, j) إذا كان i = j اطبع "A"i آخر مطبعة "(" PrintOptimalParenthesis(s, i, s[i, j]) PrintOptimalParenthesis(s, s[i, j] + 1, j) مطبعة ")"

بالطبع، هذه الخوارزمية غير مفيدة للضرب الفعلي. إنها مجرد طريقة سهلة الاستخدام لمعرفة شكل النتيجة.

لضرب المصفوفات فعلياً باستخدام التقسيمات المناسبة، نحتاج إلى الخوارزمية التالية:

دالة MatrixChainMultiply ( سلسلة من 1 إلى n ) // تُعيد المصفوفة النهائية، أي A1×A2×...×An OptimalMatrixChainParenthesis ( سلسلة من 1 إلى n ) // ستُنتج هذه الدالة "جداول" s[.] و m[.] OptimalMatrixMultiplication ( s , سلسلة من 1 إلى n ) // تُجري عملية الضرب فعليًادالة OptimalMatrixMultiplication ( s , i , j ) // تُعيد نتيجة ضرب سلسلة من المصفوفات من Ai إلى Aj بالطريقة المثلى إذا كان i < j // استمر في تقسيم السلسلة وضرب المصفوفات في الجانبين الأيسر والأيمن 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 // المصفوفة في الموضع i else print "خطأ، يجب أن يكون i <= j صحيحًا"دالة MatrixMultiply ( A , B ) // دالة تضرب مصفوفتين إذا كانت أعمدة ( A ) = صفوف ( B ) for i = 1 , صفوف ( A ) for j = 1 , أعمدة ( B ) C [ i , j ] = 0 for k = 1 , أعمدة ( A ) C [ i , j ] = C [ i , j ] + A [ i , k ] * B [ k , j ] return C else print "خطأ، أبعاد غير متوافقة."