نویسنده

• غلامرضا ثانی و مجید نمازی

چکیده

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

کلیدواژه‌ها

• هوش مصنوعی
• جستجو
• مسائل ارضای محدودیت
• مسائل برچسب دهی سازگار

عنوان مقاله [English]

A New Method for Solving Constraint Satisfaction Problems

نویسنده [English]

• G. Ghassem-Sani and M. Namazi

چکیده [English]

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

کلیدواژه‌ها [English]

• Artificial Intelligence
• Search
• Constraint Satisfaction Problems
• consistent labeling problems