بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
سوال اصلی
چه زمانی اجازه داره از الگوریتم های متا هیوریستیک استفاده کنیم؟
اسلاید 2 :
مساله (Problem)
یک سوال کلی که باید جواب داده شود.
مثال : مساله ی بهینه سازی فروشنده دوره گرد.
پارامترها (Parameters)
متغیرهای آزاد مساله که مقادیرشان نامعین قرار داده میشود.
مثال : مجموعه ای از شهرهای و مسافت بین هر زوج شهر و
اسلاید 3 :
تعریف مسئلهنمونه (Instance)
یک نمونه از یک مساله، با قرار دادن مقادیر معین برای تمام پارامترهای مساله بدست می آید.
مثال : ....
اسلاید 4 :
تعریف مسئلهمساله بهینه سازی فروشنده دوره گرد
طول ” تور“ی که از همه ی شهرها به ترتیب میگذرد و به شهر اول بر میگردد را حداقل کنید
اسلاید 5 :
تعریف الگوریتمالگوریتم (Algorithm)
یک الگوریتم یک رویه ی گام به گام (شامل توالی محدودی از دستورات) برای حل یک مساله است.
الگوریتمها با زمان چند جمله ای Polynomial Time Algorithms
الگوریتمها با زمان نمایی Exponential Time Algorithms
اسلاید 6 :
طول ورودی (Input length)
تعداد سمبلهای اطلاعات ورودی مورد نیاز برای توصیف یک نمونه مساله با استفاده از یک طرح کدگذاری منطقی.
بزرگترین عدد (Largest number)
اهمیت (بزرگی) بزرگترین عدد در یک نمونه مساله
تابع پیچیدگی زمانی (Time-complexity function)
بیان کننده ی زمان مورد نیاز الگوریتم است، توسط ارائه ی بیشترین زمان مورد نیاز الگوریتم برای حل نمونه مساله با همه طول ورودی های ممکن.
اسلاید 7 :
تعریف: به یک مساله رام نشدنی می گوییم اگر آنقدر سخت باشد که هیچ الگوریتم با زمان چندجمله ای نمی تواند آنرا حل کند.
الگوریتم با زمان چند جمله ای چیست ؟
اسلاید 8 :
الگوریتم با زمان چندجمله ای (Polynomial-time algorithm)
یک الگوریتم که تابع پیچیدگی زمانی آن است، که p یک تابع چندجمله ای و n طول ورودی است.
الگوریتم با زمان نمايي (Exponential-time algorithm)
هر الگوریتم که تابع پیچیدگی زمانی آن نمی تواند محدود باشد. مانند:
اسلاید 9 :
مسایلی که تابع پیچیدگی زمانی حل آنها چند جمله ای نباشد
در مسایل پیوسته اگر
تابع هدف(min) : محدب
محدودیت ها/فضای حل: محدب
جواب بهینه عمومی دارد و با شرایط KKT قابل حل است
اگر دارای شرایط بالا نباشد، مساله از کلاس NP می باشد و تابع پیچیدگی زمانی حل آن از نوع نمایی است.
اسلاید 10 :
مسائل تصمیم ---> پاسخ بله یا خیر
مسائل بهینه سازی Optimization Problems
برای حل یک مساله ابتدا باید کلاس آن مساله مشخص شود.
برای ثابت کردن اینکه یک مساله NP-Complete است باید آن را به یکی از مسایل شناخته شده این کلاس transfer کرد و پس از آن اجازه استفاده از الگوریتم های متاهیوریستیک وجود دارد
