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

از ویکی‌پدیا، دانشنامهٔ آزاد.

فهرست مندرجات

[ویرایش] مقدمه

ریشه واژه «heuristic» از لغت eurisco در زبان یونانی است که به معنی " من کشف کردم " می باشد. زمانی که ارشمیدس روشی برای محاسبه وزن تاج طلا در حمام پیدا کرد، برهنه از حمام بیرون آمد و فریاد زد: "Eureka!" که به معنی " من آنرا یافتم " است. اما در جستجوی فضای حالت منظور از heuristic قوانینی برای انتخاب شاخه هائی در فضای حالت است که سریعتر می تواند به یک پاسخ قابل قبول برای مسئله منجر گردد.

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

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

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

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

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

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

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

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

تصویر:Computer-stub.png این نوشتار دربارهٔ رایانه خُرد است. با گسترش آن به ویکی‌پدیا کمک کنید.