مسائل ارضای محدودیت
مسئله ارضای محدودیت به دنبال تخصیص مقادیری به مجموعهای از متغیرها است که به طور همزمان تمامی محدودیتهای بین آنها را ارضا کند و یک نمایش یکنواخت برای بسیاری از مسائل ترکیبیاتی فراهم میآورد.
Definition
مسئله ارضای محدودیت شامل مجموعهای از متغیرها، دامنهای از مقادیر ممکن برای هر یک، و مجموعهای از محدودیتها است که ترکیبات مجاز مقادیر را مشخص میکند؛ یک راهحل، تخصیص کاملی است که هیچ محدودیتی را نقض نمیکند.
Scope
این موضوع به فرمالیسم مسئله ارضای محدودیت (CSP) (متغیرها، دامنهها، محدودیتها) و الگوریتمهایی که آن را حل میکنند میپردازد: جستجوی پسگرد با ابتکارات ترتیبدهی متغیر و مقدار، انتشار محدودیت و تکنیکهای سازگاری (سازگاری گره، کمان و مسیر، مانند الگوریتم AC-3)، و بهرهبرداری از ساختار مسئله (CSPs با ساختار درختی، شرطیسازی برش). این موضوع به جستجوی محلی برای CSPs و به عمل گستردهتر برنامهنویسی محدودیت متصل میشود. فرمولبندیهای بهینهسازی پیوسته و مبتنی بر یادگیری مسائل مشابه در اینجا خارج از محدوده هستند.
Core questions
- چگونه مسائل متنوع (زمانبندی، رنگآمیزی نقشه، پازلها) به طور یکنواخت به عنوان متغیرها، دامنهها و محدودیتها مدلسازی میشوند؟
- چگونه انتشار محدودیت مقادیر را قبل و در طول جستجو هرس میکند تا پسگرد را کاهش دهد؟
- کدام ابتکارات ترتیبدهی متغیر و مقدار، جستجوی پسگرد را کارآمد میکنند؟
- چگونه میتوان از ساختار گراف محدودیت (به عنوان مثال، درختی بودن) برای حل کارآمد بهرهبرداری کرد؟
Key concepts
- متغیرها، دامنهها، محدودیتها
- گراف محدودیت
- جستجوی پسگرد
- بررسی پیشرو
- سازگاری کمان و AC-3
- ابتکار حداقل مقادیر باقیمانده
- انتشار محدودیت
- CSPs با ساختار درختی و شرطیسازی برش
Key theories
- سازگاری کمان و انتشار محدودیت
- یک CSP زمانی سازگار کمان است که هر مقدار از هر متغیر یک شریک سازگار در هر متغیر همسایه داشته باشد؛ الگوریتمهایی مانند AC-3 این را با حذف مکرر مقادیر پشتیبانی نشده اعمال میکنند، که اغلب دامنهها را قبل یا در طول جستجو به شدت کوچک میکند.
- جستجوی پسگرد با ابتکارات
- CSPs با تخصیص عمق اول با پسگرد حل میشوند، که با ابتکاراتی مانند انتخاب متغیر با بیشترین محدودیت (حداقل مقادیر باقیمانده)، مقدار با کمترین محدودیت، و با درهم آمیختن بررسی پیشرو یا انتشار برای تشخیص زودهنگام بنبستها، عملی میشود.
- بهرهبرداری از ساختار
- هنگامی که گراف محدودیت یک درخت است، یک CSP میتواند در زمانی خطی نسبت به تعداد متغیرها حل شود، و ساختارهای نزدیک به درخت را میتوان از طریق شرطیسازی برش یا تجزیه درختی به این حالت کاهش داد.
Clinical relevance
تکنیکهای CSP موتور محرک برنامهریزی و زمانبندی، تخصیص منابع، پیکربندی محصولات، تأیید سختافزار و نرمافزار، و حلکنندههای پازل مانند سودوکو هستند؛ زبانهای برنامهنویسی محدودیت و حلکنندههای ساخته شده بر اساس این ایدهها به طور گسترده در برنامهریزی صنعتی و تحقیقات عملیاتی استفاده میشوند.
History
شبکههای محدودیت در دهه 1970 از کارهای مربوط به برچسبگذاری صحنه و سازگاری رابطهای پدید آمدند، با مقاله مکورث در سال 1977 که سازگاری گره، کمان و مسیر را رسمی کرد. در طول دهههای 1980-90 این حوزه به برنامهنویسی محدودیت تبدیل شد، در کتاب راهنمای برنامهنویسی محدودیت در سال 2006 تثبیت شد و همچنان یک موضوع استاندارد در هوش مصنوعی باقی مانده است.
Key figures
- Alan K. Mackworth
- Rina Dechter
- Eugene C. Freuder
- Ugo Montanari
Related topics
Seminal works
- mackworth1977
- dechter2003
- rossi2006
Frequently asked questions
- مسئله ارضای محدودیت چه تفاوتی با یک مسئله جستجوی عمومی دارد؟
- یک مسئله جستجوی عمومی، حالتها را به عنوان جعبههای سیاه در نظر میگیرد، اما یک CSP ساختار داخلی یک حالت را به عنوان تخصیص به متغیرها تحت محدودیتها آشکار میکند. این ساختار به حلکنندههای CSP اجازه میدهد تا از انتشار محدودیت و ابتکارات ترتیبدهی استفاده کنند که جستجوی عمومی نمیتواند از آنها بهرهبرداری کند.
- سازگاری کمان چه کاری انجام میدهد؟
- سازگاری کمان مقادیر را از دامنه یک متغیر حذف میکند که هیچ مقدار سازگاری در یک متغیر همسایه، با توجه به محدودیت بین آنها، ندارند. اعمال آن قبل و در طول جستجو فضای جستجو را هرس میکند و گاهی اوقات میتواند یک مسئله را بدون پسگرد به طور کامل حل کند.