Algorithms/Dynamic Programming

يمكن تعريف البرمجة الديناميكية بأنّها عملية تحسين تُجرى على العمليات التعاودية، بمعنى أنّه يمكن استخدام البرمجة الديناميكية في أيّ مكان تظهر فيها استدعاءات تعاودية متكررة تستخدم المدخلات عينها. وتتلخّص عملية التحسين في تخزين النتائج التي نحصل عليها من المسائل الفرعية وبهذا تنتفي الحاجة إلى إعادة حساب تلك النتائج في وقت لاحق. تختزل عملية التحسين البسيطة هذه التعقيد الزمني للخوارزميات من تعقيد زمني أسّي exponential إلى متعدد الحدود polynomail.

فعلى سبيل المثال يبلغ التعقيد الزمني لعملية حساب أعداد فيبوناتشي بطريقة تعاودية مقدارًا أسيًّا ولكن يمكن تحسين هذه الطريقة بتخزين حلول المسائل الفرعية في الخوارزمية ليُختزل التعقيد الزمني بذلك إلى مقدار خطّي.

خصائص المسائل التي يمكن حلها باستخدام البرمجة الديناميكية

تعدّ البرمجية الديناميكية إحدى نماذج الخوارزميات Algorithm Paradigm والتي تقدّم حلًّا لمسألة معقدة عن طريق تقسيمها إلى مسائل فرعية وتخزين النتائج المستحصلة لتجنب حساب النتيجة ذاتها مرة أخرى.

تمتاز المسألة التي يمكن حلّها باستخدام البرمجة الديناميكية بالخاصيتين التاليتين:

1. مسائل فرعية متداخلة Overlapping Subproblems
2. بنية فرعية مثالية Optimal Substructure

مسائل فرعية متداخلة

تشبه البرمجة الديناميكية نموذج فرّق تسد في أنّها تدمج حلول المسائل الفرعية بعضها ببعض. تستخدم البرمجة الديناميكية عمومًا عندما تظهر الحاجة إلى استخدام حلول مجموعة معينة من المسائل الفرعية مرة بعد أخرى. تخزّن حلول المسائل الفرعية في البرمجة الديناميكية في جدول وذلك لتجنّب حسابها مرة أخرى. هذا يعني أنّ البرمجة الديناميكية غير مفيدة عندما لا تكون هناك مسائل فرعية متداخلة؛ إذ لا فائدة من تخزين الحلول إن لم تكن الخوارزمية بحاجة إليها مرة أخرى.

فعلى سبيل المثال لا تتضمن عمليات البحث الثنائي Binary Search مسائل فرعية متداخلة، ولكن تتضمن عملية حساب أعداد فيبوناتشي بطريقة تعاودية العديد من المسائل الفرعية التي يجري حلّها مرة تلو الأخرى.

int fib(int n) 
{ 
if ( n <= 1 ) 
    return n; 
return fib(n-1) + fib(n-2); 
}

يمكن ملاحظة أنّ الدالة fib(3)‎ تستدعى مرتين، وإن تسنّى لنا تخزين القيمة الناتجة عن استدعاء هذه الدالة، فستنتفي الحاجة إلى إعادة حساب هذه القيمة وسيكون بالإمكان استخدام القيمة المخزّنة سابقًا عوضًا عن ذلك.

طرق تخزين القيم

هناك طريقتان مختلفتان لتخزين القيم هما:

1. التحفيظ Memoization (من الأعلى إلى الأسفل)
2. الجدولة Tabulation (من الأسفل إلى الأعلى)

التحفيظ

تشبه طريقة التحفيظ في حل مسألة معينة الطريقة التعاودية ولكن مع تعديل بسيط، وهو أنّ هذه الطريقة تبحث في جدول البحث lookup table معين قبل حساب الحلول. تبدأ العملية بتهيئة مصفوفة بحث تحمل القيمة NIL كقيمة أولية. وفي كل مرّة نحتاج فيها إلى إيجاد حلٍّ لمسألة فرعية، نبدأ بالبحث في جدول البحث، فإن كانت القيمة محسوبة مسبقًا موجودة فيه فسنعيد حينئذٍ تلك القيمة، وإلا سنحسب القيمة ونضع النتيجة في جدول البحث ليتسنى لنا إعادة استخدامها في وقت لاحق.

تعرض الأمثلة التالية كيفية استخدام طريقة التحفيظ في خوارزمية حساب العدد ذي الترتيب n في متتالية فيبوناتشي:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 
#define NIL -1 
#define MAX 100 

int lookup[MAX]; 

/* تهيئ هذه الدالة قيم جدول البحث */
void _initialize() 
{ 
    int i; 
    for (i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
} 

/* الدالة المسؤولة عن حساب العدد ذي الترتيب المعطى في متتالية فيبوناتشي */
int fib(int n) 
{ 
    if (lookup[n] == NIL) 
    { 
        if (n <= 1) 
            lookup[n] = n; 
        else
            lookup[n] = fib(n - 1) + fib(n - 2); 
} 

return lookup[n]; 
} 

// اختبار الشيفرة السابقة
int main () 
{ 
    int n = 40; 
    _initialize(); 
    cout << "Fibonacci number is " << fib(n); 
    return 0; 
}

• بايثون:

# الدالة المسؤولة عن حساب العدد ذي الترتيب المعطى في متتالية فيبوناتشي
def fib(n, lookup): 

    # الحالة الأساس
    if n == 0 or n == 1 : 
        lookup[n] = n 

  # إن لم تكن القيمة محسوبة مسبقًا فسنحسبها الآن
  if lookup[n] is None: 
        lookup[n] = fib(n-1 , lookup) + fib(n-2 , lookup) 

  # n تعيد الدالة القيمة المرتبطة بالقيمة المعطاة
  return lookup[n] 


# اختبار الدالة السابقة
def main(): 
    n = 34
    # إنشاء جدول البحث
    # يستوعب الجدول 100 عنصر
    lookup = [None]*(101) 
    print "Fibonacci Number is ", fib(n, lookup) 

if __name__=="__main__": 
    main()

• جافا:

public class Fibonacci 
{ 
final int MAX = 100; 
final int NIL = -1; 

int lookup[] = new int[MAX]; 

/* تهيئ هذه الدالة قيم جدول البحث */
void _initialize() 
{ 
    for (int i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
} 

/* الدالة المسؤولة عن حساب العدد ذي الترتيب المعطى في متتالية فيبوناتشي */
int fib(int n) 
{ 
    if (lookup[n] == NIL) 
    { 
    if (n <= 1) 
        lookup[n] = n; 
    else
        lookup[n] = fib(n-1) + fib(n-2); 
    } 
    return lookup[n]; 
} 

public static void main(String[] args) 
{ 
    Fibonacci f = new Fibonacci(); 
    int n = 40; 
    f._initialize(); 
    System.out.println("Fibonacci number is" + " " + f.fib(n)); 
} 

}

الجدولة

تبني هذه الطريقة جدولًا من الأسفل إلى الأعلى وتعيد آخر قيمة من الجدول عند الحاجة. فعلى سبيل المثال، تحسب دالة فيبوناتشي الأعداد في المتتالية حسب التسلسل fib(0)‎ ثم fib(1)‎ ثم fib(2)‎ ثم fib(3)‎ وهكذا. وهذا يعني أنّنا نبني جدول الحلول للمسائل الفرعية من الأسفل إلى الأعلى حرفياً.

تعرض الأمثلة التالية كيفي استخدام طريقة الجدولة في خوارزمية حساب العدد ذي الترتيب n في متتالية فيبوناتشي:

• C++‎:

#include<stdio.h> 
int fib(int n) 
{ 
// إنشاء المصفوفة
int f[n+1]; 
int i; 

// الحالة الأساس
f[0] = 0; f[1] = 1; 

// حساب متتالية فيبوناتشي وتخزين القيم
for (i = 2; i <= n; i++) 
	f[i] = f[i-1] + f[i-2]; 

return f[n]; 
} 

// اختبار الدالة السابقة
int main () 
{ 
int n = 9; 
printf("Fibonacci number is %d ", fib(n)); 
return 0; 
}

• بايثون:

def fib(n): 

	# إنشاء المصفوفة 
	f = [0]*(n+1) 

	# الحالة الأساس
	f[1] = 1

	# حساب متتالية فيبوناتشي وتخزين القيم
	for i in xrange(2 , n+1): 
		f[i] = f[i-1] + f[i-2] 
	return f[n] 

# اختبار الدالة السابقة
def main(): 
	n = 9
	print "Fibonacci number is " , fib(n) 

if __name__=="__main__": 
	main()

• جافا:

public class Fibonacci 
{ 
int fib(int n) 
{ 
	// إنشاء المصفوفة
	int f[] = new int[n+1]; 
	// الحالة الأساس
	f[0] = 0; 
	f[1] = 1; 
	// حساب متتالية فيبوناتشي وتخزين القيم
	for (int i = 2; i <= n; i++) 
		f[i] = f[i-1] + f[i-2]; 
	return f[n]; 
} 

// اختبار الدالة السابقة

public static void main(String[] args) 
{ 
	Fibonacci f = new Fibonacci(); 
	int n = 9; 
	System.out.println("Fibonacci number is" + " " + f.fib(n)); 
} 

}

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

من المحتمل أن لا يظهر أثر عملية التحسين (سواء باستخدام طريقة التحفيظ أو الجدولة) عند حساب متتالية فيبوناتشي لأعداد صغيرة، ولكن الأثر يظهر جليًّا عند حساب الرقم ذي الترتيب 40 في المتتالية، إذ تستغرق عملية حساب هذا العدد بالطريقة التعاودية البسيطة وقتًا أطول بكثير من طريقة البرمجة الديناميكية (التحفيظ أو الجدولة).

بنية فرعية مثالية

نقول أنّ مسألة معيّنة تمتلك بنية فرعية مثالية إذا كان بالإمكان الحصول على الحل المثالي للمسألة المعطاة بجمع الحلول المثالية للمسائل المتفرّعة عن المسألة الرئيسية.

فعلى سبيل المثال تمتلك مسألة المسار الأقصر Shortest Path خاصية البنية الفرعية المثالية التالية:

إن كانت عقدة معينة (لتكن x) تقع في المسار الأقصر بين العقدة المصدرية u والعقدة الهدف v فإنّ المسار الأقصر بين u و v هو ناتج عن دمج المسار الأقصر بين العقدتين u و x والمسار الأقصر بين العقدتين x و v.

ويمكن القول أنّ خوارزميات المسارات الأقصر لجميع الأزواج All Pair Shortest Path مثل خوارزميتي فلويد-وارشال وبيلمان-فورد هي أفضل مثال على البرمجة الديناميكية.

لا تمتلك خوارزميات المسار الأطول Longest Path في المقابل خاصية البنية الفرعية المثالية، والمقصود هنا هو المسار الأطول البسيط (مسار دون دورات) بين عقدتين.

خذ الرسم البياني غير الموزون هذا كمثال:

هناك مساران أطولان أفضلان بين العقدتين q و t هما: ‎q→r→t و ‎q→s→t. لا يمتلك هذان المساران الأطولان الأفضلان -على عكس المسارات الأقصر الفضلى- خاصية البنية الفرعية المثالية. فعلى سبيل المثال لا ينتج المسار q→r→t عن دمج المسار الأطول بين العقدتين q و r والمسار الأطول بين العقدتين r و t وذلك لأنّ المسار الأطول بين العقدتين q و r هو q→s→t→r والمسار الأطول بين العقدتين r و t هو r→q→s→t.

حل المسائل باستخدام البرمجة الديناميكية

تتبع عملية حل المسائل باستخدام البرمجة الديناميكية الخطوات التالية:

1. تشخيص ما إذا كانت المسألة المعنية مسألة برمجة ديناميكية
2. اتخاذ القرار بشأن استخدام تعبير حالة state expression مع أقل عدد ممكن من المعاملات.
3. صياغة علاقة الحالة state relationship
4. إجراء عملية الجدولة (أو التحفيظ)

الخطوة الأولى: تصنيف المسألة على أنّها مسألة برمجة ديناميكية

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

تمتلك جميع مسائل البرمجة الديناميكية خاصية المسائل الفرعية المتداخلة، وتمتلك معظم المسائل الديناميكية الكلاسيكية خاصية البنية الفرعية المثالية، ويمكن القول أنّه بمجرد ملاحظة هاتين الخاصيتين في مسألة معينة، فإنّ من المؤكّد أنّ بالإمكان حلّ تلك المسألة باستخدام البرمجة الديناميكية.

الخطوة الثانية: اتخاذ القرار بشأن الحالة

تتمحور مسائل البرمجة الديناميكية حول الحالة وانتقالها، وتعدّ هذه الخطوة الأكثر أهمية ويجب تنفيذها بعناية؛ وذلك لأنّ انتقال الحالة يعتمد على التعريف الذي جرى اختياره للحالة.

ويقصد بالحالة هنا مجموعة المعاملات التي يمكنها تعريف موقع أو موقف معين في المسألة تعريفًا فريدًا، ويجب أن يكون عدد المعاملات قليلًا قدر الإمكان وذلك لتقليص المساحة التي ستشغلها تلك الحالة.

فعلى سبيل المثال تعرّف الحالة في مسألة حقيبة الظهر Knapsack problem باستخدام معاملين هما index و weight (أي تعرّف المصفوفة DP[index][weight]‎) واللذان يخبراننا أنّ الفائدة العظمى maximum profit بأخذ العناصر من النطاق الذي يبدأ من 0 وينتهي بقيمة المعامل index وتمتلك الحقيبة سعة مساوية لقيمة المعامل weight. وهذا يعني أنّ المعاملين index و weight قد عرّفا بطريقة فريدة مسألة فرعية في مسألة حقيبة الظهر.

الخطوة الثالثة: صياغة علاقة تربط بين الحالات

لما كانت البرمجة الديناميكية تعتمد على النتائج المحسوبة لصياغة النتيجة النهائية، فإنّ من اللازم إيجاد علاقة تربط بين الحالات السابقة للوصول إلى الحالة الراهنة.

وهذا هو الجزء الأصعب في حل مسائل البرمجة الديناميكية ويتطلب الكثير من الملاحظة والتمرين. فعلى سبيل المثال:

لنفترض أن لدينا الأعداد ‎{1, 3, 5}‎ والمطلوب هو إيجاد عدد الطرق التي يمكن استخدام هذه الأرقام فيها لحساب رقم معيّن (ليكن N) وذلك بإجراء عملية الجمع مع السماح بتكرار الأعداد وتغيير ترتيبها.

إن كان N = 6 فإنّ عدد الطرق سيكون 8.

لكي نتمكّن من حلّ هذه المسألة ديناميكيًا يجب في البداية اتخاذ قرار بشأن الحالة الخاصة بالمسألة المعطاة، وسنستخدم معاملًا (ليكن n) لاتخاذ القرار بشأن الحالة الراهنة وذلك لإمكانية استخدام هذه المعامل في تشخيص أي مسألة فرعية بطريقة فريدة. وبهذا تكون الحالة في هذه المسألة هي state(n)‎، والتي تمثّل هنا العدد الكلي للترتيبات التي يمكن استخدامها لتكوين العدد n باستخدام العناصر ‎{1, 3, 5}‎.

ولمّا كان بالإمكان استخدام الأعداد 1 و 3 و 5 فقط لتكوين العدد المعطى، سنفترض أنّنا نعرف نتائج الأعداد n = 1, 2, 3, 4 , 5, 6 مسبقًا، وبمعنى آخر فإنّنا نعرف نتائج كلّ من ‎state (n = 1), state (n = 2), state (n = 3) ……… state (n = 6)‎.

لو أردنا معرفة النتيجة الخاصة بالحالة state (n = 7)‎ باستخدام الأعداد 1 و 3 و 5 فقط، فيمكننا حينئذٍ الحصول على المجموع 7 بالطرق الثلاثة التالية:

1- إضافة 1 إلى جميع الاحتمالات التي تعطي الحالة state (n =6)‎.

   [ (1+1+1+1+1+1) + 1]
   [ (1+1+1+3) + 1]
   [ (1+1+3+1) + 1]
   [ (1+3+1+1) + 1]
   [ (3+1+1+1) + 1]
   [ (3+3) + 1]
   [ (1+5) + 1]
   [ (5+1) + 1]

2- إضافة 3 إلى جميع الاحتمالات التي تعطي الحالة state (n=4)‎.

[(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]

3- إضافة 5 إلى جميع الاحتمالات التي تعطي الحالة state (n=2)‎.

[ (1+1) + 5]

ومما سبق يمكن صياغة المعادلة التالية:

state(7) = state (6) + state (4) + state (2)

أو

state(7) = state (7-1) + state (7-3) + state (7-5)

ويمكن القول عمومًا:

state(n) = state(n-1) + state(n-3) + state(n-5)

وتصبح الشيفرة كما يلي:

// تعيد الدالة عدد الترتيبات لتكوين العدد المعطى
int solve(int n) 
{ 
// الحالة الأساس
if (n < 0) 
	return 0; 
if (n == 0) 
	return 1; 

return solve(n-1) + solve(n-3) + solve(n-5); 
}

تعمل الشيفرة السابقة بتعقيد زمني أسّي وتحسب الحالة نفسها مرارًا وتكرارًا؛ ولهذا يجب إضافة عملية التحفيظ memoization.

الخطوة الرابعة: إضافة التحفيظ أو الجدولة إلى الحالة

تخزّن الإجابة عن حالة معيّنة في جدول البحث وذلك لاستدعائها مرة أخرى إن تطلب الأمر ذلك دون الحاجة إلى حسابها مرة أخرى.

يعرض المثال التالي الشيفرة السابقة بعد إضافة عملية التحفيظ إليها:

// تهيئة القيمة لتكون -1 
int dp[MAXN]; 

// تعيد هذه الدالة عدد الترتيبات لتكوين العدد `n`
int solve(int n) 
{ 
// الحالة الأساس
if (n < 0) 
	return 0; 
if (n == 0) 
	return 1; 

// التحقق من أنّ الحالة الراهنة محسوبة مسبقًا
if (dp[n]!=-1) 
	return dp[n]; 

// تخزين النتيجة وإعادتها
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5); 
}

الأعداد القبيحة

الأعداد القبيحة هي الأعداد التي تكون عواملها الأولية هي الأعداد ‎2, 3, 5‎.

تصريف العملة

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

حساب أقل عدد من العملات التي تكوّن قيمة معينة

تفترض هذه المسألة وجود مبلغ من المال والمطلوب هو تصريف هذا المبلغ إلى عملات أصغر على فرض أن هناك عددًا غير محدود من هذه العملات.

مسألة حقيبة الظهر ‎0-1

المطلوب في مسألة حقيبة الظهر ‎0-1 هو وضع مجموعة من العناصر ذات أوزان وقيم محددة في حقيبة ظهر تتسع لعدد معين من العناصر مع مراعاة الحصول على أكبر قيمة ممكنة لمجموع قيم العناصر الموجودة في الحقيبة، ولكن بشرط عدم وضع جزء من العنصر فإما أن يوضع العنصر كاملًا أو لا يوضع إطلاقًا.

مسألة أطول تسلسل فرعي مشترك

نقول عن تسلسل فرعي معيّن بأنّه أطول تسلسل فرعي مشترك Longest Common Subsequence عندما يظهر هذا التسلسل الفرعي بنفس الترتيب النسبي ولكن دون اشتراط تجاور العناصر.

مسألة أطول تسلسل فرعي تصاعدي

تبحث مسألة أطول تسلسل فرعي تصاعدي Longest Increasing Subsequence ( وتعرف اختصارًا بـ LIS) عن طول أطول تسلسل فرعي في تسلسل معين بشرط أن تُرتب جميع العناصر في التسلسل الفرعي ترتيبًا تصاعديًا.

مصادر

• صفحة Dynamic Programming في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Overlapping Subproblems Property in Dynamic Programming | DP-1 في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Optimal Substructure Property in Dynamic Programming | DP-2 في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة How to solve a Dynamic Programming Problem في توثيق الخوارزميات في موقع GeeksforGeeks.