هوش مصنوعی (فصل پنجم: مسائل با ارضای محدودیت)

Alireza yousefpour yousefpour@shomal.ac.ir فصل پنجم: مسائل با ارضاء محدوديت مسائل ارضاء محدوديت : (onstraint Satisfaction Problem- CSP نوع خاصي از مسئله است که حاالت توسط مقداردهی به مجموعه‌اي از متغيرها تعري ف مي‌شون د و آزمون هدف مجموعه‌اي از محدوديت‌ه ا را ب ه آنه ا اختص اص مي‌دهد که متغير ملزم به پيروي از آنها هستند. محدوديت‌ها به گونه‌هاي مختلفي ظاهر مي‌شوند محدوديت‌هاي يکتا محدوديت‌هاي دودويي محدوديت‌هاي مطلق (کامل) محدوديت‌هاي اولويت‌دار فصل پنجم: مسائل با ارضاء محدوديت -ادامه ارضاي محدوديت ( )CSPچيست؟ پارامترهاي حل مسئله شامل : ‏مجموعه متناهي از متغيرهاX1 , X2 , … , Xn : ‏مجموعه متناهي از محدوديتها: ‏C1 , C2 , …, Cm ‏دامنه هاي نا تهي براي هر يک از متغيرهاDX1,DX2,…,DXn : هر محدوديت Ciزيرمجموعه اي از متغيرها و ترکيبهاي ممکني از مقادير براي آن زيرمجموعه هاست  ادامه- مسائل با ارضاء محدوديت :فصل پنجم : وزير8 تعريف پارامترها در 8 variables Xi, i = 1 to 8  Domain for each variable {1,2,…,8}  Constraints are of the forms: Xi = k  Xj  k for all j = 1 to 8, ji Xi = ki, Xj = kj |i-j| | ki - kj|  for all j = 1 to 8, ji فصل پنجم: مسائل با ارضاء محدوديت -ادامه چند اصطالح : انتسابي که هيچ محدوديتي را نقض نکند ،انتساب سازگار نام دارد انتساب کامل آن است که تمام متغيرها در آن باشد راه حل CSPيک انتساب کامل است با توجه به اینکه تمام محدوديتها را برآورده می کند بعضي از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنند فصل پنجم: مسائل با ارضاء محدوديت – مثال رنگ آميزي مثال رنگ آميزي نقشه : متغيرهاWA, NT, Q, NSW, V, SA, : ‏T دامنه: {آبي ،سبز ،قرمز} = Di محدوديتها :دو منطقه مجاور ،همرنگ نيستند (محدودیت دودویی) ‏WANT, WASA, NTSA, ‏NTQ, SAQ, SANSW, ‏SAV,QNSW, NSWV مثال: WA ≠ NTيعني عضو هاي ( )WA,NTبرابر : {(قرمز,سبز)(,قرمز,آبي)(,سبز,قرمز)( ،سبز,آبي)(,آبي,قرمز)(,آبي,سبز)} فصل پنجم: مسائل با ارضاء محدوديت – مثال رنگ آميزي آزمون هدف راه حل ،انتساب مقاديري به متغيرهاست که محدوديتها را ارضا کند فصل پنجم: گراف محدوديت – مثال رنگ آميزي گراف محدوديت از نوع محدوديت دودويي در گراف محدوديت: ‏گره ها :متغيرها ‏يالها :محدوديتها دو گره مجاور هستند که داراي يک يال در گراف باشند گراف براي ساده تر کردن جست و جو بکار ميرود فصل پنجم: حل مسائل CSP از طريق جستجو: مسائل با ارضاء محدوديت – گراف محدوديت -1فرمول بندی افزايشی با استفاده از اين فرمول بندي ،هر يک از الگوريتم هاي جستجوي فصل هاي 3و 4مي توانند CSPرا حل کنند. -2فرمول بندی حالت کامل با استفاده از جستجوهای محلی مسئله را حل کنند. -1در فرمول بندي افزايشي می توان مسئله را مثل جستجوهای استاندارد ارائه کرد: ‏حالت اوليه :انتساب خالي{} که در آن ،هيچ متغيري مقدار ندارد ‏عملگر :انتساب يک مقدار به هر متغير فاقد مقدار ،به شرطي که با متغيرهايي که قبال مقدار گرفتند ،متضاد نباشند ‏آزمون هدف :انتساب فعلي کامل است؟ ‏هزينه مسير :هزينه ثابت براي هر مرحله فصل پنجم: مسائل با ارضاء محدوديت – گراف محدوديت در صورتي که از جستجوي سطحي استفاده شود گاهي با مشکالتي مواجه مي شويم. فاکتور انشعاب در سطح باال ndمي باشد و در سطح بعد ( d)n-1است در عمق nبا n متغير با انتساب داريم که در نتيجه تعداد گره های برگی برابر با n!dnخواهد بود. در نتيجه زمانی برابر با ) O(n!dnخواهيم داشت. ( dتعداد مقادير در دامنه و nتعداد متغيرها) گرچه با خاصيت تعويض پذيري فقط dnدر عمق ،nانتساب کامل وجود دارد. -2فرمول بندی حالت کامل در حالت ابتدايی nانتساب به nمتغير داريم که ممکن اسـت محدوديتها را ارضاء نکند با استفاده از جستجوی محلی به دنبال حالتی پيش می رويم که انتساب کامل باشد. فصل پنجم: مسائل با ارضاء محدوديت – جستجوي عقبگرد جستجوي عقبگرد براي CSP ‏Backtracking Search ‏يک جست و جوي عمقي است. ‏انتخاب مقادير يک متغير در هر زمان و عقبگرد در صورت عدم وجود مقداري معتبر براي انتساب به متغير ‏يک الگوريتم ناآگاهانه است ‏براي مسئله هاي بزرگ کارآمد نيست. فصل پنجم: مسائل ارضاء محدوديت – جستجوي عقبگرد -مثال جستجوي عمقي مثال مسئله 4وزير هر وزير در يک سطر قرار مي گيرد ‏BT Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏B B ‏Q ‏T T ‏Q ‏Q ‏B ‏T Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏B B ‏Q ‏T ‏B T ‏B ‏Q ‏T T ‏B ‏B ‏T T Q ‏B Q ‏T ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏Q ‏B B ‏Q ‏T T ‏Q ‏Q ‏Q فصل پنجم: مسائل با ارضاء محدوديت – جستجوي عقبگرد جستجوي عمقي عقبگرد براي مسئله رنگ آميزي فرمول بندی افزايشیWA=blue ‏Q ‏WA ‏NSW ‏V ‏T ‏WA=green ‏WA=red ‏NT=blue ‏NT ‏SA {} ‏WA=red ‏WA=red ‏NT=green ‏WA=red ‏NT=green ‏Q=blue هر راه حل در عمق nبا nمتغير به نظر مي رسد ‏WA=red ‏NT=green ‏Q=red – جستجوي عقبگرد مسائل با ارضاء محدوديت :فصل پنجم Function CSP-BACKTRACKING(Partial Assignment a) Return a solution, or failure  If a is complete then return a  X  select an unassigned variable  D  select an ordering for the domain of X  For each value v in D do If v is consistent with a then  Add (X= v) to a  result  CSP-BACKTRACKING(a)  If result  failure then return result  Return failure فصل پنجم: مسائل ارضاء محدوديت – جستجوي عقبگرد چند سوال : .1کدام متغيرها بايد در مرحله بعد مقدار دهي شوند؟ .2با کدام ترتيب مقادير آنها امتحان مي شوند؟ .3نتايج جايگذاري هاي متغير جاري براي ديگر متغيرهاي فاقد مقدار چيست؟ .4وقتي مسيري شکست مي خورد ،يعني حالتي که در آن متغير هيچ مقدار مجازي ندارد آيا جستجو مي تواند از تکرار شکست در مسيرهاي بعدي جلوگيري کند؟ فصل پنجم: مسائل ارضاء محدوديت – مقادير باقيمانده کميت انتخاب متغير : ايده اول :يک ايده اکتشافي انتخاب متغيري با کمترين مقادير باقيمانده مجاز ‏Minimum Remaining Values - MRV اگر متغيري با صفر مقدار مجاز باقيمانده داشته باشد MRVآنرا انتخاب مي کند پس متغيري انتخاب ميشود که به احتمال زياد ،بزودي با شکست مواجه خواهد شد. اين الگوريتم در مسئله رنگ آميزي شکست خواهد خورد زيرا همان ابتدا هر متغير سه مقدار مجاز دارند ؟ فصل پنجم: مسائل ارضاء محدوديت – درجه اکتشاف ايده دوم :يک ايده اکتشافي ديگر انتخاب متغيري که در بيشترين تعداد محدوديت روي ديگر متغيرهاي فاقد مشارکت ،کاهش دهد( .اکتشاف درجه اي) يعني متغيري با بيشترين محدوديت در متغيرهاي باقيماندهسعي ميکند فاکتور انشعاب را در انتخاب آينده کم کند به عنوان مثال سمت چپ ترین گره در سطح اول درخت متغيري است که بيشتريندرجه(محدوديت) را دارد ؟ فصل پنجم: مسائل ارضاء محدوديت – درجه اکتشاف ايده سوم :يک ايده اکتشافي ديگر اکتشاف مقداري باکمترين محدوديت ‏Least-Constraining-Value Heuristic متغيري با کمترين مقدار محدود کننده انتخاب مي شود. ؟ }SA={blue ؟ }{=SA فصل پنجم: مسائل ارضاء محدوديت – درجه اکتشاف -ادامه اين روش مقداري را ترجيح ميدهد که در گراف محدوديت ،متغيرهاي همسايه به ندرت آن را انتخاب ميکنند ‏سعي بر ايجاد بيشترين قابليت انعطاف براي انتساب بعدي متغيرها فصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو انتشار اطالعات مابين محدوديت ها با در نظر گرفتن بعضي از محدوديتها مي توان فضاي جستجو را بشدت کاهش دهيم -1کنترل رو به جلو ‏Forward Checking -2کنترل رو به عقب ‏Backward ‏Checking -1کنترل رو به جلو وقتي انتساب به Xصورت ميگيرد ،فرآيند بررسي رو به جلو ،متغيرهاي بدون انتساب مثل Yرا در نظر ميگيرد که از طريق يک محدوديت به Xمتصل است و هر مقداري را که با مقدار انتخاب شده براي Xبرابر است ،از دامنه Y حذف ميکند فصل پنجم: مسائل ارضاء محدوديت به عنوان مثال: در رنگ آميزي – بررسي پيشرو فصل پنجم: مسائل ارضاء محدوديت به عنوان مثال: در رنگ آميزي – بررسي پيشرو -ادامه فصل پنجم: به عنوان مثال: مسائل ارضاء محدوديت – بررسي پيشرو -ادامه در رنگ آميزي در اين الگوريتم بررسي رو به جلو نمي تواند انتساب خوبي داشته باشد فصل چهارم :جستجوي اصالح تکراري به عنوان مثال: دامنه متغير }{=SA در رنگ آميزي در نتيجه در اين زمان کنترل رو به جلو نمي تواند انتساب مناسبي را براي متغيرها داشته باشد فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 {}1,2,3,4 ‏X1 {}1,2,3,4 ‏X4 {}1,2,3,4 ‏X3 {}1,2,3,4 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 {}1,2,3,4 ‏X1 {}1,2,3,4 ‏X4 {}1,2,3,4 ‏X3 {}1,2,3,4 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }3,4, , ‏X1 {}1,2,3,4 ‏X4 { } ,2,3, ‏X3 { }4, ,2, – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }3,4, , ‏X1 {}1,2,3,4 ‏X4 { } ,2,3, ‏X3 { }4, ,2, – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }3,4, , ‏X1 {}1,2,3,4 ‏X4 { } ,2,3, ‏X3 { } , , , – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 بن بست عقب گرد فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 {}1,2,3,4 ‏X1 { }2,3,4, ‏X4 {}1,2,3,4 ‏X3 {}1,2,3,4 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 {}3,4, ,1 ‏X3 { } , 3, , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 {}3,4, ,1 ‏X3 { } , 3, , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 { } , 3, , 1 ‏X3 {} , , , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 { } , 3, , 1 ‏X3 {} , , , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 { } , 3, , ‏X3 {} , , , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 فصل پنجم: مسائل ارضاء محدوديت مثال :مسئله -4وزير هر وزير در يک سطر قرار مي گيرد ‏X2 { }4, , , ‏X1 { }2,3,4, ‏X4 { } , 3, , ‏X3 {} , , , 1 – بررسي پيشرو و عقبگرد جستجوي عمقي 2 3 4 1 1 2 3 4 – بررسي پيشرو و عقبگرد مسائل ارضاء محدوديت وزير-4 مسئله:مثال جستجوي عمقي درخت جستجوQ FC Q FCFCFCFC FC FC FC FC FC B Q T FCFCFC Q FCFCFC Q FCFC B Q T FC FCFC FC FCFC FCFC Q FCFC FC FCFC B Q T FC Q FCFC B Q T FCFCFC Q Q FCFCFC FCFCFCFC FCFC Q B Q T FCFCFC Q Q FCFCFC FCFC Q FC هر وزير در يک سطر قرار مي گيرد BT Q FC FC FC FC FC FC :فصل پنجم FC FC FC فصل پنجم: مسائل ارضاء محدوديت انتشار محدوديت – انتشار محدوديت ‏Constraint Propagation کنترل رو به جلو بسياري از ناسازگاريها را تشخيص مي دهد ولي قادر به کشف تمامي آنها نيست. در مثال قبلي حالتي بوجود آمد که NT , SAبه رنگ آبي دچار شده اند ولي آنها مجاور هستند و نمي توانند رنگ يکسان داشته باشند. کنترل رو به جلو نتوانست اين را به عنوان يک ناسازگاري کشف کند و نگاه رو به جلو ندارد در انتشار محدوديت ،انتشار محدوديتهاي يک متغير به ديگر متغيرهاست مثال :پخش محدوديتهاي WAو Qبه NTو SA فصل پنجم: مسائل ارضاء محدوديت – سازگاري يال سازگاري لبه (: )arc يک روش سريع براي انتشار محدوديت که از کنترل رو به جلو قويتر است با استفاده از يال مستقيم بين دو گره ها در گراف محدوديت است مثال :سازگاري يال لبه SA  NSWسازگار است ‏SA=blue and NSW=red اگر فصل پنجم: مسائل ارضاء محدوديت – سازگاري يال مثال :سازگاري يال يال ميتواند سازگار شود بطوريکه :با حذف blueاز NSW زمان کل در بدترين حالت )O(n2d3 ,حذف redاز V فصل پنجم: مسائل ارضاء محدوديت – سازگاري k -K س ازگار : ‏سازگاري يال تمام ناسازگاريهاي ممکن را مشخص نميکند ‏با روش -Kسازگاري ،شکلهاي قويتري از پخش را ميتوان تعريف کرد ‏در صورتي CSPسازگاري Kاست ،که براي هر k-1متغير و براي هر انتساب سازگار با آن متغيرها ،يک مقدار سازگار هميشه بتواند به متغير kام نسبت داده شود فصل پنجم: مسائل ارضاء محدوديت – سازگاري k در سازگاري Kرا مي توان بطور مثال :سازگاري :1هر متغير با خودش سازگار است(سازگاري گره) ‏سازگاري :2مشابه سازگاري يال ‏سازگاري :kبسط هر جفت از متغيرهاي همجوار به سومين متغير همسايه(سازگاري مسير) گراف در صورتي قوياً سازگار Kاست که: ‏سازگار kباشد ‏همچنين سازگار k-1و سازگار k-2و ...سازگار 1باشد ‏در اين صورت ،مسئله را بدون عقبگرد ميتوان حل کرد ‏پيچيدگي زماني آن ) O(ndاست فصل پنجم: مسائل ارضاء محدوديت – جستجوي بهي@نه سازي -2فرمول بندی با حالت کامل جستجوي محلي در مسائل ارضاي محدوديت ‏بسياري از CSPها را بطور کارآمد حل ميکنند ‏حالت اوليه ،مقداري را به هر متغير نسبت ميدهد ‏عملگر ،تغيير مقدار يک متغير در هر زمان ‏انتخاب مقدار جديد براي يک متغير ‏انتخاب مقداري که کمترين برخورد را با متغيرهاي ديگر ايجاد کند(اکتشاف برخورد کم) زمان اجراي برخورد کم مستقل از اندازه مسئله است ‏برخورد کم ،براي مسئله هاي سخت نيز کار ميکند فصل پنجم: مسائل ارضاء محدوديت – جستجوي بهي@نه سازي راه‌حل دو مرحله‌اي براي مسئله 8وزير با استفاده از کمترين برخورد 3 2 3 2 1 2 2 3 2 3 1 3 2 0 در هر مرحله يک وزير به منظور تعيين مجدد ستون انتخاب مي‌شود. تعداد برخوردها در هر چهارخانه نشان داده شده است. الگوريتم وزير را به چهارخانه‌اي که حداقل برخورد را داشته باشد ،براي از بين بردن تصادفي برخوردها ،حرکت مي‌دهد.