فى علم ال “Computer Science” و ال “Mathematics” , ال "Dynamic Programming" هو عبارة عن طريقة نستطيع بها حل بعض المشكلات , عن طريق تقسيم المشكلة الكبيرة الى عدة مشاكل صغيرة .
وبالمناسبة كلمة “programming” فى مصطلح “Dynamic Programming” ليس لها علاقة بالبرمجة التى ندرسها فى الكلية ك“coding” .... وانما المقصود بها على حد تصورى , ايجاد طريقة معقولة ومناسبة بخطوات لحل المشكلة, عن طريق تخرين الحلول الصغيرة واستخدامها فى ايجاد الحل الكبير, وبالتالى كلمة "Programming" لها معنى "Historical".
المشاكل التى يمكن حلها بال “Dynamic Programming” يجب ان تكون قابلة للتقسيم لعدة مشاكل صغيرة ... ونقسم المشاكل الصغيرة الى مشاكل أصغر الى أن نصل الى أصغر مشكلة جزئية ممكنة نستطيع حلها بدون أى حسابات وذلك ما يعرف بال “Base Case”.
أشهر أمثلة ال “Dynamic Programming” على الاطلاق هى “Longest Common Subsequence” .
“Longest Common Subsequence” هو عبارة عن أكبر جزء مشترك بين متسلسلتين أو أكتر , وال “LCS” له تطبيقات عديدة ,حيث يمكن على سبيل المثال باستخدام ذلك ال Algorithm مقارنة ال DNA لأكثر من شخص ومعرفة نسبة التطابق بينهما .... حيث ان ال DNA يتكون من متسلسة كبيرة .
مثال :
A = {a,b,c,d,e,f}
B = {a,b,w,d,e,f}
ال LCS للمتسلسلتين A , B هو 5 وهو عبارة عن {a,b,d,e,f}
ويمكننا ان نحل المثال السابق يدويا
نقارن الحرف الأول فى A بالحرف الأول فى B نجد ان الحرفان متطابقان وهو "a" اذن ال LCS تساوى 1.
ننتقل للحرف الثانى فى A مع الحرف الثانى فى B وهو"b", " اذن ال LCS تساوى 1 + 1 = 2.
ننقل للحرف الثالث فى A مع الحرف الثالث فى B نجد ان الحرفان غير متطابقان وبالتالى يجب ان نقارن المتسلسلتان الى النهاية أى, نقارن الحرف الثالث فى A مع الحرف الرابع ف B اذا تطابقا ننتقل الى الحرف الرابع فى A مع الحرف الخامس فى B
واذا لما يتطابقا نقارن الحرف الثالث فى A مع الحرف الخامس فى B الى ان نصل الى نهاية المتسلسة الثانية ثم نعود الى الحرف الرابع فى A ونقارنه بكل حروف المتسلسة الثانية وهكذا
وفى هذا المثال سنقارن ال “c” بال { w,d,e,f } وفى كل مرة ال LCS لا تزيد لعدم وجود أى حروف متشابهة
وبعد ذلك نبدأ بمقارنة ال “d” أى الحرف الرابع فى ال A مع الحرف الثالث فى ال B وهو ال "w" لا يوجد تطابق اذن ال LCS تساوى 2 (أكبر LCS حصلنا عليها حتى الان)
ثم نقارن الحرف الرابع فى A مع الحرف الرابع فى B نجد ان الحرفان متطابقان , اذن ال LCS تساوى 2 + 1
ثم نقارن الحرف الخامس فى A مع الحرف الخامس فى B نجد أن الحرفان متطابقان اذن ال LCS تساوى 3 + 1
ثم نقارن الحرف السادس فى A مع الحرف السادس فى B نجد أن الحرفان متطابقان اذن ال LCS تساوى 4 + 1
الان وصلنا الى نهاية المتسلسة الاولى والمتسلسة الثانية واذثبتنا ان ال LCS لل A,B تساوى 5
خلاصة الأمر : نقارن كل حرف بمن يوازيه فى Sequence الاخرى ... اذا تطابق الحرفان ننتقل الى الحرف التالى فى كل Sequence ويزيد ال LCS واحد
اذا لما يتطابقا , اذن نقارن نفس الحرف فى Sequence الأولى مع الحرف التالى فى Sequence الثانية وكلما يتطابق حرفين يزيد ال LCS واحد , الى ان نصل الى الحرف الاخير من Sequence الأولى مع الحرف الاخير من Sequence الثانية .
عندما نبدأ فى حل مشكلة بال “Dynamic Programming” يجب أولا ان نبحث عن ال “Base Case”
فى مثال ال “Longest Common Subsequence” ما هو ال “Base Case” ؟؟
أى ما هى أصغر مشكلة جزئية نعرف حلها بدون أى حسابات ؟؟
] فكر(ى) شوية [:D
.
.
.
.
.
.
ال “Base Case” هى عندما نقارن Sequence فارغة باخرى فارغة , حينها يكون ال LCS يساوى 0
ونستنتج التالى
| LCS | B | A |
| 0 | {a,b,c,d,e} | {} |
| 0 | {} | {a,b,c,d,e} |
| 0 | {} | {} |
ويمكننا كتابة خطوات الحل فى المثال السابق بصورة رياضية كالتالى
لكى نستطيع فهم العلاقة الرياضة السابقة بصورة أفضل يمكننا رسم الجدول التالى
| f | e | d | w | b | a | | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| | | | | | | 0 | a |
| | | | | | | 0 | b |
| | | | | | | 0 | c |
| | | | | | | 0 | d |
| | | | | | | 0 | e |
| | | | | | | 0 | f |
نلاحظ فى ذلك الجدول اننا نضيف قبل كل Sequence حرف فارغ
الأصفار هنا هى عبارة عن ال “Base Case”
ونقارن أول حرف فارغ فى Sequence الأولى بكل الحروف فى Sequence الثانية وطبعا الناتج يكون 0
ونقارن الحرف الأول فى Sequence الثانية "الحرف الفارغ" بكل حروف Sequence الأولى ويكون الناتج فى كل الحالات أيضا 0
وهذه هى الحالة الأول فى العلاقة الرياضية
وبعد ذلك سنقارن الحروف فى ذلك الجدول Row By Row ونبدأ بالحرف فى ال Row الثانى "a" ونقارنه بالحرف فى ال Column الثانى “a”, نجد ان الحرفين متساويين اذن نطبق الحالة الثانية فى العلاقة الرياضية .
ثم ننتقل الى الحرف فى ال Column الثالث “b”نجد ان الحرفان لا يتطابقان أذن نطبق الحالة الثالثة فى العلاقة الرياضية وهى اعتبار ان ال LCS هو عبارة عن أكبر قيمة لل LCS تم الوصول اليها حتى الان دون اضافة
ونقوم بملئ الجدول السابق بنفس الطريقة مع كل الحروف, سنحصل فى النهاية على الجدول بالشكل التالى
وبالطبع قيمة ال LCS هى القيمة الموجودة فى اخر Cell فى تلك ال Matrix وهى تساوى 5
الان يمكنكم المحاولة فى كتابة الكود بأنفسكم باستخدام العلاقة الرياضية السابقة بسهولة كبيرة
يمكنك الاطلاع على الكود بالطريقة العادية من هنااا
بالمناسبة ذلك الكود هو حل مسألة Common Subsequence على ال PKU
كود ال هنااا Recursion
بالمناسبة ذلك الكود يحل مسألة Longest Common Subsequence
أى شئ مش مفهوم اتفضلوا اسألو