الگوریتم جستجوی کاشف

الگوریتم جستجوی کاشف، به دسته‌ای از راه‌حل‌ها گویند که به دنبال جوابی معقول و قابل قبول برای یک مسئله دشوار می‌گردند که الزاماً بهترین جواب برای آن مسئله نیست.

روش‌های کشف کنندگی

کشف‌کنندگی از نظر دانشمندان هوش مصنوعی در دو وضعیت پایه می‌تواند صورت گیرد:

1. مسئله‌ای وجود داشته باشد که فاقد راه حل دقیق باشد چرا که در تعریف مسئله و یا داده‌های موجود برای آن ابهام دیده می‌شود. برای مثال می‌توان به تشخیص پزشکی اشاره نمود. مجموعه‌ای از علائم بیماری می‌تواند نشانه وجود چندین بیماری باشد اما پزشکان با توجه به قدرت کشف کنندگی که بر اثر تجربه بدست آمده‌است بهترین تشخیص را انجام داده و بر این اساس اقدام به درمان بیماری می‌کنند. احساس بینائی اغلب با ابهام روبرو است و به همین علت در تشخیص پیوستگی، امتداد و جهت اشیاء دچار اشکال می‌شود. خطای باصره نیز این امر را تشدید می‌کند. سیستم بینائی از کشف کنندگی لازم برخوردار است تا قادر به انتخاب یکی از چند تفسیر ممکن از یک رویداد بصری شود.
2. مسئله‌ای ممکن است پاسخ دقیقی داشته باشد اما هزینه یافتن این پاسخ به قدری سنگین باشد که در عمل مقرون به صرفه نباشد. در بسیاری از مسائل واقعی فضای حالت دارای رشد نمائی یا فاکتوریلی به ازای افزایش عمق جستجو است. در چنین شرایطی روشهای جستجوی کامل مثل جستجوی عمقی یا سطحی در دوره عملی زمانی قادر به یافتن پاسخ نیست. خواص کشف کنندگی به‌وسیله جهت دادن به جستجو بخش قابل ملاحظه‌ای از این فضا را حذف می‌کند. متاسفانه روشهای کشف کنندگی متکی بر تجربه و یا حس هستند و به همین علت استفاده از آنها در الگوریتم‌ها دشوار است. باید توجه داشت که خاصیت کشف کنندگی به علت حذف بخش قابل توجهی از فضای حالت ممکن است بعضی از جواب‌های بهینه را نیز از دست بدهد و در نهایت به جواب شبه بهینه دست یابد و یا اینکه در این امر توفیقی نداشته باشد.

الگوریتم‌های کشف کننده شامل دو بخش هستند: الف)ملاک کشف کنندگی ب)الگوریتمی که بر پایه ملاک کشف کنندگی برای جستجوی فضای حالت مورد استفاده قرار گیرد.

منابع

• The design and analysis of algorithms, D.Kozen
• Artificial intelligence, G.Luger

• طراحی الگوریتم، رامین رهنمون

جستارهای وابسته

• هوش مصنوعی
• طراحی الگوریتم