مشکلات رضایت از محدودیت ( CSPs ) سوالات ریاضی هستند که به عنوان مجموعه ای از اشیا تعریف می شوند که دولت باید تعدادی محدودیت یا محدودیت را برآورده کند . CSPs نشان دهنده نهادها در یک مشکل به عنوان مجموعه ای همگن از محدودیت های محدود بر متغیرها است که توسط روش های رضایت از محدودیت حل می شود . CSPs موضوع پژوهش شدید در هر دو تحقیقهوش مصنوعی و تحقیق عملیاتی است ، زیرا منظم سازی در فرمول بندی آنها یک مبنای رایج برای تجزیه و تحلیل و حل مشکلات بسیاری از خانواده های به ظاهر غیر مرتبط است. CSP ها اغلب پیچیدگی های بالا را نشان می دهند، نیاز به ترکیبی از اکتشافات و روش های جستجوی ترکیبی در یک زمان معقول حل می شود. مسئله صدق پذیری دودویی (SAT) از نظریه ارضا پیمانه (SMT) و پاسخ برنامه نویسی مجموعه (ASP) را می توان تقریبا از اشکال عنوان خاصی از مسائل ارضای محدودیت فکر می کردم.

نمونه هایی از مشکلات ساده که می تواند به عنوان یک مسئله رضایت از محدودیت مدل سازی شود عبارتند از:

این اغلب با آموزش ASP، Boolean SAT و حل کننده SMT ارائه می شود. در مورد کلی، مشکلات محدودیت می تواند بسیار سخت تر باشد و ممکن است در برخی از این سیستم های ساده قابل بیان نباشد.

مثالهای "زندگی واقعی" عبارتند از: برنامه ریزی خودکار ، [1] [2] ابهام واژگان ، [3] [4] موسیقی شناسی [5] و تخصیص منابع . [6] یک مثال برای راه حل پازل استفاده از یک مدل محدودیت به عنوان یک الگوریتم حل سودوکو است .

وجود یک راه حل برای CSP می تواند به عنوان یک مشکل تصمیم گیری شود . این را می توان با یافتن یک راه حل یا عدم یافتن یک راه حل بعد از جستجوی جامع تصمیم گرفت (الگوریتم های تصادفی معمولا هرگز به نتیجه گیری کامل نمی رسند، در حالی که جستجوهای هدایت شده اغلب بر روی مشکلات به اندازه کافی کوچک انجام می شود). در برخی موارد CSP ممکن است پیش از این راه حل هایی داشته باشد، از طریق برخی از روش های دیگر نتیجه گیری ریاضی.

 

فهرست

تعریف رسمی [ ویرایش ]

به صورت رسمی، یک مسئله رضایت از محدودیت به عنوان سه گانه تعریف می شود \ langle X، D، C \ rangle ، جایی که [7]

X = \ {X_ {1}، \ ldots، X_ {n} \} مجموعه ای از متغیرها است

D = \ {D_ {1}، \ ldots، D_ {n} \} مجموعه ای از مقادیر مربوطه است و

C = \ {C_ {1}، \ ldots، C_ {m} \} مجموعه ای از محدودیت ها است.

هر متغیر X_ {I} می تواند مقادیری را در دامنه غیر قابل نفوذ بگیرد D_ {I}. هر محدودیتیC_ {j} \ در C به نوبه خود یک جفت است \ langle t_ {j}، R_ {j} \ rangle ، جایی کهt_ {j} \ زیر مجموعه X یک زیر مجموعه ازک متغیرها و R_ {j} هست یک  در رابطه با زیر مجموعه های مربوطهدی جی}. ارزیابی از متغیرهای یک تابع از یک زیر مجموعه از متغیرها به یک مجموعه خاص از ارزش ها در زیر مجموعه مربوطه از حوزه است. ارزیابیv یک محدودیت را برآورده می کند \ langle t_ {j}، R_ {j} \ rangle  اگر مقادیر اختصاص داده شده به متغیرها باشد t_ {j} رابطه را ارضا می کند R_ {j}.

ارزیابی است سازگار اگر در آن از محدودیت نقض نمی کند. ارزیابی کامل است اگر شامل همه متغیرها باشد. یک ارزیابی یک راه حل است اگر هماهنگ و کامل باشد؛ گفته می شود چنین ارزیابی برای حل مشکل رضایت از محدودیت است.

قطعنامه [ ویرایش ]

مشکلات رضایت از محدودیت در حوزه های محدود معمولا با استفاده از یک فرم جستجو حل می شود . تکنیک هایی که بیشتر مورد استفاده قرار می گیرند عبارتند از انواع بازپرداخت ، محدودیت انتشار و جستجوی محلی .

Backtracking یک الگوریتم بازگشتی است. این یک تخصیص جزئی متغیرها را حفظ می کند. در ابتدا همه متغیرها غیرقانونی هستند. در هر مرحله یک متغیر انتخاب می شود و تمام مقادیر ممکن به نوبه خود اختصاص داده می شود. برای هر مقدار، انطباق تخصیص جزئی با محدودیت ها بررسی می شود؛ در صورت انطباق، یک تماس بازگشتی انجام می شود. هنگامی که تمام مقادیر مورد آزمایش قرار گرفتند، الگوریتم backtracks. در این الگوریتم backtracking پایه، سازگاری به عنوان رضایت تمام محدودیت ها تعریف می شود که متغیرهای آن همه اختصاص داده شده اند. چندین نسخه از بازخوانی وجود دارد. Backmarking باعث افزایش کارایی بررسی صحت می شود. پشت سر هماجازه می دهد تا بخش هایی از جستجو را از طریق بازگرداندن "بیش از یک متغیر" در بعضی موارد ذخیره کند. یادگیری محدودیت ها موجب صرفه جویی در محدودیت های جدید می شود که بعدا می تواند برای اجتناب از بخشی از جستجو استفاده شود. پیشروی نیز اغلب در عقب رانندگی استفاده می شود تا تلاش کند تا اثرات انتخاب متغیر یا ارزش را پیش بینی کند، در نتیجه بعضی اوقات پیش می آید که یک Subproblem رضایت بخش یا غیر قابل قبول باشد.

تکنیک های انتشار محدودیت ها روش هایی هستند که برای اصلاح مشکل رضایت از محدودیت استفاده می شوند. دقیق تر، آنها روش هایی هستند که یک شکل از قاعده محلی را اجرا می کنند ، که شرایطی است که به قوام گروهی از متغیرها و یا محدودیت ها مربوط می شود. انتشار محدودیت دارای کاربردهای متنوع است. اولا، یک مسئله را به یک معادل تبدیل می کند، اما معمولا حل آن ساده تر است. دوم، ممکن است رضایت یا نارضایتی از مشکلات را ثابت کند. این به طور کلی تضمین نمی شود؛ با این حال، آن را همیشه برای برخی از انواع انتشار محدودیت و / یا برای انواع خاصی از مشکلات رخ می دهد. اشکال شناخته شده و مورد استفاده از انسجام محلی قوام قوسی ، قوام قوای قوسی و سازگاری مسیر است. روش محبوبترین محدودیت انتقال الگوریتم AC-3 است که قوام قوسی را اجرا می کند.

روش های جستجوی محلی الگوریتم های رضایت ناقص هستند. آنها ممکن است یک راه حل یک مشکل پیدا کنند، اما حتی ممکن است مشکل حل شود. آنها با تکرار یک تکلیف کامل بر روی متغیرها کار می کنند. در هر مرحله تعدادی از متغیرها در مقدار تغییر می کنند، با هدف کلی افزایش تعداد محدودیت هایی که این تخصیص راضی می کند. الگوریتم دقیقه درگیری یک الگوریتم جستجوی محلی خاص برای CSP ها است و خاموش است که اصل است. در عمل، جستجوی محلی به نظر می رسد به خوبی کار می کنند، زمانی که این تغییرات نیز تحت تاثیر انتخاب های تصادفی قرار می گیرد. یکپارچگی جستجو با جستجوی محلی توسعه یافته است، که منجر به الگوریتم های ترکیبی می شود .

جنبه های نظری [ ویرایش ]

مشکلات تصمیم گیری [ ویرایش ]

CSP ها در نظریه پیچیدگی محاسباتی و نظریه مدل محدود نیز مورد مطالعه قرار گرفته اند . یک سوال مهم این است که آیا برای هر مجموعه روابط مجموعه ای از تمام CSP ها که می توانند با استفاده از روابط انتخاب شده از آن مجموعه نمایش داده شوند یا در P یا NP-complete هستند . اگر چنین قضیه دوگانگی درست باشد، CSP ها یکی از بزرگترین زیر مجموعه های شناخته شده NP را ارائه می دهند که از مشکلات NP-middle که از وجود آن توسط قضیه لنرن بر اساس این فرض که P ≠ NP ثابت می شود، اجتناب می شود . Thetheorem dichotomy Schaefer در مورد زمانی که همه روابط در دسترس موجود است رفتار می کنداپراتورهای بولی ، یعنی برای اندازه دامنه 2. قضیه دوگانگی شاصر اخیرا به یک کلاس بزرگتر از روابط تعمیم داده شد. [8]

اکثر کلاسهای CSP که شناخته شده هستند قابل ردیابی هستند، آنهایی هستند که hypergraph محدودیتها عرض width را محدود می کند (و هیچ محدودیتی در مجموعه روابط محدود وجود ندارد)، یا جایی که محدودیت ها دارای فرم دلخواه هستند، اما پلی مورفیسم ها اساسا غیر انحصاری وجود دارد [ توضیح لازم ] از مجموعه روابط محدود.

هر CSP همچنین می تواند به عنوان یک مسئله مهاربندی پرسشی مشترک باشد. [9]

مشکلات عملکرد [ ویرایش ]

وضعیت مشابهی بین کلاسهای FP و #P وجود دارد . با تعمیم قضیه Ladner ، در FP ≠ #P نیز هیچ مشکلی در FP و # P-complete وجود ندارد . همانطور که در مورد تصمیم گیری، یک مشکل در #CSP توسط مجموعه ای از روابط تعریف شده است. هر مشکلی به عنوان ورودی یک فرمول بولین به عنوان ورودی است و وظیفه محاسبه تعداد تکالیف رضایت بخش است. این می تواند بیشتر با استفاده از اندازه های بزرگتر دامنه و پیوستن وزن به هر تخصیص رضایت بخش و محاسبه مجموع این وزن ها. شناخته شده است که هر مشکل پیچیده وزن #CSP یا FP یا # P-hard است. [10]

واژگان [ ویرایش ]

مدل کلاسیک مساله رضایت محدودیت یک مدل از محدودیت های استاتیک، غیر انعطاف پذیر را تعریف می کند. این مدل سفت و سخت، کمبودی است که به آسانی می تواند مشکلات را به نمایش گذارد. [11] تغییرات متعددی از تعریف اساسی CSP برای تطبیق مدل با طیف وسیعی از مشکلات ارائه شده است.

CSPs دینامیک [ ویرایش ]

CSPs دینامیک [12] ( DCSPs ) مفید هستند وقتی که فرمول اصلی یک مشکل به نحوی تغییر می یابد، به طور معمول به این دلیل است که مجموعه ای از محدودیت هایی که در نظر گرفته می شود به دلیل محیط زیست در نظر گرفته شده است. [13] DCSP ها به عنوان دنباله ای از CSP های استاتیک مشاهده می شوند، هر کدام یک تغییر از پیشین است که در آن متغیرها و محدودیت ها می توانند اضافه شوند (محدود کردن) یا حذف (relaxation). اطلاعات موجود در فرمول های اولیه مشکل می تواند مورد استفاده برای اصلاح بعدی است. روش حل را می توان بر اساس شیوه انتقال اطلاعات طبقه بندی کرد:

  • Oracles: راه حل موجود در CSP های قبلی در دنباله به عنوان اکتشافی برای هدایت قطعنامه CSP فعلی از ابتدا استفاده می شود.
  • تعمیرات محلی: هر CSP محاسبه می شود و از راه حل جزئی نسخۀ قبلی محاسبه می شود و ترمیم محدودیت های نا متناسب با جستجوی محلی .
  • ضبط محدودیت: محدودیت های جدید در هر مرحله از جستجو برای نشان دادن یادگیری گروه متضاد تصمیم گیری تعریف می شود. این محدودیت ها به مشکلات جدید CSP منتقل می شوند.

CSPs انعطاف پذیر [ ویرایش ]

CSP های کلاسیک محدودیت ها را سخت به کار می گیرند، به این معنی که آنها ضروری هستند (هر راه حل باید همه آنها را برآورده کند) و انعطاف ناپذیر (به این معنا که آنها باید کاملا راضی باشند یا در غیر این صورت آنها به طور کامل نقض می شوند). CSP انعطاف پذیر این فرضها را آرام می کند، بعضی اوقات محدودیت ها را آرام می کند و راه حل را با تمام آنها مطابقت نمی دهد. این مشابه ترجیحات در برنامه ریزی مبتنی بر اولویت است . برخی از انواع CSP های انعطاف پذیر عبارتند از:

  • MAX-CSP، که در آن تعدادی از محدودیت ها مجاز به نقض هستند، و کیفیت راه حل بر اساس تعداد محدودی از محدودیت ها محاسبه می شود.
  • CSP وزنی ، یک MAX-CSP که در آن هر تخلف از یک محدودیت با توجه به اولویت از پیش تعریف شده وزن می شود. بنابراین رضایت از محدودیت با وزن بیشتر ترجیح داده می شود.
  • محدودیت های مدل فازی CSP به عنوان روابط فازی که در آن رضایت از یک محدودیت یک عملکرد پیوسته از ارزش متغیرهای آن است، از کاملا رضایت کامل گرفته تا کاملا نقض شده است.

CSPs تصادفی شده [ ویرایش ]

در DCSPs [14] هر متغیر محدودیتی به عنوان یک مکان جغرافیایی جداگانه در نظر گرفته شده است. محدودیت های شدید در تبادل اطلاعات بین متغیرها قرار می گیرند، و نیاز به استفاده از الگوریتم های به طور کامل توزیع شده برای حل مسئله رضایت از محدودیت دارند.

همچنین نگاه کنید به [ ویرایش ]