روشي جديد براي حل مسائل ارضاي محدوديت

A New Method for Solving Constraint Satisfaction Problems

بسياري از مسائل مطرح در زمينه هوش مصنوعي را مي‌توان به صورت مسائل ارضاي محدوديت توصيف كرد. اين مسائل با استفاده از مجموعه‌اي از متغيرها و تعدادي محدوديت بر روي مقاديري كه اين متغيرها مي‌توانند اختيار كنند، تعريف مي‌شوند (در اين نوع از مسائل از واژه برچسب نيز براي اشاره به مقدار يك متغير استفاده مي‌شود و لذا به آنها مسائل برچسب دهي سازگار نيز اطلاق مي‌شود). حل اين مسائل مجموعه‌اي از مقادير منحصر به فرد براي متغيرهاست، به‌طوري‌كه تمامي محدوديتهاي مورد نظر مسئله ارضا شده باشد. تا به حال تعدادي الگوريتم جستجو، ويژه حل اين نوع از مسائل ارائه شده ‌است كه برخي از آنها با آينده‌نگري كه در حين حل مسئله انجام مي‌دهند، تعداد عقبگردهاي3 كمتري انجام داده و در تعداد قدمهاي كمتري به راه حل دست مي‌يابند. اين الگوريتمها عبارت‌اند از بررسي جلورو، آينده‌نگر جزيي و آينده‌نگر كامل. اين الگوريتمها از نظر ميزان تلاشي كه در هر مرحله در قالب بررسيهاي سازگاري4، صرف آينده‌نگري مي‌كنند و تعداد عقبگردهايي كه در حين حل مسئله انجام مي‌دهند، با يكديگر تفاوت دارند. در اين مقاله، ضمن تشريح الگوريتمهاي ذكر شده، روش جستجوي جديدي كه آن را آينده‌نگر كامل بهبود يافته ناميده‌ايم نيز معرفي مي‌‌شود كه از الگوريتم آينده‌نگر كامل كاراتر است

Many important problems in Artificial Intelligence can be defined as Constraint Satisfaction Problems (CSP). These types of problems are defined by a limited set of variables, each having a limited domain and a number of Constraints on the values of those variables (these problems are also called Consistent Labeling Problems (CLP), in which “Labeling means assigning a value to a variable.) Solution to these problems is a set of unique values for variables such that all the problem constraints are satisfied. Several search algorithms have been proposed for solving these problems, some of which reduce the need for backtracking by doing some sort of looking to future, and produce more efficient solutions. These are the so-called Forward Checking (FC), Partially Lookahead (PL), and Fully Lookahead (FL) algorithms. They are different in terms of the amount of looking to the future, number of backtracks that are performed, and the quality of the solution that they find. In this paper, we propose a new search algorithm we call Modified Fully Lookahead (MFL) which is Shown to be more efficient than the original Fully Lookahead algorithm