dynamic programming

) البرمجة الديناميكية(Dynamic programming)

هي طريقة لتصميم الخوارزميات تستعمل عندما يكون ممكنا اعتبار المسالة نتيجة لتعاقب قرارات, حيث تستخدم البرمجة الديناميكية مبدأ الامثلية (principle of optimality) للوصول الى تعاقب القرارات الامثل. اذ ينص هذا المبدأ عل ان تعاقب القرارت الامثل لديه الخاصية التالية:-
" مهما تكن الحالة الابتدائية والقرارالمتخذ فيها يجب ان تكون القرارات الباقية تعاقب القرار الامثل بالاستناد الى الحالة الناتجة من القرار الاول". ان التطبيق التداخلي لهذا المبدأ ينتج علاقات تداخل، حيث تقوم خوارزميات البرمجة الديناميكية بحل هذه العلاقات للحصول على حل لمثال مسألة معين.
الفرق الجوهري بين طريقة الطماع ( قرارات خطوة خطوة معتمدة على معلومات محلية) والبرمجة الديناميكية ( قرارات خطوة خطوة معتمدة على معلومات عالمية) هو انه في الاولى يولد تعاقب قرارت واحد فقط بينما في الثانية يمكن ان تولد تعاقبات قرارات كثيرة لكن التعاقبات الحاوية على تعاقبات جزئية غير مثلى لا يمكن ان تكون مثلى ولهذا لا تولد. لذلك وبالرغم من ان العدد الكلي لتعاقبات القرار المختلفة هو دالة اسية في عدد القرارات ( اذا كان هناك d من الخيارات لكل قرار من القرارات التي عددها n فان هناك dn تعاقب قرار ممكن) فأن خوارزميات البرمجة الديناميكية عادة لديها تعقيدات متعددة حدود. بالاضافة الى ذلك توجد ميزة اخرى لطريقة البرمجة الديناميكية هي الاحتفاظ بالحلول المثلى للمسائل الجزئية لتجنب اعادة حساب قيمها.

مسألة المخطط متعدد المراحل (Multistage graph problem)

المخطط متعدد المراحل هو مخطط موجه فيه تقسم العقد الى k?2 مجموعة منفصلة vi حيث 1?i?k المجموعتان v1 و vk تكونان بحيث . افترض ان s هي عقدة البداية في v1 و t هي عقدة النهاية في vk وافترض ان c[i,j] تمثل كلفة الحافة بين i و j (<i, j>). كلفة المسار من s الى t هي مجموع كلف الحواف على المسار.
مسألة المخطط متعدد المراحل هي ايجاد مسار اقل كلفة من s الى t. كل مجموعة vi تمثل مرحلة في المخطط وكل مسار من s الى t يبدأ بالمرحلة 1وينتهي بالمرحلة k. الشكل التالي يمثل مخطط متعدد مراحل ذي خمس مراحل.


















صياغة البرمجة الديناميكية لمسألة مخطط ذي k مرحلة ( طريقة تصاعدية Forward approach)

نلاحظ ان كل مسار من s الى t يكون نتيجة لتعاقب k-2 قرار، كل قرار i يشمل تحديد اي العقد vi+1 حيث 1?i?k-2 تكون على المسار. افترض ان p(i,j) هو المسار الاقل كلفة من العقدة j في المجموعة vi الى العقدة t وان cost(i,j) هو كلفة ذلك المسار، وباستعمال الطريقة التصاعدية (تحل تناقصيا).

وحيث

فأن العلاقة (1) تحل للحالة cost(1,s) بحساب اولا

ثم

.
.
.

وأخيرا

وباعتبار المخطط السابق نحصل على:-
cost(3,6) = min{6+cost(4,9), 5+cost(4,10)} = 7
cost(3,7) = min{4+cost(4,9), 3+cost(4,10)} = 5
cost(3,8) = min{5+cost(4,10), 6+cost(4,11)} = 7
cost(2,2) = min{4+cost(3,6), 2+cost(3,7), 1+cost(3,8)} = 7
cost(2,3) = min{2+cost(3,6), 7+cost(3,7)} = 9
cost(2,4) = min{11+cost(3,8)} = 18
cost(2,5) = min{11+cost(3,7), 8+cost(3,8)} = 15
cost(1,1) = min{9+cost(2,2), 7+cost(2,3), 3+cost(2,4), 2+cost(2,5)} = 16

لهذا فان المسار الاقل كلفة من s الى t له الكلفة 16 ولتحديد المسار نسجل القرارات المتخذة في كل حالة(عقدة). افترض D[i,j] هي قيمة r التي تصغر فنحصل على

D[3,6]=10 D[3,7]=10 D[3,8]=10 D[2,2]=7
D[2,3]=6 D[2,4]=8 D[2,5]=8 D[1,1]=2
وباعتبار المسار الاقل كلفة هو
S=1 v2 v3 … vk-1 t=12

v2=D[1,1]=2 , v3=D[2,D[1,1]] = 7 , v4=D[3,D[2,D[1,1]]] = 10

اذن المسار الامثل هو
1, 2, 7, 10, 12