دسته بندی | مدیریت |
بازدید ها | 18 |
فرمت فایل | doc |
حجم فایل | 12 کیلو بایت |
تعداد صفحات فایل | 10 |
الگوریتم های هیوریستیک ها
1-مقدمه
سیستمهای پیچیده اجتماعی تعداد زیادی از مسائل دارای طبیعت ترکیباتی1 را پیش روی ما قرار میدهند. مسیر کامیونهای حمل و نقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکههای ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابطهای رادیویی میبایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازههای لازم بریده شوند؛ از این دست مسائل بیشمارند. تئوری پیچیدگی به ما می گوید که مسائل ترکیباتی اغلب پلینومیال2 نیستند. این مسائل در اندازههای کاربردی و عملی خود به قدری بزرگ هستند که نمیتوان جواب بهینه آنها را در مدت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و بنابراین چارهای نیست که به جوابهای زیر بهینه3 بسنده نمود به گونهای که دارای کیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست آیند.
چندین رویکرد برای طراحی جوابهای با کیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است. الگوریتمهایی هستند که میتوانند یافتن جوابهای خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوریتمهای تقریبی میگویند. الگوریتمهای دیگری هستند که تضمین میدهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آنها الگوریتمهای احتمالی گفته میشود. جدای از این دو دسته، میتوان الگوریتمهایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسئله مورد بررسی را به همراه داشتهاند. به این الگوریتمها، الگوریتمهای هیوریستیک گفته میشود.