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

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

اسلاید 1: فصل پنجممسائل با ارضاي محدوديتAlireza yousefpouryousefpour@shomal.ac.ir

اسلاید 2: فصل پنجم: مسائل با ارضاء محدوديتمسائل ارضاء محدوديت :نوع خاصي از مسئله است که حالات توسط مقداردهی به مجموعه‌اي از متغيرها تعريف مي‌شوند و آزمون هدف مجموعه‌اي از محدوديت‌ها را به آنها اختصاص مي‌دهد که متغير ملزم به پيروي از آنها هستند. محدوديت‌هاي يکتا محدوديت‌هاي دودويي محدوديت‌هاي مطلق (کامل) محدوديت‌هاي اولويت‌دار(Constraint Satisfaction Problem- CSP)محدوديت‌ها به گونه‌هاي مختلفي ظاهر مي‌شوند

اسلاید 3: مجموعه متناهي از متغيرها: X1 , X2 , … , Xn مجموعه متناهي از محدوديتها: C1 , C2 , …, Cmدامنه هاي نا تهي براي هر يک از متغيرها: DX1,DX2,…,DXn ارضاي محدوديت (CSP) چيست؟هر محدوديت Ci زيرمجموعه اي از متغيرها و ترکيبهاي ممکني از مقادير براي آن زيرمجموعه هاستفصل پنجم: مسائل با ارضاء محدوديت - ادامهپارامترهاي حل مسئله شامل :

اسلاید 4: فصل پنجم: مسائل با ارضاء محدوديت - ادامهتعريف پارامترها در 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iXi = ki, Xj = kj |i-j| | ki - kj| for all j = 1 to 8, ji

اسلاید 5: انتسابي که هيچ محدوديتي را نقض نکند، انتساب سازگار نام دارد انتساب کامل آن است که تمام متغيرها در آن باشد راه حل CSP يک انتساب کامل است با توجه به اینکه تمام محدوديتها را برآورده می کند بعضي از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنندفصل پنجم: مسائل با ارضاء محدوديت - ادامهچند اصطلاح :

اسلاید 6: مثال رنگ آميزي نقشه :متغيرها: 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) برابر :{(قرمز,سبز),(قرمز,آبي),(سبز,قرمز)، (سبز,آبي),(آبي,قرمز),(آبي,سبز)}

اسلاید 7: راه حل، انتساب مقاديري به متغيرهاست که محدوديتها را ارضا کندفصل پنجم: مسائل با ارضاء محدوديت – مثال رنگ آميزيآزمون هدف

اسلاید 8: گراف محدوديتگره ها: متغيرهايالها: محدوديتهاگراف براي ساده تر کردن جست و جو بکار ميروددر گراف محدوديت:فصل پنجم: گراف محدوديت – مثال رنگ آميزي از نوع محدوديت دودوييدو گره مجاور هستند که داراي يک يال در گراف باشند

اسلاید 9: حالت اوليه: انتساب خالي{} که در آن، هيچ متغيري مقدار نداردعملگر: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطي که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشندآزمون هدف: انتساب فعلي کامل است؟هزينه مسير: هزينه ثابت براي هر مرحله1- در فرمول بندي افزايشي می توان مسئله را مثل جستجوهای استاندارد ارائه کرد:فصل پنجم: مسائل با ارضاء محدوديت – گراف محدوديتحل مسائل CSPاز طريق جستجو:1- فرمول بندی افزايشی با استفاده از اين فرمول بندي، هر يک از الگوريتم هاي جستجوي فصل هاي 3 و 4 مي توانند CSP را حل کنند. 2- فرمول بندی حالت کاملبا استفاده از جستجوهای محلی مسئله را حل کنند.

اسلاید 10: فصل پنجم: مسائل با ارضاء محدوديت – گراف محدوديتدر صورتي که از جستجوي سطحي استفاده شود گاهي با مشکلاتي مواجه مي شويم.فاکتور انشعاب در سطح بالا nd مي باشد و در سطح بعد (n-1)d است در عمق n با n متغير با انتساب داريم که در نتيجه تعداد گره های برگی برابر با n!dn خواهد بود.در نتيجه زمانی برابر با O(n!dn) خواهيم داشت.(d تعداد مقادير در دامنه و n تعداد متغيرها) گرچه با خاصيت تعويض پذيري فقط dn در عمق n، انتساب کامل وجود دارد.2- فرمول بندی حالت کاملدر حالت ابتدايی n انتساب به n متغير داريم که ممکن اسـت محدوديتها را ارضاء نکند با استفاده از جستجوی محلی به دنبال حالتی پيش می رويم که انتساب کامل باشد.

اسلاید 11: جستجوي عقبگرد براي CSPيک جست و جوي عمقي است.انتخاب مقادير يک متغير در هر زمان و عقبگرد در صورت عدم وجود مقداري معتبر براي انتساب به متغيريک الگوريتم ناآگاهانه استبراي مسئله هاي بزرگ کارآمد نيست.فصل پنجم: مسائل با ارضاء محدوديت – جستجوي عقبگردBacktracking Search

اسلاید 12: مثالفصل پنجم: مسائل ارضاء محدوديت – جستجوي عقبگرد- مثالQQBTQQQQQBTBTQQQQBTBTBTBTQQQBTQBTQQBTBTQQQQQQQQQQQQQQQQBTBTQQQQQمسئله 4 وزيرهر وزير در يک سطر قرار مي گيردجستجوي عمقي

اسلاید 13: جستجوي عمقي عقبگرد براي مسئله رنگ آميزيفصل پنجم: مسائل با ارضاء محدوديت – جستجوي عقبگرد{} WA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVT هر راه حل در عمق n با n متغير به نظر مي رسد- فرمول بندی افزايشی

اسلاید 14: فصل پنجم: مسائل با ارضاء محدوديت – جستجوي عقبگردFunction CSP-BACKTRACKING(Partial Assignment a)Return a solution, or failureIf a is complete then return aX  select an unassigned variableD  select an ordering for the domain of XFor each value v in D doIf v is consistent with a then Add (X= v) to aresult  CSP-BACKTRACKING(a)If result  failure then return resultReturn failure

اسلاید 15: فصل پنجم: مسائل ارضاء محدوديت – جستجوي عقبگردچند سوال :کدام متغيرها بايد در مرحله بعد مقدار دهي شوند؟ با کدام ترتيب مقادير آنها امتحان مي شوند؟3. نتايج جايگذاري هاي متغير جاري براي ديگر متغيرهاي فاقد مقدار چيست؟4. وقتي مسيري شکست مي خورد، يعني حالتي که در آن متغير هيچ مقدار مجازي ندارد آيا جستجو مي تواند از تکرار شکست در مسيرهاي بعدي جلوگيري کند؟

اسلاید 16: اگر متغيري با صفر مقدار مجاز باقيمانده داشته باشد MRV آنرا انتخاب مي کند پس متغيري انتخاب ميشود که به احتمال زياد، بزودي با شکست مواجه خواهد شد.فصل پنجم: مسائل ارضاء محدوديت– مقادير باقيمانده کميتانتخاب متغير :اين الگوريتم در مسئله رنگ آميزي شکست خواهد خورد زيرا همان ابتدا هر متغير سه مقدار مجاز دارندMinimum Remaining Values - MRVيک ايده اکتشافيانتخاب متغيري با کمترين مقادير باقيمانده مجازايده اول:؟

اسلاید 17: سعي ميکند فاکتور انشعاب را در انتخاب آينده کم کند - به عنوان مثال سمت چپ ترین گره در سطح اول درخت متغيري است که بيشترين درجه(محدوديت) را داردفصل پنجم: مسائل ارضاء محدوديت– درجه اکتشافيک ايده اکتشافي ديگرانتخاب متغيري که در بيشترين تعداد محدوديت روي ديگر متغيرهاي فاقد مشارکت، کاهش دهد. (اکتشاف درجه اي)- يعني متغيري با بيشترين محدوديت در متغيرهاي باقيمانده؟ايده دوم :

اسلاید 18: فصل پنجم: مسائل ارضاء محدوديت– درجه اکتشافيک ايده اکتشافي ديگراکتشاف مقداري باکمترين محدوديتSA={blue}SA={}؟؟Least-Constraining-Value Heuristicايده سوم :متغيري با کمترين مقدار محدود کننده انتخاب مي شود.

اسلاید 19: اين روش مقداري را ترجيح ميدهد که در گراف محدوديت، متغيرهاي همسايه به ندرت آن را انتخاب ميکنندسعي بر ايجاد بيشترين قابليت انعطاف براي انتساب بعدي متغيرهافصل پنجم: مسائل ارضاء محدوديت– درجه اکتشاف - ادامه

اسلاید 20: انتشار اطلاعات مابين محدوديت هافصل پنجم: مسائل ارضاء محدوديت– بررسي پيشرو1- کنترل رو به جلووقتي انتساب به X صورت ميگيرد، فرآيند بررسي رو به جلو، متغيرهاي بدون انتساب مثل Y را در نظر ميگيرد که از طريق يک محدوديت به X متصل است و هر مقداري را که با مقدار انتخاب شده براي X برابر است، از دامنه Y حذف ميکندForward Checking2- کنترل رو به عقب1- کنترل رو به جلوBackward Checkingبا در نظر گرفتن بعضي از محدوديتها مي توان فضاي جستجو را بشدت کاهش دهيم

اسلاید 21: به عنوان مثال: در رنگ آميزيفصل پنجم: مسائل ارضاء محدوديت– بررسي پيشرو

اسلاید 22: فصل پنجم: مسائل ارضاء محدوديت– بررسي پيشرو - ادامهبه عنوان مثال: در رنگ آميزي

اسلاید 23: فصل پنجم: مسائل ارضاء محدوديت– بررسي پيشرو - ادامهبه عنوان مثال: در رنگ آميزيدر اين الگوريتم بررسي رو به جلو نمي تواند انتساب خوبي داشته باشد

اسلاید 24: فصل چهارم: جستجوي اصلاح تکراريبه عنوان مثال: در رنگ آميزيدر نتيجه در اين زمان کنترل رو به جلو نمي تواند انتساب مناسبي را براي متغيرها داشته باشددامنه متغير SA={}

اسلاید 25: 13243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مثال: مسئله 4-وزيرفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردجستجوي عمقيهر وزير در يک سطر قرار مي گيرد

اسلاید 26: 13243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد

اسلاید 27: X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 28: X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 29: X1{1,2,3,4}X3{ , , , }X4{ ,2,3, }X2{ , ,3,4}مثال: مسئله 4-وزيربن بستعقب گردجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 30: 13243241X1{ ,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مثال: مسئله 4-وزيرفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردجستجوي عمقيهر وزير در يک سطر قرار مي گيرد

اسلاید 31: X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}مثال: مسئله 4-وزيرفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردجستجوي عمقيهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 32: X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 33: X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 34: X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}مثال: مسئله 4-وزيرجستجوي عمقيفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241

اسلاید 35: X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}مثال: مسئله 4-وزيرفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241جستجوي عمقي

اسلاید 36: X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}مثال: مسئله 4-وزيرفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيرد13243241جستجوي عمقي

اسلاید 37: مثال: مسئله 4-وزيرFCFCFCFCFCFCQFCFCFCFCFCQFCBTFCFCFCFCQFCFCFCFCFCQFCQFCFCFCFCFCFCFCQBTQFCFCFCBTFCFCFCFCQFCFCFCQFCFCBTFCFCQFCFCFCQFCQFCFCFCFCFCFCQFCFCQBTFCQFCQFCFCFCFCFCQFCFCQBTفصل پنجم: مسائل ارضاء محدوديت – بررسي پيشرو و عقبگردهر وزير در يک سطر قرار مي گيردجستجوي عمقي - درخت جستجو

اسلاید 38: انتشار محدوديتدر انتشار محدوديت، انتشار محدوديتهاي يک متغير به ديگر متغيرهاستمثال: پخش محدوديتهاي WA و Q به NT و SAفصل پنجم: مسائل ارضاء محدوديت– انتشار محدوديتConstraint Propagationکنترل رو به جلو بسياري از ناسازگاريها را تشخيص مي دهد ولي قادر به کشف تمامي آنها نيست.در مثال قبلي حالتي بوجود آمد که NT , SA به رنگ آبي دچار شده اند ولي آنها مجاور هستند و نمي توانند رنگ يکسان داشته باشند.کنترل رو به جلو نتوانست اين را به عنوان يک ناسازگاري کشف کند و نگاه رو به جلو ندارد

اسلاید 39: لبه SA  NSW سازگار است اگر SA=blue and NSW=redمثال: سازگاري يالفصل پنجم: مسائل ارضاء محدوديت– سازگاري يالسازگاري لبه (arc) :يک روش سريع براي انتشار محدوديت که از کنترل رو به جلو قويتر است با استفاده از يال مستقيم بين دو گره ها در گراف محدوديت است

اسلاید 40: يال ميتواند سازگار شود بطوريکه: با حذف blue از NSW , حذف red از Vفصل پنجم: مسائل ارضاء محدوديت– سازگاري يالمثال: سازگاري يالزمان کل در بدترين حالتO(n2d3)

اسلاید 41: سازگاري يال تمام ناسازگاريهاي ممکن را مشخص نميکندبا روش K-سازگاري، شکلهاي قويتري از پخش را ميتوان تعريف کرددر صورتي CSP سازگاريK است، که براي هر k-1 متغير و براي هر انتساب سازگار با آن متغيرها، يک مقدار سازگار هميشه بتواند به متغير kام نسبت داده شودفصل پنجم: مسائل ارضاء محدوديت– سازگاري kK- سازگار :

اسلاید 42: سازگاري1: هر متغير با خودش سازگار است(سازگاري گره)سازگاري2: مشابه سازگاري يال سازگاريk: بسط هر جفت از متغيرهاي همجوار به سومين متغير همسايه(سازگاري مسير) گراف در صورتي قوياً سازگارK است که:سازگارk باشدهمچنين سازگارk-1 و سازگارk-2 و... سازگار 1 باشددر اين صورت، مسئله را بدون عقبگرد ميتوان حل کردپيچيدگي زماني آن O(nd) استدر سازگاري K را مي توان فصل پنجم: مسائل ارضاء محدوديت– سازگاري kبطور مثال:

اسلاید 43: 2- فرمول بندی با حالت کاملجستجوي محلي در مسائل ارضاي محدوديتبسياري از CSPها را بطور کارآمد حل ميکنندحالت اوليه، مقداري را به هر متغير نسبت ميدهدعملگر، تغيير مقدار يک متغير در هر زمانانتخاب مقدار جديد براي يک متغيرانتخاب مقداري که کمترين برخورد را با متغيرهاي ديگر ايجاد کند(اکتشاف برخورد کم) زمان اجراي برخورد کم مستقل از اندازه مسئله استبرخورد کم، براي مسئله هاي سخت نيز کار ميکندفصل پنجم: مسائل ارضاء محدوديت– جستجوي بهينه سازي

اسلاید 44: 22123123323302 در هر مرحله يک وزير به منظور تعيين مجدد ستون انتخاب مي‌شود. تعداد برخوردها در هر چهارخانه نشان داده شده است. الگوريتم وزير را به چهارخانه‌اي که حداقل برخورد را داشته باشد، براي از بين بردن تصادفي برخوردها، حرکت مي‌دهد.راه‌حل دو مرحله‌اي براي مسئله 8 وزير با استفاده از کمترين برخوردفصل پنجم: مسائل ارضاء محدوديت– جستجوي بهينه سازي