كتب code for dynamic programming
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
كود لحل البرمجة الديناميكيه (معلومة)
حساب طول الـ LCS
في الكود التالي المتسلسلات هي X[1..m] و Y[1..n] و يتم حساب الـ بين X[1..i] و Y[1..j] لكل 1 ≤ i ≤ m و 1 ≤ j ≤ n و تقوم بحفظها في C[i,j] . و يحتوي C[m,n] علي طول الـ LCS
function LCSLength(X[1..m], Y[1..n]) C = array(0..m, 0..n) for i := 0..m C[i,0] = 0 for j := 0..n C[0,j] = 0 for i := 1..m for j := 1..n if X[i] = Y[j] C[i,j] := C[i-1,j-1] + 1 else C[i,j] := max(C[i,j-1], C[i-1,j]) return C[m,n]
قراءة LCS
الكود التالي به تنخفض الاختيارات عند حساب جدول C , إذا كان آخر عنصر من البادئات متساوي، يجب أن تكون في الـ LCS بالاحتفاظ بـ X و Y
function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i = 0 or j = 0 return "" else if X[i] = Y[j] return backtrack(C, X, Y, i-1, j-1) + X[i] else if C[i,j-1] > C[i-1,j] return backtrack(C, X, Y, i, j-1) else return backtrack(C, X, Y, i-1, j)
قراءة جميع LCS
إذا كان اختيار X و Y سوف يعطينا نتيجه طويله، فقم بقراءة نتائج المتسلسلات الجزئية . لاحظ ان هذة الدالة ليست كثيرة الحدود
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i = 0 or j = 0 return {""} else if X[i] = Y[j] return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)} else R := {} if C[i,j-1] ≥ C[i-1,j] R := R ∪ backtrackAll(C, X, Y, i, j-1) if C[i-1,j] ≥ C[i,j-1] R := R ∪ backtrackAll(C, X, Y, i-1, j) return R
طباعه الفرق
لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥ و <,بـ > و ≤
function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i > 0 and j > 0 and X[i] = Y[j] printDiff(C, X, Y, i-1, j-1) print " " + X[i] else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j]) printDiff(C, X, Y, i, j-1) print "+ " + Y[j] else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j]) printDiff(C, X, Y, i-1, j) print "- " + X[i] else print ""
مثال
بفرض ان X هي XMJYAUZ و Y هي MZJAWXU. أطول متسلسله جزئيه مشتركه بين X و Y هي MJAU . الجدول C الموضح بالاسفل يبين لنا طول أطول متسلسله جزئيه مشتركه بين البادئات . صفوف الـ i و اعمدة j تظهر طول الـ LCS الارقام الملونه تظهر مسار الدالة من الاسفل الي الاعلي . عند تساوي ال x و y يكونا جزء من ال LCS و تتحرك للاعلي بأتجاه اليسار وفي حاله عدم التساوي يكون المسار للاعلي أو لليسار معتمدة علي الخلية ذات اعلي رقم
