books code for dynamic programming
If you do not find what you're looking for, you can use more accurate words.
كود لحل البرمجة الديناميكيه (Info)
حساب طول الـ 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 و تتحرك للاعلي بأتجاه اليسار وفي حاله عدم التساوي يكون المسار للاعلي أو لليسار معتمدة علي الخلية ذات اعلي رقم
