الگوریتم حریصانه: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Iamalibabaei (بحث | مشارکتها) بدون خلاصۀ ویرایش |
Iamalibabaei (بحث | مشارکتها) بدون خلاصۀ ویرایش برچسب: متن دارای ویکیمتن نامتناظر |
||
خط ۵۰:
روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنبالهای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنبالهای از کارهاست که جواب بهینه را به ما میدهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیهتر به دنباله خودمان پیدا میکنیم که بهینه باشد و سرانجام دنبالهای که پیدا کردیم با دنباله ما یکسان میشود.
میزان شباهت دنباله <math>\mathit{E}=e_1,e_2,...,e_3</math> و <math>\mathit{F}=f_1,f_2,...,f_3</math> را بزرگترین اندیسی مثل <math>\mathit{x}</math> در نظر میگیریم که <math>\forall_{\mathit{y}< \;\mathit{x}}:e_y=f_y</math>
درواقع شباهت دو دنباله بزرگترین عددی مثل <math>\mathit{x}</math> است که <math>\mathit{x}</math> عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
|