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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

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

منابع[ویرایش]

  • The design and analysis of algorithms, D.Kozen
  • Artificial intelligence, G.Luger
  • طراحی الگوریتم، رامین رهنمون

جستارهای وابسته[ویرایش]