CSP (Constraint Satisfaction Problem)

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

روش های جستجوی آگاهانه

این استراتژی ها با استفاده از دانش ویژه مسئله، راه حل های کارا تری پیدا می کنند.

کشف کنندگی(Heuristic)

کلمه کشف کنندگی از فعل یونانی Heuriskein که به معنی پیدا کردن یا کشف کردن است، مشتق شده است.

برخی کشف کنندگی را متضاد حالت الگوریتمیک به کار می برند.

تکنیک های کشف کنندگی بر کاربرد های اولیه هوش مصنوعی حکم فرما بود. اولین آزمایشگاه سیستم های خبره، که توسط Ed Fergenbaum، Bruce Buchanan، Joshua Lederberg در دانشگاه استنفورد آغاز به کار کرد، پروژه برنامه نویسی کشف کننده (HPP) نامیده شد.

کشف کنندگی ها به عنوان راه تجربی مطرح می شوند که خبره دان ها از آن برای تولید راه حل های خوب بدون جستجوی بی نتیجه استفاده می کردند.

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

1- جستجوی بهترین (Best-First Search)

همانطور که می دانید، الگوریتم جستجوی عمومی با استفاده از صف ها دانش مسئله را به کار می برد. اگر با استفاده از یک تابع ارزیابی (Evaluation)، که توضیحاتی مبنی بر مطلوب بودن یا نبودن گره را در بر دارد، صف را مرتب کنیم، ابتدا گره ای که بهترین رتبه را در ارزیابی داشته باشد، بسط داده می شود. این استراتژی را جستجوی بهترین می گویند.

نام «جستجوی بهترین» نادرست است. زیرا اگر ما می توانستیم واقعا بهترین گره را در ابتدا بسط دهیم، دیگر نمی توانستیم نام این عمل را جستجو بگذاریم.

به دلیل وجود توابع ارزیابی گوناگون، خانواده بزرگی از الگوریتم های جستجوی بهترین وجود دارد. همان گونه که الگوریتم جستجوی بهترین نیز عضوی از خانواده بزرگ الگوریتم جستجوی عمومی است.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |