مسائل ارضای محدودیت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

مسائل ارضای محدودیت (به انگلیسی: Constraint satisfaction problem) یا به اختصار CSP تعداد زیادی از مسائل هوش مصنوعی را در بر می‌گیرند. یک مثال ساده سودوکو می‌باشد که می‌توان آن را بعنوان یک مسئله ارضای محدودیت در نظر گرفت. بسیاری از مسائل مطرح در زمینه هوش مصنوعی را می‌توان به صورت مسائل ارضای محدودیت توصیف کرد. این مسائل با استفاده از مجموعه‌ای از متغیرها و تعدادی محدودیت برای مقادیری که این متغیرها می‌توانند اختیار کنند، تعریف می‌شوند (در این نوع از مسائل از واژه «برچسب» نیز برای اشاره به «مقدار» یک متغیر استفاده می‌شود و لذا به آنها مسائل برچسب دهی سازگار نیز اطلاق می‌شود). حل این مسائل مجموعه‌ای از مقادیر منحصر به فرد برای متغیرهاست، به طوری که تمامی محدودیت‌های موردنظر مسئله ارضا شده باشد. الگوریتم سازگاری کمان یا (Arc consistency) یکی از معروفترین الگوریتم‌ها برای حل این مسائل می‌باشد

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

  • Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009