آشنایی با طراحی الگوریتم ها

[K A S R A]

الگوریتم ... یعنی قلب تپنده نرم افزار . به جرات میشه گفت : بحث طراحی الگوریتم مهمترین قسمت علم مهندسی نرم افزاره ...
به زبان ساده : طراحی الگوریتم , تکنیک ها و روش های حل مسئله .
یه مثال جالب : برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
مسئله فروشنده دوره گرد یکی از مسائل معروف و NP Compelete ( دسته ای از مسائل که هنوز هیچ راه حل کار آمدی برای حل کردنشون وجود نداره اما غیر ممکن بودن حل این دسته از مسائل هنوز اثبات نشده )
هست ... که با یه مدلسازی ساده میشه خیلی از مسائل کامپیوتری NP Compelete رو با این مسئله هم ارز در نظر گرفت ... برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
صورت مسئله :
یه فرو شنده قصد داره یرای فروش اجناسش از تعدادی شهر (n شهر ) , که هر شهر با چندین شهر دیگه بوسیله یه جاده وصل شده , سفر کنه . در ضمن فروشنده باید از شهر خودش شروع به حرکت کنه , از همه شهرها یه بار عبور کنه و دوباره به جای اولش برگرده .
هدف : حداقل کردن زمان سفره . یعنی یافتن کوتاهترین مسیر برای سفر (البته با شرایط بالا) ...
این مسئله به ظاهر ساده میتونه قویترین Super Computer ها رو به زانو در بیاره ... برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
اگر فرض کنیم حافظه ی کافی در اختیار داریم ... برای n = 60 ( تعداد شهرها)
بهترین و بهینه ترین الگوریتمی که تاکنون برای حل این مسئله پیشنهاد شده به مدت زمانی در حدود 3857 سال زمان بر روی قویترین Super Computer برای حل احتیاج داره ...
البته همین روش , برای زمانی که n=40 باشه در حدود 45 ثانیه و روی یک Pc معمولی کارو تموم میکنه ...
در صورتی که یک الگوریتم نا کار آمد برای n = 20 هم به سالها زمان برای یافتن پاسخ احتیاج داره
اهمیت طراحی الگوریتم اینجا مشخص میشه ...

موفق باشید
کسری
برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید