Algorythm Design (6)

‫برنامه نویسی پویا‬ ‫‪Dynamic Programming‬‬ ‫طراحی الگوریتم ها ‪ -‬دانشگاه فردوسی مشهد ‪ -‬صمد‬ ‫پایدار‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬

‫مقدمه‬ ‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫زنجیره ضرب ماتریس ها‬ ‫کوله پشتی صفر و یک‬ ‫ویرایش رشته ها‬ ‫فروشنده دوره گرد‬ ‫‪...‬‬

‫روش حریصانه‬

‫‪2‬‬

‫مقدمه‬ ‫‪‬‬

‫شبیه روش تقسیم و حل است‪.‬‬ ‫‪‬‬

‫در تقسیم و حل مساله را به تعدادی زیرمساله‬ ‫کوچکتر تقسیم می کنیم و آن زیرمسائل را حل کرده‬ ‫و با ترکیب جواب آنها‪ ،‬جواب مساله اصلی را بدست‬ ‫می آوریم‪.‬‬ ‫‪‬‬

‫‪‬‬

‫یک روال بال به پایین‬

‫اگر زیرمسائل بهم مربوط باشند‪ ،‬معمول کارآیی‬ ‫خیلی پایین می آید‬ ‫‪‬‬ ‫‪‬‬

‫بخاطر حل مکرر زیرمسائل مشابه‬ ‫مثال‪ :‬الگوریتم فیبوناتچی مبتنی بر روش تقسیم و حل‪ ،‬با‬ ‫مرتبه زمانی نمایی‬

‫روش حریصانه‬

‫‪3‬‬

‫مقدمه‬ ‫‪‬‬

‫در روش پویا‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫برای حل یک مساله باید تعدادی زیرمساله کوچکتر را حل کنیم‪.‬‬ ‫تمام کوچکترین مسائل را حل می کنیم و جواب آنها را ذخیره‬ ‫می کنیم‪.‬‬ ‫سپس به سطح بعد می رویم و تمام مسائل آن را حل می‬ ‫کنیم‪.‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫تمام مسائل را حل می کنیم‪.‬‬ ‫یک تفاوت با تقسیم و حل‪ :‬مثل در جستجوی دودویی تمام زیرمسائل را‬ ‫حل نمی کردیم‪.‬‬

‫در حل مسائل هر سطح‪ ،‬از جواب مسائل تمام سطح های قبل‬ ‫استفاده می کنیم )عدم نیاز به محاسبه مجدد و حل مکرر(‪.‬‬ ‫نهایتا به مساله اصلی می رسیم و با حل آن کار تمام می‬ ‫شود‪.‬‬

‫روش حریصانه‬

‫‪4‬‬

‫مقدمه‬ ‫‪‬‬

‫ویژگی های اغلب مسائلی که با این روش‬ ‫حل می شوند‬ ‫‪‬‬

‫‪‬‬

‫برای حل یک نمونه از مساله باید تعدادی نمونه‬ ‫دیگر با اندازه کوچکتر را حل کرد‪.‬‬ ‫موضوع بهینه سازی مطرح است‪ .‬یعنی باید‬ ‫بهترین جواب از بین جواب های ممکن را پیدا‬ ‫کنیم‪.‬‬

‫روش حریصانه‬

‫‪5‬‬

‫مقدمه‬ ‫‪‬‬

‫اصل بهینگی )‪(Principle of optimality‬‬ ‫صدق می کند‪.‬‬ ‫‪‬‬

‫‪‬‬

‫اگر بدست آوردن جواب بهینه مساله اصلی‪،‬‬ ‫مستلزم بدست آوردن جواب بهینه هر یک از‬ ‫زیرمسائل باشد‪ ،‬آنگاه اصل بهینگی در مورد‬ ‫مساله صدق می کند‪.‬‬ ‫به بیان دیگر‪ ،‬جواب بهینه مساله اصلی‪ ،‬شامل‬ ‫جواب بهینه زیرمسائل باشد‪.‬‬

‫روش حریصانه‬

‫‪6‬‬

‫مقدمه‬ ‫‪‬‬

‫مثال‪ :‬پیدا کردن کوتاهترین مسیر بین دو‬ ‫شهر ‪ A‬و ‪ C‬که از شهر ‪ B‬بگذرد‪.‬‬ ‫‪‬‬

‫‪‬‬

‫باید ابتدا کوتاهترین مسیر بین ‪ A‬و ‪ B‬را پیدا کرده‬ ‫و سپس کوتاهترین مسیر بین ‪ B‬و ‪ C‬را نیز پیدا‬ ‫کنیم و با ترکیب آنها کوتاهترین مسیر بین ‪ A‬و ‪C‬‬ ‫را بدست آوریم‪.‬‬ ‫اصل بهینگی صدق می کند ‪ ‬به احتمال زیاد‬ ‫مساله را می توان به روش پویا حل کرد‪.‬‬

‫روش حریصانه‬

‫‪7‬‬

‫مقدمه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫مثال‪ :‬پیدا کردن بلندترین مسیر بدون حلقه از ‪ V1‬به ‪V4‬‬ ‫جواب مساله‪[V1, V3, V2, V4] :‬‬ ‫اگر مساله را به دو زیرمساله تقسیم کنیم‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫پیدا کردن بلندترین مسیر بدون حلقه از ‪ V1‬به ‪V3‬‬ ‫پیدا کردن بلندترین مسیر بدون حلقه از ‪ V3‬به ‪1 V4‬‬ ‫جواب زیرمساله اول‪[V1, V2, V3] :‬‬ ‫جواب زیرمساله دوم‪[V3, V2, V4] :‬‬ ‫‪V3‬‬ ‫ترکیب جوابهای بهینه زیرمسائل‪:‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫[‪]V1, V2, V3, V2, V4‬‬ ‫حلقه دارد ‪ ‬این جواب مساله اصلی نیست‪.‬‬

‫‪V1‬‬

‫‪1‬‬ ‫‪2‬‬ ‫‪V2‬‬ ‫‪3‬‬

‫با ترکیب حواب بهینه زیرمسائل‪ ،‬جواب بهینه مساله اصلی بدست‪4‬‬ ‫نیامد‪.‬‬ ‫در نتیجه اصل بهینگی در مورد این مساله صدق نمی کند‪.‬‬ ‫‪V4‬‬

‫روش حریصانه‬

‫‪8‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫زنجیره ضرب ماتریس ها‬ ‫کوله پشتی صفر و یک‬ ‫ویرایش رشته ها‬ ‫فروشنده دوره گرد‬ ‫‪...‬‬

‫روش حریصانه‬

‫‪9‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫ضرب چند ماتریس‬ ‫‪M = M1 * M2 * M3‬‬ ‫دو ماتریس در صورتی قابل ضرب هستند که‬ ‫تعداد ستونهای ماتریس اول با تعداد سطرهای‬ ‫ماتریس دوم برابر باشد‪.‬‬ ‫ضرب ماتریس ها شرکت پذیر است‪.‬‬ ‫فقط می توانیم ماتریس های مجاور را در هم‬ ‫ضرب کنیم‪.‬‬ ‫اگر ‪ M1‬دارای ‪ i‬سطر و ‪ j‬ستون و ‪ M2‬دارای ‪j‬‬ ‫ستون و ‪ k‬سطر باشد‪ ،‬آنگاه ماتریس ‪،M1*M2‬‬ ‫دارای ‪ i‬سطر و ‪ k‬ستون خواهد بود‪.‬‬ ‫روش حریصانه‬

‫‪10‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫الگوریتم معمولی برای ضرب ماتریس ها مرتبه‬ ‫زمانی ‪ (O(n3‬داشت ‪ ‬تعداد ضرب ها زیاد‬ ‫اگر بخواهیم زنجیره ای از ماتریس ها را در هم‬ ‫ضرب کنیم‪ ،‬می توانیم این کار را به ترتیب‬ ‫های مختلفی انجام دهیم‬ ‫مثال‪M1*M2*M3 :‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫ترتیب اول‪(M1*(M2*M3 :‬‬ ‫ترتیب دوم‪M1*M2)*M3) :‬‬

‫در ترتیب های مختلف‪ ،‬تعداد اعمال ضرب‬ ‫صورت گرفته ممکن است تفاوت قابل توجهی‬ ‫داشته باشند‪.‬‬ ‫روش حریصانه‬

‫‪11‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪M4‬‬

‫‪‬‬

‫مثال‪ :‬محاسبه ‪M1*M2*M3*M4‬‬

‫‪‬‬

‫یک ترتیب ممکن ‪( (M1 * (M2 * (M3 *M4‬‬

‫‪M3‬‬

‫‪M2‬‬

‫‪M1‬‬

‫‪20*10 50*20 1*50 100*1‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪ X = M3*M4 ‬تعداد ضرب ‪ 5000= 100*1*50 :‬حاصل‪ :‬ماتریس‪100*50‬‬ ‫‪ M2 * (X) Y = ‬تعداد ضرب‪ 100000= 100*50*20 :‬حاصل‪ :‬ماتریس‪100*20‬‬ ‫‪ M1 * Y ‬تعداد ضرب‪ 20000= 100*20*10 :‬حاصل‪ :‬ماتریس‪100*10‬‬ ‫مجموع تعداد ضرب های انجام شده‪ 125000 :‬ضرب‬

‫یک ترتیب ممکن )‪M1 * (M2 * M3) ) * M4‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪ X = M2*M3 ‬تعداد ضرب ‪ 1000= 1*50*20 :‬حاصل‪ :‬ماتریس‪1*20‬‬ ‫‪ M1 * (X) Y = ‬تعداد ضرب‪ 200= 1*20*10 :‬حاصل‪ :‬ماتریس‪1*10‬‬ ‫‪ Y*M4 ‬تعداد ضرب‪ 1000= 100*1*10 :‬حاصل‪ :‬ماتریس‪100*10‬‬ ‫مجموع تعداد ضرب های انجام شده‪ 2200 :‬ضرب‬

‫روش حریصانه‬

‫‪12‬‬

‫زنجیره ضرب ماتریس ها‬ M = M1 * M2 * … * Mn M = M1 * (M2 * … * Mn) M = (M1 * M2) * (M3 * … * Mn) M = (M1 * M2 * M3) * (M4 * … * Mn) … M = (M1 * … * Mn-1) * Mn M = (M1 * M2 * … * Mi) * (Mi+1 * Mi+2 * … Mn) n −1

F(n ) = ∑ F(i).F(n − i)

:‫تعداد ترتیب های مختلف‬

1

13

‫روش حریصانه‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫تعداد ترتیب های مختلف‪ :‬اعداد کاتالن‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫رشد بسیار سریع‬ ‫‪F(5)=14‬‬ ‫‪F(10)=4862‬‬ ‫‪F(15)=2674460‬‬

‫روش حریصانه‬

‫‪14‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫صورت مساله‪ :‬تعیین ترتیب بهینه ضرب زنجیره ای ‪n‬‬ ‫ماتریس‬ ‫آیا اصل بهینگی صدق می کند؟‬ ‫بله‬ ‫بطور مثال‪ ،‬اگر ترتیب بهینه ‪ M1*M2*M3*M4‬به شکل‬ ‫))‪(M1 * ((M2 * (M3 * M4‬‬ ‫باشد‪ ،‬آنگاه ترتیب بهینه ‪ M2*M3*M4‬به شکل زیر می‬ ‫باشد‪.‬‬ ‫)‪M2 * (M3 * M4‬‬ ‫روش حریصانه‬

‫‪15‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫راه حل‪:‬‬ ‫‪‬‬ ‫‪‬‬

‫ابعاد ماتریس ‪ Mi : ri-1 * ri‬که ‪i=1,…,n‬‬ ‫‪ mi,j‬تعداد حداقل اعمال ضرب لزم برای محاسبه ‪:‬‬

‫‪,1≤i≤j≤n‬‬ ‫‪‬‬

‫اگر ‪ i=j‬باشد ‪mi,j =0‬‬

‫‪‬‬

‫در غیر اینصورت‬

‫‪Mi * Mi+1 * ... * Mj‬‬

‫) ‪mi,j = min ( mi,k + mk+1,j + ri-1 * rk * rj‬‬

‫‪‬‬

‫‪i≤k≤j‬‬ ‫‪‬‬

‫باید ‪ m1,n‬را بدست آوریم )حداقل تعداد اعمال ضرب‬ ‫لزم(‬ ‫روش حریصانه‬

‫‪16‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫‪‬‬

‫از یک آرایه دو بعدی برای ذخیره ‪ mi,j‬استفاده می‬ ‫کنیم‪.‬‬ ‫مراحل انجام کار )حل زیرمسائل کوچکتر(‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫مرحله ‪ :0‬تعداد ‪ 0‬عمل ضرب ماتریسی ‪ ‬قرار دادن‬ ‫صفر در ‪ mi,i‬که ‪i=1,...,n‬‬ ‫مرحله ‪ :1‬تعداد ‪ 1‬عمل ضرب ماتریسی ‪ ‬محاسبه ‪mi,i+1‬‬ ‫‪،i=1,..,n-1‬‬ ‫مرحله ‪ :2‬تعداد ‪ 2‬عمل ضرب ماتریسی ‪ ‬محاسبه ‪mi,i+2‬‬ ‫‪،i=1,..,n-2‬‬ ‫‪...‬‬ ‫مرحله ‪ :n-1‬تعداد ‪ n-1‬عمل ضرب ماتریسی ‪ ‬محاسبه‬ ‫‪m1,n‬‬

‫روش حریصانه‬

‫‪17‬‬

‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬

‫مثال‪ :‬محاسبه‬ ‫‪M1*M2*M3*M4‬‬

‫حداقل تعداد ضرب‬ ‫های لزم‬

‫‪M4‬‬

‫‪M3‬‬

‫‪M2‬‬

‫‪M1‬‬

‫‪100*1‬‬

‫‪1*50‬‬

‫‪50*20‬‬

‫‪20*10‬‬

‫‪2200‬‬

‫‪1200‬‬

‫‪m‬‬ ‫‪10000‬‬

‫‪3000‬‬

‫‪1000‬‬

‫‪0‬‬

‫‪5000‬‬

‫‪0‬‬

‫‪0‬‬

‫‪0‬‬

‫روش حریصانه‬

‫‪18‬‬

‫زنجیره ضرب ماتریس ها‬ int minCost(int n) { for(i=1; i<=n; i++) m[i][i]=0;

‫الگوریت‬ ‫م‬

for(l=1; l
‫روش حریصانه‬



‫زنجیره ضرب ماتریس ها‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫مرتبه زمانی‬ ‫با توجه به الگوریتم‪ ،‬دو حلقه تودرتو داریم‪،‬‬ ‫هر یک با مرتبه زمانی ‪.(O(n‬‬ ‫در داخل حلقه هم عمل مینیمم گیری انجام‬ ‫می شود که مرتبه زمانی آن هم ‪ (O(n‬است‬ ‫در نتیجه مرتبه زمانی کل الگوریتم‪(O(n3 :‬‬

‫روش حریصانه‬

‫‪20‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫زنجیره ضرب ماتریس ها‬ ‫کوله پشتی صفر و یک‬ ‫ویرایش رشته ها‬ ‫فروشنده دوره گرد‬ ‫‪...‬‬

‫روش حریصانه‬

‫‪21‬‬

‫کوله پشتی صفر و یک‬ ‫‪ ‬شبیه مساله کوله پشتی غیر صفر و یک می باشد با‬ ‫این تفاوت که یک شیء را یا باید بطور کامل انتخاب‬ ‫کنیم یا اصل انتخاب نکنیم‪.‬‬ ‫‪ ‬انتخاب کسری از شیء مجاز نمی باشد‪.‬‬ ‫‪ ‬برای کوله پشتی غیر صفر و یک‪ ،‬الگوریتمی مبتنی‬ ‫بر روش حریصانه ارائه شد‪.‬‬ ‫‪ ‬این الگوریتم برای کوله پشتی صفر و یک قابل‬ ‫استفاده نمی باشد‪.‬‬ ‫‪ ‬مثال نقض‪M=20 :‬‬ ‫)‪(W1 , W2 , W3) = (18 , 15 , 10‬‬ ‫)‪(P1 , P2 , P3) = (25 , 24 , 15‬‬ ‫جواب کوله پشتی غیر صفر و یک ‪ (1/2 ,1 ,0) :‬ارزش‪:‬‬ ‫‪31.5‬‬ ‫روش حریصانه‬

‫‪22‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬

‫جواب حاصل از استفاده از الگوریتم حریصانه‬ ‫برای این مثال‪:‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫)‪ (0 , 1 , 0‬ارزش‪24 :‬‬

‫جواب بهینه برای این مثال‪(0 , 1 , 0) :‬‬ ‫ارزش‪24 :‬‬ ‫در نتیجه الگوریتم حریصانه ارائه شده‪ ،‬برای‬ ‫کوله پشتی صفر و یک مناسب نیست‪.‬‬

‫روش حریصانه‬

‫‪23‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬

‫از یک منظر دیگر‪ ،‬مساله کوله پشتی صفر و یک‬ ‫معادل است با‬ ‫‪‬‬

‫‪‬‬

‫انتخاب زیرمجموعه ای از اشیا که مجموع ارزش آنها‬ ‫ماکزیمم شود و مجموع وزن آنها از ظرفیت کوله‬ ‫پشتی تجاوز نکند‪.‬‬

‫از این منظر‪:‬‬ ‫‪‬‬

‫یک مجموعه ‪ n‬عضوی دارای ‪ 2n‬زیرمجموعه است ‪‬‬ ‫یک راه حل‪ :‬بررسی تمام حالت ممکن‬

‫‪‬‬

‫روش ‪ :brute-force‬مرتبه زمانی ‪(O(2n‬‬ ‫اما با استفاده از روش پویا‪ ،‬بدنبال روش بهتری‬ ‫هستیم‪.‬‬ ‫آیا اصل بهینگی صدق می کند؟‬

‫‪‬‬

‫‪‬‬

‫روش حریصانه‬

‫‪24‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫تعریف نماد ‪ [P[i][w‬که ‪ i>0‬و ‪w>0‬‬ ‫‪]P[i][w‬برابر است با بیشترین ارزش ممکن‬ ‫برای کوله پشتی وقتی که آنرا با زیرمجموعه‬ ‫ای از‪i‬شیء اول پر کنیم و کوله پشتی را‬ ‫حداکثر تا ظرفیت‪.w‬پر کنیم‬ ‫اگر کوله پشتی را با انتخاب اشیا از بین ‪i‬‬ ‫شیء اول پر کنیم‪ ،‬طوری که مجموع وزن‬ ‫اشیا از ‪ w‬بیشتر نشود و ضمنا مجموع ارزش‬ ‫اشیا حداکثر شود‪ ،‬حداکثر ارزش بدست آمده‬ ‫را با ‪ [P[i][w‬نشان می دهیم‪.‬‬ ‫روش حریصانه‬

‫‪25‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬

‫طبق مفهوم ‪ [P[i][w‬خواهیم داشت‬ ‫‪if w‬‬

‫‪‬‬

‫} ‪max { P[i-1][w] , P[i-1][w-wi]+Pi‬‬ ‫‪P[i][w]= ≥ wi‬‬ ‫]‪P[i-1][w‬‬ ‫‪if w < wi‬‬

‫مساله اصلی پیدا کردن ‪ [P[n][M‬است‪.‬‬ ‫‪‬‬

‫البته این فقط بیشترین ارزش ممکن برای پر کردن کوله‬ ‫پشتی می باشد و باید ‪ Xi‬ها را هم محاسبه کنیم‪.‬‬

‫روش حریصانه‬

‫‪26‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫روش کار‪ :‬استفاده از یک آرایه دو بعدی ‪ n*M‬برای‬ ‫‪ P‬و محاسبه تمام عناصر آن تا نهایتا ‪ [P[n][M‬را‬ ‫بدست آوریم‪.‬‬ ‫این کار مرتبه زمانی ‪ (O(n.M‬خواهد داشت‪.‬‬ ‫اگر ‪ M‬خیلی بزرگ باشد‪ ،‬مثل ‪ M>2n‬باشد آنگاه‬ ‫مرتبه زمانی این الگوریتم از الگوریتم ‪brute-‬‬ ‫‪ force‬هم بدتر خواهد شد ‪ ‬قابل قبول نیست‪.‬‬ ‫روش بهتر‪ :‬با توجه به رابطه صفحه قبل‪ ،‬واضح‬ ‫است که برای محاسبه هر عنصر ‪ P‬نهایتا‪ ،‬به دو‬ ‫عنصر دیگر ‪ P‬نیاز داریم‪ .‬بنابراین فقط عناصر لزم‬ ‫را محاسبه می کنیم‪.‬‬ ‫روش حریصانه‬

‫‪27‬‬

‫کوله پشتی صفر و یک‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫اول می خواهیم ‪ [P[n][M‬را بدست آوریم‪ .‬برای‬ ‫این کار باید ‪ [P[n-1][M‬و همچنین ‪[P[n-1][M-wn‬‬ ‫را بدست آوریم و ‪...‬‬ ‫یک درخت دودویی‬ ‫اجرای مثال قبل با استفاده از این روش‬ ‫‪‬‬

‫‪ M=20‬و ‪n=3‬‬

‫)‪(W1 , W2 , W3) = (18 , 15 , 10‬‬ ‫)‪(P1 , P2 , P3) = (25 , 24 , 15‬‬ ‫‪‬‬

‫نحوه پیدا کردن ‪ Xi‬ها ؟‬

‫‪‬‬

‫با این کار مرتبه زمانی الگوریتم ‪ (O(2n‬خواهد شد‪.‬‬ ‫روش حریصانه‬

‫‪28‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫زنجیره ضرب ماتریس ها‬ ‫کوله پشتی صفر و یک‬ ‫ویرایش رشته ها‬ ‫فروشنده دوره گرد‬ ‫‪...‬‬

‫روش حریصانه‬

‫‪29‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫دو رشته ‪ X‬و ‪ Y‬داریم‬

‫‪‬‬

‫می خواهیم با اجرای یک دنباله از اعمال ویرایشی‪،‬‬ ‫رشته ‪ X‬را به رشته ‪ Y‬تبدیل کنیم بطوریکه مجموع‬ ‫هزینه این اعمال حداقل گردد‪.‬‬ ‫اعمال ویرایشی مجاز‬

‫‪X = x1 x2 x3 … xn‬‬ ‫‪Y = y1 y2 y3 … ym‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪delete‬حذف یک کاراکتر از رشته ‪:‬‬ ‫‪insert‬درج یک کاراکتر در رشته ‪:‬‬ ‫‪change‬تعویض یک کاراکتر در رشته با یک کاراکتر دیگر ‪:‬‬

‫روش حریصانه‬

‫‪30‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫‪abbac‬‬

‫مثال‪ X=abbac :‬و ‪Y=abcbc‬‬

‫‪delete b‬‬

‫‪abcbc‬‬ ‫‪‬‬

‫‪change a to c‬‬

‫‪ababc‬‬

‫‪insert b‬‬

‫‪abac‬‬

‫آیا این راه حل بهینه است؟‬ ‫‪‬‬

‫به هزینه هر یک از اعمال ویرایشی بستگی دارد‪.‬‬ ‫‪ )D(xi‬هزینه حذف کاراکتر ‪xi:‬‬

‫‪‬‬

‫‪ )I(xi‬هزینه درج کاراکتر ‪xi:‬‬

‫‪‬‬

‫‪ )C(xi,yi‬هزینه تعویض کاراکتر ‪ xi:‬با کاراکتر‪yi‬‬

‫‪‬‬

‫روش حریصانه‬

‫‪31‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫اصل بهینگی؟‬ ‫‪K‬‬

‫‪Y‬‬ ‫‪n2‬‬ ‫‪‬‬

‫‪X‬‬ ‫‪n1‬‬

‫فرض کنیم دنباله ای شامل ‪ n‬عمل ویرایشی داریم که با‬ ‫حداقل هزینه‪ X ،‬را به ‪ Y‬تبدیل می کند‪ .‬می توانیم فرض‬ ‫کنیم که در حین این کار ابتدا با ‪ n1‬عمل ویرایشی اول‪X ،‬‬ ‫به ‪ K‬تبدیل می شود و سپس با استفاده از ‪ n2‬عمل‬ ‫ویرایشی دوم‪ K ،‬به ‪ Y‬تبدیل می شود‪ .‬در اینصورت واضح‬ ‫است که ‪ n1‬عمل ویرایشی اول‪ ،‬برای تبدیل ‪ X‬به ‪ K‬یک‬ ‫جواب بهینه می باشند و ‪ n2‬عمل ویرایشی دوم نیز‪ ،‬برای‬ ‫تبدیل ‪ K‬به ‪ Y‬یک جواب بهینه می باشند‪(n=n1+n2) .‬‬

‫روش حریصانه‬

‫‪32‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫نماد‪ :(cost(i,j‬حداقل هزینه برای تبدیل پیشوند ‪i‬‬ ‫کاراکتری ‪ X‬به پیشوند ‪ j‬کاراکتری از ‪Y‬‬ ‫‪‬‬

‫یعنی هزینه تبدیل ‪ x1x2x3…xi‬به ‪y1y2y3..yj‬‬

‫‪y1y2...yjyj+1 ...ym‬‬

‫‪‬‬

‫‪x1x2...xixi+1 ...xn‬‬

‫با توجه به مفهوم این نماد‪:‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪i=j=0‬‬ ‫اگر ‪ cost(i,j) = cost(0,0) = 0‬‬ ‫اگر ‪ i>0‬و ‪cost(i,j) = cost(i,0) = cost(i-1,‬‬ ‫‪(0) + D(xi‬‬ ‫اگر ‪ i=0‬و ‪cost(i,j) = cost(0,j) = cost(0,j-‬‬ ‫‪(1) + I(Yj‬‬

‫روش حریصانه‬

‫‪‬‬

‫‪j=0‬‬

‫‪‬‬

‫‪j>0‬‬ ‫‪33‬‬

‫ویرایش رشته ها‬ x1x2...xixi+1 ...xn

y1y2...yjyj+1 ...ym

:‫ آنگاه راه های ممکن‬j>0 ‫ و‬i>0 ‫اگر‬ 

cost(i,j) = cost(i-1,j) + D(xi)



cost(i,j) = cost(i,j-1) + I(yj)



cost(i,j) = cost(i-1,j-1) + C(xi,yi)



cost(i,j) = cost(i-1,j-1)

34

, if xi != yj , if xi == yj

‫روش حریصانه‬



‫ویرایش رشته ها‬ ‫‪‬‬

‫اگر ‪ i>0‬و ‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪ j>0‬سه روش کلی‬

‫ممکن است هزینه این روش ها یکسان نباشد‪.‬‬ ‫چون می خواهیم حداقل هزینه را پیدا کنیم‪ ،‬پس اگر‬ ‫‪ i>0‬و ‪ j>0‬آنگاه‬

‫{ ‪cost(i,j) = MIN‬‬ ‫‪cost(i-1,j) + D(xi) ,‬‬ ‫‪cost(i,j-1) + I(yi) ,‬‬ ‫)‪if(xi!=yj) cost(i-1,j-1) + C(xi,yi‬‬ ‫)‪else cost(i-1,j-1‬‬ ‫}‬ ‫روش حریصانه‬

‫‪35‬‬

‫ویرایش رشته ها‬ :‫فرمول کلی‬ if i = j = 0 0 cost(i - 1,0) + D(xi) if j = 0 , i > 0  cost(0, j - 1) + I(yj) if i = 0 , j > 0  cost(i, j) =  cost(i - 1, j) + D(xi) cost(i, j - 1) + I(yj)  MIN  if i > 0 , j > 0  if(xi!= yj) cost(i - 1, j - 1) + C(xi, yj)  else cost(i - 1, j - 1) 

36

‫روش حریصانه‬



‫ویرایش رشته ها‬ ‫‪‬‬

‫هدف‪ :‬اگر رشته ‪ X‬دارای ‪ n‬کاراکتر و رشته ‪ Y‬دارای ‪m‬‬ ‫کاراکتر باشد‪ ،‬باید ‪ (cost(n,m‬را پیدا کنیم‪.‬‬ ‫‪‬‬

‫‪‬‬

‫البته ‪ (cost(n,m‬یک مقدار است‪ ،‬علوه بر آن باید دنباله اعمال‬ ‫را نیز پیدا کنیم‪.‬‬

‫از آرایه دو بعدی ‪ cost‬استفاده می کنیم و عناصر آن را‬ ‫محاسبه می کنیم تا نهایتا مقدار ‪ [cost[n][m‬را بدست‬ ‫آوریم‪.‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫سطر اول را محاسبه می کنیم ‪ [cost[0][j‬و‪≥m 0≤j‬‬ ‫ستون اول را محاسبه می کنیم ‪ [cost[i][0‬و ‪i≤n≥0‬‬ ‫بقیه عناصر را سطر به سطر محاسبه می کنیم‪.‬‬ ‫آرایه )‪ (n+1)*(m+1‬عنصری‬

‫روش حریصانه‬

‫‪37‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫مثال‪ :‬تبدیل ‪ abc‬به ‪ cd‬با فرض اینکه هزینه‬ ‫تمام اعمال ویرایشی به ازای هر کاراکتر برابر‬ ‫‪ 1‬می باشد‪.‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫حداقل هزینه‪cost(3,2)=3 :‬‬ ‫دنباله اعمال ویرایشی لزم‪:‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪2‬‬

‫‪1‬‬

‫‪1‬‬

‫‪2‬‬

‫‪2‬‬

‫‪2‬‬

‫‪3‬‬

‫‪2‬‬

‫‪3‬‬

‫‪)delete(a‬‬ ‫‪)change(b,c‬‬ ‫‪)change(c,d‬‬ ‫البته در این مثال‪ ،‬دنباله ویرایشی بهینه یکتا نمی‬ ‫باشد‪.‬‬

‫روش حریصانه‬

‫‪38‬‬

‫ویرایش رشته ها‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫در این الگوریتم باید )‪ (n+1)*(m+1‬عنصر آرایه‬ ‫‪ cost‬را محاسبه کنیم‪.‬‬ ‫محاسبه هر عنصر‪ ،‬به تعداد ثابتی عمل نیاز دارد‬ ‫که با مرتبه زمانی ‪ (O(1‬قابل انجام است‪ .‬یعنی‬ ‫حجم اعمال لزم برای محاسبه هر عنصر آرایه‬ ‫‪ ،cost‬مستقل از ‪ n‬و ‪ m‬است‪.‬‬ ‫در نتیجه‪ ،‬مرتبه زمانی الگوریتم ‪ (O(n.m‬می‬ ‫باشد‪.‬‬

‫روش حریصانه‬

‫‪39‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫زنجیره ضرب ماتریس ها‬ ‫کوله پشتی صفر و یک‬ ‫ویرایش رشته ها‬ ‫فروشنده دوره گرد‬ ‫‪...‬‬

‫روش حریصانه‬

‫‪40‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫‪‬‬

‫‪TSP: Traveling Salesperson Problem‬‬ ‫یک فروشنده باید برای فروش اجناس خود‪ ،‬باید به‬ ‫تعدادی شهر برود و در نهایت هم به شهر خودش‬ ‫بازگردد‪ .‬فروشنده می خواهد کوتاهترین مسیر را‬ ‫پیدا کند بطوری که از هر شهر فقط یک بار بگذرد‪.‬‬ ‫استفاده از یک گراف جهت دار وزن دار برای مدل‬ ‫کردن مساله‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫گره های گراف‪ :‬شهر ها‬ ‫یالهای گراف‪ :‬جاده های ارتباطی بین شهرها‬ ‫وزن یالها‪ :‬طول مسیر بین دو شهر یا هزینه جابجایی بین‬ ‫دو شهری که گره های ابتدا و انتهای یال را مشخص می‬ ‫کنند‪.‬‬

‫روش حریصانه‬

‫‪41‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫گردش )‪(tour‬‬ ‫‪‬‬

‫‪‬‬

‫برای گراف جهت دار وزن دار ‪ G‬با ‪ n‬گره‪ ،‬یک‬ ‫گردش‪ ،‬مسیری است از یک گره به خود آن گره‪،‬‬ ‫بطوری که از هر یک از گره های دیگر‪ ،‬دقیقا یک‬ ‫بار بگذرد‪.‬‬

‫مساله ‪ TSP‬در واقع‬ ‫‪‬‬

‫پیدا کردن گردش بهینه )‪ (optimum tour‬می‬ ‫باشد‪ .‬یعنی گردشی که دارای کمترین هزینه ممکن‬ ‫باشد )البته به فرض اینکه حداقل یک گردش وجود‬ ‫داشته باشد(‬

‫روش حریصانه‬

‫‪42‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫اگر ‪ n‬شهر )‪ n‬گره( وجود داشته باشد )فرض‪ :‬گراف کامل متصل(‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫باید در هر گام یک شهر را انتخاب کرده و به آنجا برویم‪.‬‬ ‫ابتدا در گره مبدأ قرار داریم که این گره را با ‪ v1‬نشان می دهیم‪.‬‬ ‫در گام ‪) 1‬شروع حرکت( ‪ n-1‬گره قابل انتخاب می باشد‪ .‬کدام؟‬ ‫در گام ‪ n-2 ،2‬گره قابل انتخاب است‪ .‬کدام؟‬ ‫‪...‬‬ ‫در گام ‪ n-1 ،1‬گره قابل انتخاب است‪.‬‬ ‫در نتیجه‪ ،‬تعداد کل حالت ممکن )تعداد گردشهای ممکن( برابر است با‪:‬‬

‫!)‪(n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1 = (n-1‬‬ ‫‪‬‬

‫در واقع )‪ !(n-1‬گردش مختلف وجود دارد که باید از بین آنها کوتاهترین را‬ ‫انتخاب کنیم‪.‬‬

‫روش حریصانه‬

‫‪43‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫الگوریتم ‪ :brute-force‬بررسی تمام حالت ممکن‬ ‫‪‬‬

‫‪‬‬

‫(‪)!n-1‬گردش مختلف وجود دارد که باید طول هر کدام از آنها را‬ ‫‪.‬محاسبه کنیم و سپس کوتاهترین گردش را انتخاب کنیم‬ ‫برای محاسبه طول هر گردش‪ ،‬از آنجا که هر گردش شامل ‪ n‬یال است‪،‬‬ ‫باید طول ‪ n‬یال را با هم جمع کنیم‪.‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫واضح است که جمع ‪ n‬عدد با مرتبه زمانی ‪ (O(n‬انجام می شود‪.‬‬

‫پس‪ ،‬محاسبه طول )‪ !(n-1‬گردش‪ ،‬با مرتبه زمانی ‪ (!(O(n.(n-1‬قابل‬ ‫انجام است یعنی با مرتبه زمانی ‪(!O(n‬‬ ‫سپس باید کوتاهترین گردش را پیدا کنیم‪ ،‬که این هم با مرتبه زمانی‬ ‫‪ (!(O((n-1‬قابل انجام است‪.‬‬ ‫در نتیجه الگوریتم مرتبه زمانی ‪ ،brute-force‬برابر ‪ (!O(n‬می باشد‪.‬‬

‫روش حریصانه‬

‫‪44‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫‪‬‬

‫این مرتبه زمانی فقط برای ‪ n‬های خیلی‬ ‫کوچک قابل قبول است‪.‬‬ ‫مثل اجرای الگوریتم ‪ brute-force‬برای‬ ‫‪ ،n=20‬بر روی یک کامپیوتر معمولی‪ ،‬سالها‬ ‫طول می کشد‪.‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪1018 ≈ !20‬‬

‫آیا می توان الگوریتم بهتری‪ ،‬مبتنی بر برنامه‬ ‫نویسی پویا ارائه کرد؟‬ ‫آیا اصل بهینگی در مورد مساله صادق است؟‬ ‫‪‬‬

‫بله‬

‫روش حریصانه‬

‫‪45‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫‪V‬مجموعه تمام گره ها ‪:‬‬ ‫‪v1‬گره مبدأ ‪:‬‬

‫‪‬‬

‫هدف‪ :‬پیدا کردن کوتاهترین مسیری که از هر یک از گره‬ ‫های مجموعه ‪ {V-{v1‬یک بار می گذرد و سپس به ‪ v1‬ختم‬ ‫می شود‪.‬‬ ‫فرض کنیم به روشی‪ ،‬تشخیص داده ایم که اولین گره‬ ‫مسیر )بعد از ‪ (v1‬گره ‪ vk‬می باشد‪ .‬آنگاه برای تشخیص گره‬ ‫بعدی‪،‬‬ ‫باید کوتاهترین مسیری را پیدا کنیم که از هر یک از گره‬ ‫های مجموعه ‪ {V-{v1, vk‬یک بار بگذرد و به ‪ v1‬ختم شود‪.‬‬ ‫‪...‬‬ ‫مساله خاصیت بازگشتی دارد‪.‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫روش حریصانه‬

‫‪46‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫‪A‬را بعنوان مجموعه گره های انتخاب نشده‬ ‫در نظر می گیریم که در هر گام‪ ،‬گره بعدی را‬ ‫‪.‬باید از آن مجموعه انتخاب کنیم‬ ‫‪‬‬

‫‪‬‬

‫واضح است که ‪ A‬زیرمجموعه ‪ V‬است‪.‬‬

‫از ماتریس دوبعدی ‪ W‬بعنوان ماتریس‬ ‫مجاورت گراف استفاده می کنیم‪.‬‬ ‫‪‬‬

‫‪ ]W[i][j‬وزن یالی که از گره ‪ vi:‬به گره ‪.vj‬می رود‬

‫روش حریصانه‬

‫‪47‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫نماد ‪ : [D[vi][A‬طول کوتاهترین مسیری که از ‪vi‬‬ ‫شروع می شود و از هر یک از گره های مجموعه ‪A‬‬ ‫یک بار می گذرد و به ‪ v1‬ختم می شود‪.‬‬ ‫استخراج رابطه بازگشتی‬

‫‪‬‬

‫با توجه به مفهوم این نماد‪،‬‬

‫‪‬‬

‫∅ =!‪MIN { W[i][j] + D[v j ][A - {v j}]} if A‬‬ ‫‪D[vi ][A] =  v j∈A‬‬ ‫]‪W[i][1‬‬ ‫∅ = ‪if A‬‬

‫‪‬‬

‫هدف اصلی بدست آوردن ‪ [{D[v1][V-{v1‬می باشد‪.‬‬

‫‪ ‬البته این مقدار‪ ،‬فقط طول کوتاهترین گردش را مشخص‬ ‫می کند‪ ،‬سپس باید خود مسیر گردش را مشخص نمود‪.‬‬ ‫‪48‬‬ ‫روش حریصانه‬

‫فروشنده دوره گرد‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫‪‬‬ ‫‪‬‬

‫اگر از یک آرایه دو بعدی برای ذخیره مقادیر عناصر ‪ D‬استفاده کنیم‪.‬‬ ‫این آرایه دارای ‪ n‬سطر و ‪ 2n‬ستون خواهد بود‪.‬‬ ‫‪‬‬

‫‪‬‬

‫چرا ‪ :2n‬چون مجموعه ‪ n‬عضوی ‪ ،V‬دارای ‪ 2n‬زیرمجموعه می باشد‪.‬‬

‫پس بطور کلی تعداد عناصری که باید محاسبه کنیم برابر است با‬

‫‪n . 2n‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫البته در عمل برخی عناصر را محاسبه نمی کنیم‪.‬‬ ‫از طرفی در محاسبه هر عنصر‪ ،‬نیاز به مینیمم گیری می باشد که این‬ ‫مینیمم گیری با مرتبه زمانی ‪ (O(n‬انجام می شود‪.‬‬ ‫در نتیجه‪ ،‬مرتبه زمانی الگوریتم ارائه شده‪(O(n2.2n :‬‬ ‫مرتبه زمانی خیلی بد است‪ ،‬اما خیلی بهتر از الگوریتم ‪brute-force‬‬ ‫می باشد‪) .‬مثل برای ‪(n=20 ،n . 2n ≈108‬‬

‫روش حریصانه‬

‫‪49‬‬

‫فروشنده دوره گرد‬ ‫مثال‪:‬‬ ‫باید به محاسبه عناصر ‪ D‬برای ‪ A‬های مختلف‬ ‫‪V2‬‬ ‫بپردازیم‪.‬‬ ‫گام ‪ :1‬محاسبه حالت لزم برای زیرمجموعه‬ ‫‪8‬‬ ‫های ‪ 0‬عضوی‬ ‫‪4‬‬ ‫]‪D[v2][Ф] , D[v3][Ф] , D[v4][Ф‬‬ ‫گام ‪ :2‬محاسبه حالت لزم برای زیرمجموعه‬ ‫های ‪ 1‬عضوی‬ ‫‪V3‬‬ ‫]‪D[v2][v3], D[v2][v4], D[v3][v2], D[v3‬‬ ‫‪[v4],‬‬ ‫]‪D[v4][v2], D[v4][v3‬‬ ‫گام ‪ :3‬محاسبه حالت لزم برای زیرمجموعه‬ ‫های ‪ 2‬عضوی‬ ‫]‪D[v2][v3,v4], D[v3][v2,v4], D[v4‬‬ ‫]‪[v2,v3‬‬ ‫گام ‪ :4‬محاسبه حالت لزم برای زیرمجموعه‬ ‫های ‪ 3‬عضوی‬ ‫نهایی‬ ‫جواب‬ ‫]‪D[v1][v2,v3,v4‬‬

‫مساله‬

‫روش حریصانه‬

‫‪2‬‬ ‫‪V1‬‬

‫‪1‬‬ ‫‪5‬‬ ‫‪6‬‬

‫‪7‬‬

‫‪3‬‬ ‫‪V4‬‬

‫‪4‬‬

‫‪50‬‬

‫فروشنده دوره گرد‬ :W ‫ماتریس‬ 1 ‫یالها‬ 2 3‫وزن‬ 4

D[v2][Ф] = W[2][1] = 1 D[v3][Ф] = W[3][1] = ∞

1

0

2

∞

3

2

1

0

8

∞

3 ∞ 4 ==============================

0

6

4

0

D[v4][Ф] = W[4][1] = 7

4

D[v2][v3] = W[2][3] + D[3][Ф] = 8 + ∞ = ∞

7

5

D[v2][v4] = W[2][4] + D[4][Ф] = ∞ + 7 = ∞ D[v3][v2] = W[3][2] + D[2][Ф] = 4+1=5 D[v3][v4] = W[3][4] + D[4][Ф] = 6+7=13 D[v4][v2] = W[4][2] + D[2][Ф] = 5+1=6 D[v4][v3] = W[4][3] + D[3][Ф] = 4 + ∞ = ∞ 51

‫روش حریصانه‬

‫فروشنده دوره گرد‬ ‫]‪D[v2][v3,v4] = MIN { W[2][3] + D[v3][v4] , W[2][4]+D[v4][v3‬‬ ‫}‬ ‫‪= MIN { 21 , ∞ } = 21‬‬ ‫]‪D[v3][v2,v4] = MIN { W[3][2]+D[v2][v4] , W[3][4]+D[v4][v2‬‬ ‫}‬ ‫‪= MIN {∞ , 12 } = 12‬‬ ‫]‪D[v4][v2,v3] = MIN { W[4][2]+D[v2][v3] , W[4][3]+D[v3][v2‬‬ ‫}‬ ‫طول کوتاهترین‬ ‫‪= MIN {∞ , 9 } = 9‬‬ ‫مسیری که از ‪v1‬‬ ‫=====================================‬ ‫شروع شود و از هر‬ ‫یک از گره های ‪ v2‬و ==========================‬ ‫یک]‪D[v1][v2,v3,v4] = MIN { W[1][2] + D[v2][v3,v4‬‬ ‫‪ v3‬و ‪ v4‬دقیقا ‪,‬‬ ‫بار بگذرد و دوباره به‬ ‫‪W[1][3] + D[v3][v2,v4] ,‬‬ ‫‪52‬‬ ‫حریصانه‬ ‫ختم شود‪.‬‬ ‫روش‬ ‫‪v1‬‬

‫فروشنده دوره گرد‬ ‫‪‬‬ ‫‪‬‬

‫اما خود مسیر را چگونه بدست آوریم؟‬ ‫عدد ‪ 12‬از کدام ‪ term‬بدست آمد؟ از ]‪W[1][4] + D[v4‬‬ ‫‪[[v2,v3‬‬ ‫‪‬‬

‫‪‬‬

‫اما مقدار ‪ [D[v4][v2,v3‬از کدام ‪ term‬بدست آمد؟‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫از ‪ [W[4][3]+D[v3][v2‬که معادل حرکت از ‪ v4‬به ‪ v3‬است‪ .‬پس بعد از‬ ‫‪ v4‬باید به ‪ v3‬برویم‪.‬‬

‫اما مقدار ‪ [D[v3][v2‬از کدام ‪ term‬بدست آمد؟‬ ‫‪‬‬

‫‪‬‬

‫این ترم معادل حرکت از ‪ v1‬به ‪ v4‬است‪ .‬پس در اولین گام از‬ ‫‪ v1‬باید به ‪ v4‬برویم‪.‬‬

‫از ‪ [W[3][2] + D[2][Ф‬که معادل حرکت از ‪ v3‬به ‪ v2‬است‪ .‬پس‬ ‫باید از ‪ v3‬به ‪ v2‬برویم‪.‬‬

‫مقدار ‪ [D[2][Ф‬چطور بدست آمد؟ این مقدار برابر بود‬ ‫با ‪ [W[2][1‬یعنی حرکت از ‪ v2‬به ‪v1‬‬ ‫‪V1  V4  V3  V2  V1‬‬ ‫در نتیجه مسیر‬

‫روش حریصانه‬

‫‪53‬‬