Difference between revisions of "الگوریتم حریصانه"

Tag: متن دارای ویکی‌متن نامتناظر
Tags: متن دارای ویکی‌متن نامتناظر Visual edit
== روش اثبات درستی ==
هرچند روش یکتایی برای اثبات درستی الگوریتم حریصانه وجود ندارد ولی روش زیر در خیلی از مواقع الگوریتم را اثبات می‌کند.
روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کردهمی‌کنیم که با دنبالهدنبالهٔ ساخته شده یکسان باشد (منظور از دنبالهدنبالهٔ بهینه، دنباله‌ای از کار‌هاستکار‌ها می‌باشد که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته،می‌گیریم و در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنبالهدنبالهٔ ما یکسان می‌شود.
 
میزان شباهت دنباله <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> عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
 
 
108

edits