روشي جديد براي حل مسائل ارضاي محدوديت
روشي جديد براي حل مسائل ارضاي محدوديت
خلاصه
بسياري از مسائل مطرح در زمينه هوش مصنوعي را مي توان به صورت مسائل ارضاي محدوديت توصيف کرد. اين مسائل با استفاده از مجموعه اي از متغيرها و تعدادي محدوديت براي مقاديري که اين متغيرها مي توانند اختيار کنند, تعريف مي شوند (در اين نوع از مسائل از واژه "برچسب" نيز براي اشاره به "مقدار" يک متغير استفاده مي شود و لذا به آنها مسائل برچسب دهي سازگار نيز اطلاق مي شود). حل اين مسائل مجموعه اي از مقادير منحصر به فرد براي متغيرهاست, به طوري که تمامي محدوديت هاي موردنظر مسئله ارضا شده باشد. تا به حال تعدادي الگوريتم جستجو, ويژه حل اين نوع از مسائل ارائه شده است که برخي از آنها با آينده نگري که در حين حل مسئله انجام مي دهند, تعداد عقب گردهاي کمتري انجام داده و در تعداد قدمهاي کمتري به راه حل دست مي يابند. اين الگوريتم ها عبارتند از "بررسي جلورو", "آينده نگر جزئي" و "آينده نگر کامل". اين الگوريتم ها از نظر ميزان تلاشي که در هر مرحله در قالب بررسي هاي سازگاري, صرف آينده نگري مي کنند و تعداد عقب گردهايي که در حين حل مسئله انجام مي دهند, با يکديگر تفاوت دارند. در اين مقاله, ضمن تشريح الگوريتم هاي ذکر شده, روش جستجوي جديدي که آنرا "آينده نگر کامل بهبوديافته" ناميده ايم نيز معرفي مي شود که از الگوريتم آينده نگر کامل کاراتر است
كليد واژه:
هوش مصنوعي, جستجو, مسائل ارضاي محدوديت, مسائل برچسب دهي سازگار
|