در علوم کامپیوتر، هوش مصنوعی و بهینه سازی، الگوریتم جستجوی کاشف، هیوریستیک ( به انگلیسی: Heuristic ) یا ابتکاری، روشی برای حل مسائلی است که راه های کلاسیک حل آن ها بسیار کند می باشند یا راه حل تقریبی برای مسائلی است که راه های کلاسیک نمی توانند برای آن ها جواب دقیقی پیدا کنند.
بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت های ممکن برای تعیین یک جواب دقیق می باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. هیوریستیک ها با استفاده از روش های نیازمند ارزیابی های کمتر و ارائه جوابی هایی در محدودیت های زمانی قابل قبول دارای نقشی اثر بخش در حل چنین مسائل خواهند بود.
علاوه بر لزوم پیدا کردن راه حل مناسب برای مسئله های پیچیده در زمان منطقی، به دلایل دیگر استفاده از روش های هیوریستیک در زیر اشاره شده است:
• هیچ راه حل بهینه ای برای حل مسئله کشف نشده باشد.
• با وجود این که راه حل مشخص و دقیقی برای حل مسئله وجود دارد اما سخت افزار مناسب و پیشرفته برای پیاده کردن این راه حل موجود نمی باشد.
• راه حل هیوریستیک مسئله از انعطاف پذیری بیشتری نسبت به راه حل دقیق آن برخوردار است که در نتیجه اجازه می دهد شروطی از مسئله که شبیه سازی آن ها در حالت عادی سخت است، در راه حل هیوریستیک مدل شوند.
یک الگوریتم هیوریستیک خوب باید شامل خصوصیات زیر باشد:
• به دست آوردن راه حل مسئله شامل محاسبات زیاد و بسیار پیچیده نباشد.
• احتمال بهینه بودن راه حل به دست آمده باید بالا باشد.
• احتمال به دست آوردن راه حل نامناسب باید بسیار پایین باشد.
روش های هیوریستیک متعددی وجود دارند که به علت تنوع بالا و تفاوت ذاتی آن ها دسته بندی کامل این روش ها ممکن نمی باشد. همچنین بسیاری از آن ها تنها جوابگوی مسئلهٔ خاصی هستند[ ۱] و نمی توان آن ها را به مسائل دیگر بسط داد. با این حال می توان دسته بندی زیر را به عنوان یک دسته بندی کلی برای هیوریستیک ها در نظر گرفت:
• روش تجزیه: در این روش مسئله به مسئله های کوچکتر شکسته می شود که حل آن ها ساده تر است.
• روش استقرائی: در این نوع هیوریستیک ها سعی می شود راه حل به دست آمده برای مسئله در حالت ساده یا مقیاس کوچکتر، به مسئله اصلی تعمیم داده شود.
• روش تقلیل: در این روش هدف، کاهش فضای راه حل های ممکن برای مسئله است. باید توجه داشت که در این صورت به علت حذف بخش قابل توجهی از فضای حالت ممکن است بعضی از جواب های بهینه نیز از دست بروند و در نهایت جواب شبه بهینه به دست آید یا اصلا جواب شبه بهینه ای برای مسئله پیدا نشود.
• روش سازنده: در این روش راه حل مسئله قدم به قدم و از صفر ساخته می شود. معمولاً راه حل های این دسته جزو الگوریتم های قطعی می باشند و به طور گسترده در بهینه سازی ترکیبیاتی استفاده می شوند.
• روش جستجوی محلی: الگوریتم های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل های پیش رو ( فضای جستجو ) با استفاده از تغییرات محدود حرکت می کنند تا یک راه حل به نظر مطلوب یافت شود. زمانی که راه حل بهتری یافت نشود، این الگوریتم پایان می پذیرد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت های ممکن برای تعیین یک جواب دقیق می باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. هیوریستیک ها با استفاده از روش های نیازمند ارزیابی های کمتر و ارائه جوابی هایی در محدودیت های زمانی قابل قبول دارای نقشی اثر بخش در حل چنین مسائل خواهند بود.
علاوه بر لزوم پیدا کردن راه حل مناسب برای مسئله های پیچیده در زمان منطقی، به دلایل دیگر استفاده از روش های هیوریستیک در زیر اشاره شده است:
• هیچ راه حل بهینه ای برای حل مسئله کشف نشده باشد.
• با وجود این که راه حل مشخص و دقیقی برای حل مسئله وجود دارد اما سخت افزار مناسب و پیشرفته برای پیاده کردن این راه حل موجود نمی باشد.
• راه حل هیوریستیک مسئله از انعطاف پذیری بیشتری نسبت به راه حل دقیق آن برخوردار است که در نتیجه اجازه می دهد شروطی از مسئله که شبیه سازی آن ها در حالت عادی سخت است، در راه حل هیوریستیک مدل شوند.
یک الگوریتم هیوریستیک خوب باید شامل خصوصیات زیر باشد:
• به دست آوردن راه حل مسئله شامل محاسبات زیاد و بسیار پیچیده نباشد.
• احتمال بهینه بودن راه حل به دست آمده باید بالا باشد.
• احتمال به دست آوردن راه حل نامناسب باید بسیار پایین باشد.
روش های هیوریستیک متعددی وجود دارند که به علت تنوع بالا و تفاوت ذاتی آن ها دسته بندی کامل این روش ها ممکن نمی باشد. همچنین بسیاری از آن ها تنها جوابگوی مسئلهٔ خاصی هستند[ ۱] و نمی توان آن ها را به مسائل دیگر بسط داد. با این حال می توان دسته بندی زیر را به عنوان یک دسته بندی کلی برای هیوریستیک ها در نظر گرفت:
• روش تجزیه: در این روش مسئله به مسئله های کوچکتر شکسته می شود که حل آن ها ساده تر است.
• روش استقرائی: در این نوع هیوریستیک ها سعی می شود راه حل به دست آمده برای مسئله در حالت ساده یا مقیاس کوچکتر، به مسئله اصلی تعمیم داده شود.
• روش تقلیل: در این روش هدف، کاهش فضای راه حل های ممکن برای مسئله است. باید توجه داشت که در این صورت به علت حذف بخش قابل توجهی از فضای حالت ممکن است بعضی از جواب های بهینه نیز از دست بروند و در نهایت جواب شبه بهینه به دست آید یا اصلا جواب شبه بهینه ای برای مسئله پیدا نشود.
• روش سازنده: در این روش راه حل مسئله قدم به قدم و از صفر ساخته می شود. معمولاً راه حل های این دسته جزو الگوریتم های قطعی می باشند و به طور گسترده در بهینه سازی ترکیبیاتی استفاده می شوند.
• روش جستجوی محلی: الگوریتم های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل های پیش رو ( فضای جستجو ) با استفاده از تغییرات محدود حرکت می کنند تا یک راه حل به نظر مطلوب یافت شود. زمانی که راه حل بهتری یافت نشود، این الگوریتم پایان می پذیرد.
wiki: الگوریتم جستجوی کاشف