پاورپوینت الگوریتم های متا هیوریستیک

پاورپوینت الگوریتم های متا هیوریستیک (pptx) 46 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 46 اسلاید

قسمتی از متن PowerPoint (.pptx) :

الگوریتم های متا هیوریستیک چه زمانی اجازه داره از الگوریتم های متا هیوریستیک استفاده کنیم؟ 2 سوال اصلی تعریف مسئله مساله ( Problem ) یک سوال کلی که باید جواب داده شود. مثال : مساله ی بهینه سازی فروشنده دوره گرد. پارامترها ( Parameters ) متغیرهای آزاد مساله که مقادیرشان نامعین قرار داده میشود. مثال : مجموعه ای از شهرهای و مسافت بین هر زوج شهر و 3 تعریف مسئله نمونه ( Instance ) یک نمونه از یک مساله، با قرار دادن مقادیر معین برای تمام پارامترهای مساله بدست می آید. مثال : .... 4 تعریف مسئله مساله بهینه سازی فروشنده دوره گرد 6 9 10 9 5 3 طول تور مینیمم = 27 طول ” تور“ی که از همه ی شهرها به ترتیب میگذرد و به شهر اول بر میگردد را حداقل کنید 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 ، ، . . . ، یا و یا الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (ادامه) 10 Size n time complexity function 60 50 40 30 20 10 .00006 .00005s .00004s .00003s .00002s .00001s .0036s .0025s .0016s .0009s .0004s .0001s   .216s .125s .064s .027s .008s .001s   13 min 5.2 min 1.7 min 24.3s 3.2s 1s   366 centuries 35.7 years 12.7 days 17.9 min 1s .001s   centuries centuries 3855 centuries 6.5years 58 min .059s   مقایسه ی چندین تابع پیچیدگی زمانی چند جمله ای و نمایی