یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
روش های فرا اکتشافی

سیستم‌های پیچیده اجتماعی تعداد زیادی از مسایل دارای طبیعت ترکیبی[1] را پیش روی ما قرار می‌دهند. مسیر کامیون­های حمل و نقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید مکان­یابی شوند، شبکه‌های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی باید دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه‌های لازم بریده شوند؛ از این دست مسایل بی‌شمارند. تئوری پیچیدگی به ما می­گوید که مسایل ترکیبی اغلب چندجمله­ای[2] نیستند. این مسایل در اندازه‌های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینه ان­ها را در مدت زمان قابل پذیرش به دست اورد. با این وجود، این مسایل باید حل شوند و بنابراین چاره‌ای نیست که به جواب­های زیر بهینه[3]بسنده کرد به گونه‌ای که دارایکیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست ایند.

چندین رویکرد برای طراحی جواب­های با کیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است. الگوریتم‌هایی هستند که می‌توانند یافتن جواب­های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به انها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به انها الگوریتم‌های احتمالی[4] گفته می‌شود. غیر از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند،اما بر اساس شواهد و سوابق نتایج ان­ها، به طور متوسط بهترین تقابل کیفیت و زمان حل، برای مسئله مورد بررسی را به همراه داشته‌اند. به این الگوریتم‌ها، الگوریتم‌های مکاشفه­ای[5] گفته می‌شود.


[1] Combinatorial

[2] Polynomial

[3] Suboptimal

[4] Probabilistic algorithm

[5] Heuristic

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26