موضوع مقاله: الگوریتم جستجوی کاشف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم جستجوی کاشف | مقدمه: بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. | ## بخش 1: الگوریتم جستجوی کاشف | هیوریستیک‌ها با استفاده از روش‌های نیازمند ارزیابی‌های کمتر و ارائه جوابی‌هایی در محدودیت‌های زمانی قابل قبول دارای نقشی اثر بخش در حل چنین مسائل خواهند بود. دلایل استفاده از هیوریستیک‌ها علاوه بر لزوم پیدا کردن راه‌حل مناسب برای مسئله‌های پیچیده در زمان منطقی، به دلایل دیگر استفاده از روش‌های هیوریستیک در زیر اشاره شده‌است: هیچ راه‌حل بهینه‌ای برای حل مسئله کشف نشده باشد. با وجود این که راه‌حل مشخص و دقیقی برای حل مسئله وجود دارد اما سخت‌افزار مناسب و پیشرفته برای پیاده کردن این راه‌حل موجود نمی‌باشد. راه‌حل هیوریستیک مسئله از انعطاف‌پذیری بیشتری نسبت به راه‌حل دقیق آن برخوردار است که در نتیجه اجازه می‌دهد شروطی از مسئله که شبیه‌سازی آن‌ها در حالت عادی سخت‌ است، در راه‌حل هیوریستیک مدل شوند. خصوصیات هیوریستیک‌های خوب یک الگوریتم هیوریستیک خوب باید شامل خصوصیات زیر باشد: به دست آوردن راه‌حل مسئله شامل محاسبات زیاد و بسیار پیچیده نباشد. انواع روش‌های هیوریستیک روش‌های هیوریستیک متعددی وجود دارند که به علت تنوع بالا و تفاوت ذاتی آن‌ها دسته‌بندی کامل این روش‌ها ممکن نمی‌باشد. | ## بخش 2: الگوریتم جستجوی کاشف | همچنین بسیاری از آن‌ها تنها جوابگوی مسئلهٔ خاصی هستند و نمی‌توان آن‌ها را به مسائل دیگر بسط داد. با این حال می‌توان دسته‌بندی زیر را به عنوان یک دسته‌بندی کلی برای هیوریستیک‌ها در نظر گرفت: روش تجزیه: در این روش مسئله به مسئله‌های کوچکتر شکسته می‌شود که حل آن‌ها ساده‌تر است. روش استقرائی: در این نوع هیوریستیک‌ها سعی می‌شود راه‌حل به دست آمده برای مسئله در حالت ساده یا مقیاس کوچکتر، به مسئله اصلی تعمیم داده شود. باید توجه داشت که در این صورت به علت حذف بخش قابل توجهی از فضای حالت ممکن است بعضی از جواب‌های بهینه نیز از دست بروند و در نهایت جواب شبه بهینه به دست آید یا اصلا جواب شبه بهینه‌ای برای مسئله پیدا نشود. معمولاً راه‌حل‌های این دسته جزو الگوریتم‌های قطعی می‌باشند و به‌طور گسترده در بهینه‌سازی ترکیبیاتی استفاده می‌شوند. روش جستجوی محلی: الگوریتم‌های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل‌های پیش رو (فضای جستجو) با استفاده از تغییرات محدود حرکت می‌کنند تا یک راه حل به نظر مطلوب یافت شود. | ## بخش 3: الگوریتم جستجوی کاشف | در بین این روش‌ها، دو روش سازنده و جستجوی محلی زمینه‌ساز به وجود آمدن الگوریتم‌های فراابتکاری یا متاهیوریستیک‌ها می‌باشند. ارزیابی کیفی یک هیوریستیک روش‌های بسیاری برای ارزیابی کیفیت یک الگوریتم جستجوی کاشف وجود دارد که در زیر به برخی از آن‌ها اشاره شده‌است: مقایسه با راه‌حل بهینه: در صورتی که راه‌حل بهینه‌ای برای حالت‌های محدودی از مسئله وجود داشته باشد، می‌توان با مقایسه هیوریستیک به دست آمده با این راه‌حل، کیفیت هیوریستیک را سنجید. مقایسه با کران: در حالاتی که هیچ راه حل بهینه‌ای حتی در حالت‌های محدود از مسئله وجود ندارد می‌توان از این روش استفاده کرد که جواب به دست آمده از هیوریستیک با کرانی از جواب مسئله مقایسه می‌شود. مقایسه با هیوریستک‌های دیگر: این روش جزو رایج‌ترین روش‌ها برای ارزیابی هیوریستک مسائل پیچیده‌ای است که برای مدت طولانی روی آن‌ها کار شده و هیوریستک‌های خوبی برای آن‌ها به دست آمده‌است. همانند روش "مقایسه با کران"، کیفیت هیوریستیک انتخابی برای مقایسه، تأثیر مستقیم روی نتیجهٔ ارزیابی دارد. | ## جمع‌بندی | نکته منفی راجع به این روش این است که معمولاً بدترین حالت الگوریتم هیوریستیک نمایانگر خوبی از حالت متوسط آن نیست.