0 - سید محمد بیدکی

Report
‫درس طراحی الگوریتم ها‬
‫فصل سوم ( ادامه )‬
‫روش برنامه نویسی پویا‬
‫‪Dynamic Programming‬‬
‫مدرس‪ :‬سید محمد بیدکی‬
‫بهار ‪1392‬‬
‫درخت های جست وجوی دودویی‬
‫‪ ‬تعریف‬
‫‪ ‬یک درخت دودویی از مجموعه مرتبی از‬
‫عناصر (کلیدها) حاصل می شود به گونه‬
‫ای که‪:‬‬
‫‪ ‬هر گره حاوی یک کلید است‪.‬‬
‫‪ ‬کلیدهای موجود در زیردرخت چپ یک گره‪،‬‬
‫کوچکتر یا مساوی کلید آن گره است‪.‬‬
‫‪ ‬کلیدهای موجود در زیردرخت راست یک‬
‫گره‪ ،‬بزرگتر یا مساوی کلید آن گره است‪.‬‬
‫‪1  2n ‬‬
‫‪ ‬‬
‫‪n 1  n ‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫تعداد درخت های‬
‫دودویی با ‪ n‬کلید‬
‫درخت بهینه‬
‫‪ ‬عمق (سطح) یک گره‬
‫‪ ‬تعداد یالهای موجود در مسیر منحصربه فرد از ریشه به آن گره‪.‬‬
‫‪ ‬عمق یک درخت‬
‫‪ ‬حداکثر عمق تمامی گره های موجود در آن درخت‪.‬‬
‫‪ ‬درخت متوازن‬
‫‪ ‬اگر عمق دو زیردرخت از هر گره‪ ،‬بیش از یک واحد اختالف نداشته باشد‪.‬‬
‫‪ ‬درخت جستجوی دودویی بهنیه‬
‫‪ ‬درختیست که در آن کلیدها به نحوی قرار گرفته باشند که زمان متوسط‬
‫برای مکان یابی یک کلید در آن کمینه است‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫زمان متوسط مکان یابی کلید‬
‫‪ ‬زمان جستجو‬
‫‪ ‬تعداد مقایسه های انجام شده برای مکان یابی یک کلید ‪depth(key) + 1‬‬
‫‪ ‬متوسط زمان جستجو‬
‫‪n‬‬
‫‪ ‬که در آن‪:‬‬
‫‪pi‬‬
‫‪c‬‬
‫‪i‬‬
‫‪i 1‬‬
‫‪ n ‬تعداد کلیدها‬
‫‪ pi ‬احتمال آنکه ‪ keyi‬کلید مورد جستجو باشد‬
‫‪ ci ‬تعداد مقایسه مورد نیاز برای یافتن ‪ keyi‬می باشد‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪1. 3(0.7) + 2(0.2) + 1(0.1) = 2.6‬‬
‫‪2. 2(0.7) + 3(0.2) + 1(0.1) = 2.1‬‬
‫‪3. 2(0.7) + 1(0.2) + 2(0.1) = 1.8‬‬
‫‪4. 1(0.7) + 3(0.2) + 2(0.1) = 1.5‬‬
‫‪5. 1(0.7) + 2(0.2) + 3(0.1) = 1.4‬‬
‫‪p1 = 0.7 p2 = 0.2 p3 = 0.1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫ایجاد جدول‬
‫‪ ‬اصل بهینگی برقرار می باشد‪.‬‬
‫‪ ‬هر زیردرخت از یک درخت جستجوی دودویی بهینه‪ ،‬برای کلیدهای موجود در آن‬
‫زیر درخت‪ ،‬بهینه است‪.‬‬
‫‪ ‬برای حل به روش برنامه سازی پویا‪ ،‬باید زمان متوسط جستجو در هر زیردرخت‬
‫را ذخیره کنیم‪.‬‬
‫‪ ‬زمان متوسط برای جست و جوی کلیدها در درختی که ‪j‬شامل کلیدهای ‪keyi‬‬
‫تا ‪ keyj‬می باشد‪:‬‬
‫‪ cm p m‬‬
‫‪m i‬‬
‫‪ ‬قرار می دهیم‪:‬‬
‫زمان متوسط جستجو در درخت بهینه شامل کلیدهای ‪ keyi‬تا ‪A[i][j] = keyj‬‬
‫‪A[i][i] = pi‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪ ‬فرض کنید سه کلید و احتماالت مرتبط با آنها را داریم‪:‬‬
‫‪P1=0.7, P2=0.2, P3=0.1‬‬
‫‪ ‬برای تعیین ]‪ A[2][3‬دو درخت ممکن خواهیم داشت‪:‬‬
‫‪1(P2) + 2(P3) = 0.4‬‬
‫‪K2‬‬
‫‪1.‬‬
‫‪K3‬‬
‫‪2(P2) + 1(P3) = 0.5‬‬
‫‪K3‬‬
‫‪K2‬‬
‫‪2.‬‬
‫‪ => A[2][3] = 0.4‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫تعیین رابطه بازگشتی‬
‫فرض کنید درخت ‪ ،K‬درختیست‬
‫بهینه که ریشه آن کلید ‪ K‬است‪:‬‬
‫زمان جستجوی میانگین در این‬
‫زیردرخت ]‪ A[k+1][n‬است‬
‫به ازای هر کلید یک مقایسه‬
‫اضافی در ریشه وجود دارد‬
‫‪keyk‬‬
‫زمان جستجوی میانگین در این‬
‫زیردرخت ]‪ A[1][k-1‬است‬
‫‪Keyk+1 … keyn‬‬
‫‪key1 … keyk-1‬‬
‫زمان متوسط جستجو در درخت ‪:K‬‬
‫]‪A[1][k-1] + p1 + … + pk-1 + pk + pk+1 + … + pn + A[k+1][n‬‬
‫زمان اضافی‬
‫مقایسه در ریشه‬
‫زمان میانگین در‬
‫زیردرخت راست‬
‫زمان میانگین‬
‫جستجو برای‬
‫ریشه‬
‫زمان اضافی‬
‫مقایسه در ریشه‬
‫زمان میانگین در‬
‫زیردرخت چپ‬
‫چون یکی از ‪ n‬درخت باید بهینه باشد‪ ،‬زمان جستجوی درخت بهینه برابر است با‪:‬‬
‫‪n‬‬
‫‪A[1][n]  min A[1][k  1]  A[k  1][n]   pm‬‬
‫‪1 k  n‬‬
‫‪m 1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫رابطه بازگشتی‬
‫‪i j‬‬
‫‪j‬‬
‫‪A[i ][ j ]  min A[i ][k  1]  A[k  1][ j ]   pm‬‬
‫‪m i‬‬
‫‪ik  j‬‬
‫‪A[i ][i ]  pi‬‬
‫‪A[i ][i  1]  0‬‬
‫‪A[ j  1][ j ]  0‬‬
‫‪‬سطرهای ماتریس ‪ A‬از ‪ 1‬تا ‪ n+1‬و ستون های آن از ‪ 0‬تا ‪ n‬اندیس گذاری می شوند‪.‬‬
‫‪‬برای ساخت درخت و دانستن کلیدهای ریشه نیاز به یک ماتریس ‪ R‬با همین ابعاد‬
‫داریم‪.‬‬
‫‪‬ماتریس ها مانند ضرب زنجیره ای ماتریس ها به صورت قطری پر می شوند‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫الگوریتم تعیین درخت جستجوی دودویی بهینه‬
Void optSearchTree( int n, const float p[], float &minavg, index R[][]) {
index i, j, k, diagonal;
float A[1..n+1][0..n];
for (i=1; i<=n; i++){
A[i][i-1] = 0; A[i][i] = p[i];
R[i][i-1]=0; R[i][i] = i;
‫تحلیل پیچیدگی زمانی الگوریتم‬
‫مشابه الگوریتم ضرب زنجیره ای‬
(n3 )
:‫ماتریسها‬
}
A[n+1][n] = 0;
R[n+1][n] = 0;
for (diagonal=1; diagonal<= n-1; diagonal++)
for(i =1; i<=n-diagonal; i++){
j = i+diagonal;
A[i][j] = min (A[i][k-1] + A[k+1][j]) + SUM(p[i] ... P[j])
R[i][j] = a value of k that gave the minimum;
}
minavg = A[1][n];
}
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
// i ≤ k ≤ j
‫ساخت درخت جستجوی دودویی بهینه‬
Node_pointer tree(index i, j){
index k;
Node_pointer p;
k=R[i][j];
if (k==0)
return NULL;
else {
p = new nodetype;
p -> key = Key[k];
P -> left = tree(i, k-1);
p -> right = tree(k+1, j);
return p;
}
}
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
‫مثال‬
‫‪Wally‬‬
‫‪Ralph‬‬
‫‪Isabella‬‬
‫‪Don‬‬
‫‪Keys‬‬
‫]‪[4‬‬
‫]‪[3‬‬
‫]‪[2‬‬
‫]‪[1‬‬
‫‪Index‬‬
‫‪1/8‬‬
‫‪1/8‬‬
‫‪3/8‬‬
‫‪3/8‬‬
‫‪priority‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪0‬‬
‫‪R‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪0‬‬
‫‪A‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪1‬‬
‫‪7/4‬‬
‫‪11/8‬‬
‫‪9/8‬‬
‫‪3/8‬‬
‫‪0‬‬
‫‪1‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪0‬‬
‫‪2‬‬
‫‪1‬‬
‫‪5/8‬‬
‫‪3/8‬‬
‫‪0‬‬
‫‪3‬‬
‫‪3‬‬
‫‪0‬‬
‫‪3‬‬
‫‪3/8‬‬
‫‪1/8‬‬
‫‪0‬‬
‫‪4‬‬
‫‪0‬‬
‫‪4‬‬
‫‪1/8‬‬
‫‪0‬‬
‫‪5‬‬
‫‪0‬‬
‫‪0‬‬
‫= ]‪A[2][3‬‬
‫‪k=2: A[2][1] + A[3][3] + p2 + p3 = 0 + 1/8 + 3/8 + 1/8 = 5/8‬‬
‫‪k=3: A[2][2] + A[4][3] + p2 + p3 = 3/8 + 0 + 3/8 + 1/8 = 7/8‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫کوله پشتی صفر و یک‬
‫‪ ‬تعداد ‪ n‬کاال با وزن و ارزش معین وجود دارد‪.‬‬
‫‪ ‬شی‪ i=1,2,…,n ، i‬دارای وزن ‪ wi‬و ارزش ‪pi‬‬
‫است‪.‬‬
‫‪ ‬یک کوله پشتی با ظرفیت وزنی ‪ W‬موجود است‪.‬‬
‫‪ ‬هدف‪:‬‬
‫‪ ‬کوله پشتی را به گونه ای پرکنیم که ارزش اشیا‬
‫انتخاب شده حداکثر شود‪.‬‬
‫‪ ‬در کوله پشتی صفرویک هر کاال یا انتخاب می‬
‫شود یا اصال انتخاب نمی گردد‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪pi‬‬
‫‪wi‬‬
‫‪3‬‬
‫‪2‬‬
‫‪3‬‬
‫‪5‬‬
‫‪4‬‬
‫‪8‬‬
‫‪5‬‬
‫‪10‬‬
‫‪9‬‬
‫ارزش‬
‫وزن‬
‫‪4‬‬
‫‪Items‬‬
‫‪W= 20‬‬
‫کوله پشتی با ظرفیت ‪20‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫الگوریتم ‪brute-force‬‬
‫‪ ‬با وجود داشتن ‪ n‬کاال در کل ‪ 2n‬حالت مختلف از ترکیب آنها وجود دارد‪.‬‬
‫‪ ‬مرتبه الگوریتم )‪ o(2n‬است‪.‬‬
‫‪ ‬آیا می توان بهتر از این حل کرد؟‬
‫‪ ‬بله – با استفاده از روش برنامه نویسی پویا‬
‫‪ ‬زیرمسئله در این مسئله چیست؟‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫فرمولبندی مسئله‬
‫‪ ‬اگر اشیا از ‪ 1‬تا ‪ n‬برچسب گذاری شوند پس مسئله یافتن جواب بهینه برای‬
‫مجموعه تصمیمات زیر است‪.‬‬
‫} ‪Sn = {x1 , x2 , … , xn‬‬
‫که ‪ xi‬تصمیم مبنی بر وجود یا عدم وجود شیئ ‪ i‬در کوله پشتی است‪.‬‬
‫‪n‬‬
‫‪‬‬
‫مجموعه ای از تصمیمات بهینه است که ماکزیمم کند مقدار ‪ p x‬‬
‫را به شرطی که ‪ w x  W‬‬
‫‪i‬‬
‫‪n‬‬
‫‪i‬‬
‫‪i‬‬
‫‪i‬‬
‫‪i 1‬‬
‫‪i 1‬‬
‫‪ ‬با داشتن مجموعه بهینه ای از ‪ k‬شیء اول بررسی کنیم امکان اضافه کردن شیء‬
‫جدیدی وجود دارد یا خیر‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫حل گام به گام بازگشتی‬
‫‪ ‬در هر مرحله تکلیف یک شیئ مشخص می شود‪ .‬اگر از ‪ xn‬شروع کنیم‬
‫‪ ‬اگر ‪ xn=1‬باشد آنگاه ارزش کوله به اندازه ‪ pn‬اضافه و ظرفیت کوله به اندازه ‪wn‬‬
‫کاسته می شود و باید مسئله را برای ‪ n-1‬شیئ و ظرفیت ‪ W-wi‬باقیمانده حل کرد‪.‬‬
‫‪ ‬اگر اگر ‪ xn=0‬باشد آنگاه باید مسئله را برای ‪ n-1‬شیئ و ظرفیت ‪ W‬حل کرد‪.‬‬
‫‪p‬‬
‫‪n‬‬
‫‪(W  wn ) ‬‬
‫‪n 1‬‬
‫‪(W), f‬‬
‫‪n 1‬‬
‫‪f‬‬
‫‪(W)  max‬‬
‫‪n‬‬
‫‪f‬‬
‫‪ ‬یعنی از دو گزینه انتخاب یا عدم انتخاب شیئ ‪ n‬اُم‪ ،‬هر کدام که بهینه باشد‬
‫برگزیده خواهد شد‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫رابطه بازگشتی‬
‫‪ B[w][k] ‬سود بهینه حاصل از انتخاب ‪ k‬قطعه اول‪ ،‬تحت این محدودیت‬
‫که وزن کل از ‪ w‬تجاوز نکند‪.‬‬
‫]‪B[ w][k  1‬‬
‫‪if wk  w‬‬
‫‪‬‬
‫‪B[ w][k ]  ‬‬
‫‪max{B[ w][k  1], B[ w  wk ][k  1]  pk } if wk  w‬‬
‫‪‬اگر ‪ wk‬بیشتر از وزن زیرمسئله باشد پس جواب شامل شیء ‪ k‬نمی شود‪.‬‬
‫‪‬اگر وزن آن کمتر یا مساوی با وزن زیرمسئله باشد‪ ،‬می تواند در جواب‬
‫باشد و مجموعه با ارزش بیشتر انتخاب می شود‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫الگوریتم به روش برنامه نویسی پویا‬
for w = 0 to W
B[w][0] = 0
for i = 0 to n
B[0][ i] = 0
T (n)  ( w * n)
for i = 1 to n
for w = 1 to W
if wi <= W // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
‫مثال‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪ n = 4‬تعداد اشیا‬
‫‪ W = 5‬ظرفیت کوله پشتی‬
‫وزن‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫ارزش‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫‪6‬‬
‫‪1‬‬
‫‪0‬‬
‫‪for w = 0 to W‬‬
‫‪B[w][0] = 0‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫‪i‬‬
‫‪W‬‬
‫‪0‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫مثال‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪ n = 4‬تعداد اشیا‬
‫‪ W = 5‬ظرفیت کوله پشتی‬
‫وزن‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫ارزش‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫‪6‬‬
‫‪for i = 0 to n‬‬
‫‪B[0][ i] = 0‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫‪i‬‬
‫‪W‬‬
‫‪0‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
0
0
0
‫مثال‬
i=1
pi=3
wi=2
w=1
w-wi =-1
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
0
0
0
‫مثال‬
i=1
pi=3
wi=2
w=2
w-wi =0
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
0
0
0
‫مثال‬
i=1
pi=3
wi=2
w=3
w-wi=1
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
0
0
0
‫مثال‬
i=1
pi=3
wi=2
w=4
w-wi=2
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
0
‫مثال‬
i=1
pi=3
wi=2
w=5
w-wi=2
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
0
0
‫مثال‬
i=2
pi=4
wi=3
w=1
w-wi=-2
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
0
0
‫مثال‬
i=2
pi=4
wi=3
w=2
w-wi=-1
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
0
0
‫مثال‬
i=2
pi=4
wi=3
w=3
w-wi=0
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
0
0
‫مثال‬
i=2
pi=4
wi=3
w=4
w-wi=1
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
‫مثال‬
i=2
pi=4
wi=3
w=5
w-wi=2
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
3
4
0
‫مثال‬
i=3
pi=5
wi=4
w=1..3
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
3
4
5
0
‫مثال‬
i=3
pi=5
wi=4
w=4
w- wi=0
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
3
4
5
7
0
‫مثال‬
i=3
pi=5
wi=4
w=5
w- wi=1
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
3
4
5
7
0
0
3
4
5
‫مثال‬
i=4
pi=6
wi=5
w=1..4
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
i
W
0
1
2
3
4
5
0
1
2
3
4
0
0
0
0
0
0
0
0
3
3
3
3
0
0
3
4
4
7
0
0
3
4
5
7
0
0
3
4
5
7
‫مثال‬
i=4
bi=6
wi=5
w=5
if wi <= w // item i can be part of the solution
if pi + B[w-wi][i-1] > B[w][i-1]
B[w][i] = pi + B[w- wi][i-1]
else
B[w][i] = B[w][i-1]
else B[w][i] = B[w][i-1] // wi > w
Items:
1: (2,3)
2: (3,4)
3: (4,5)
4: (5,6)
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
‫طوالنی ترین زیررشته مشترک )‪(LCS‬‬
‫‪ ‬در مسائل بیولوژیک‪ ،‬اغلب به دنبال مقایسه ‪ DNA‬دو موجود متفاوت‬
‫هستند‪.‬‬
‫‪ ‬یک ‪ DNA‬را می توان با رشته ای شامل حروف زیر نشان داد‪:‬‬
‫‪{A, C, G, T} ‬‬
‫‪ ‬هدف‪ :‬تعیین میزان شباهت دو ‪ DNA‬می باشد‪.‬‬
‫‪ ‬یافتن زیردنباله ای که حروف آن با یک ترتیب مشابه اما نه لزوماً پیوسته در‬
‫هر دو رشته موجود باشد‪.‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫زیر رشته (توالی یا دنباله) مشترک‬
‫ مثال‬
S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA
S3 = GTCGTCGGAAGCCGGCCGAA
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
‫مسئله ‪longest common subsequence‬‬
‫‪ ‬مسئله یافتن یکی از طوالنی ترین زیرتوالی های مشترک بین دو رشته زیر‬
‫می باشد‪:‬‬
‫‪x[1.. m] ‬‬
‫‪y[1..n] ‬‬
‫‪B‬‬
‫‪A‬‬
‫‪D‬‬
‫‪x: A B C B‬‬
‫)‪BCBA = LCS(x,y‬‬
‫‪A‬‬
‫‪B‬‬
‫‪y: B D C A‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫الگوریتم ‪Brute-force‬‬
‫‪ ‬بررسی اینکه آیا زیررشته های ]‪ x[1..m‬زیررشته ]‪ y[1..n‬هم هستند یا‬
‫خیر‬
‫‪ ‬تحلیل پیچدگی زمانی‬
‫‪ ‬یافتن زیررشته ها‪o(2m) :‬‬
‫‪ ‬بررسی زیررشته ها‪ o(n) :‬برای هر زیررشته‬
‫‪ ‬هزینه الگوریتم‪ o(n 2m) :‬از درجه نمایی‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫برنامه نویسی پویا‬
‫‪ ‬تعریف‪ :‬طول یک رشته را با |‪ |s‬نمایش می دهیم‪.‬‬
‫‪ ‬راه حل‪ :‬توجه به پیشوندهای ‪ x‬و ‪y‬‬
‫‪ ‬یافتن طوالنی ترین زیررشته مشترک بین پیشوندها‬
‫|)]‪C[i,j] = |LCS(x[1..i], y[1..j‬‬
‫|)‪C[m,n] = |LCS(x,y‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫رابطه بازگشتی‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫روش ‪divide and conquer‬‬
‫‪ ‬بدترین حالت زمانی است که ]‪x[i] ≠ y[j‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫درخت بازگشت‬
‫‪m+n‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫درخت بازگشت‬
‫‪Dynamic Programming‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫الگوریتم به روش برنامه نویسی پویا‬
LCS-Length(X, Y)
1. m = length(X)
// get the # of symbols in X
2. n = length(Y)
// get the # of symbols in Y
3. for i = 1 to m c[i,0] = 0
// special case: Y0
4. for j = 1 to n
c[0,j] = 0
// special case: X0
5. for i = 1 to m
// for all Xi
6.
for j = 1 to n
// for all Yj
7.
if ( Xi == Yj )
8.
c[i,j] = c[i-1,j-1] + 1
9.
else c[i,j] = max( c[i-1,j], c[i,j-1] )
10. return c
‫ بیدکی‬:‫ مدرس‬- ‫ روش برنامه نویسی پویا‬:‫ فصل سوم‬- ‫درس طراحی الگوریتمها‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪i‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪B‬‬
‫‪2‬‬
‫‪C‬‬
‫‪3‬‬
‫‪B‬‬
‫‪4‬‬
‫‪X = ABCB; m = |X| = 4‬‬
‫‪Y = BDCAB; n = |Y| = 5‬‬
‫]‪Allocate array c[5, 6‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪c[i,0] = 0‬‬
‫‪c[0,j] = 0‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫‪i‬‬
‫‪for i = 1 to m‬‬
‫‪for j = 1 to n‬‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪x: ABCB‬‬
‫‪y: BDCAB‬‬
‫‪i‬‬
‫) ‪if ( Xi == Yj‬‬
‫‪c[i,j] = c[i-1,j-1] + 1‬‬
‫) ]‪else c[i,j] = max( c[i-1,j], c[i,j-1‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫یافتن رشته مشترک‬
‫‪ ‬تا االن فقط طول زیررشته بدست آمده است‬
‫‪ ‬برای یافتن خود زیررشته‪:‬‬
‫‪ ‬هر ]‪ c[i,j‬به ]‪ c[i, j-1] ،c[i-1, j‬و]‪ c[i-1, j-1‬وابسته است‬
‫‪ ‬از ]‪ c[m,n‬شروع کرده و هر جا ‪ +1‬داشتیم یعنی ]‪ x[i‬جزیی از زیررشته‬
‫است‪.‬‬
‫‪c[i,j] = c[i-1,j-1] +1 = 2+1=3‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫‪2‬‬
‫‪2‬‬
‫‪3‬‬
‫‪2‬‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪j‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪i‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫‪5‬‬
‫‪B‬‬
‫‪4‬‬
‫‪A‬‬
‫‪3‬‬
‫‪C‬‬
‫‪2‬‬
‫‪D‬‬
‫‪1‬‬
‫‪B‬‬
‫‪0‬‬
‫‪Yj‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪j‬‬
‫‪i‬‬
‫‪Xi‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪C‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪B‬‬
‫‪4‬‬
‫‪B C B‬‬
‫‪LCS :‬‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬
‫مثال‬
‫درس طراحی الگوریتمها ‪ -‬فصل سوم‪ :‬روش برنامه نویسی پویا ‪ -‬مدرس‪ :‬بیدکی‬

similar documents