بخشی از پاورپوینت
اسلاید 1 :
هوش مصنوعی Artificial Intelligence
اسلاید 2 :
فصل ششم: مسئله های ارضای محدوديت
Constraint satisfaction problems
اسلاید 3 :
مسئله های ارضای محدوديت (CSP)
مساله ارضای محدوديت به وسيله مجموعه ای از متغيرهای X1,X2,… , Xn و مجموعه ای از محدوديت های C1, C2, … , Cn تعريف می شود.
هر متغير Xi دارای يک دامنه ناتهی Di با مقادير ممکن است.
هر محدوديت Ci شامل زير مجموعه هايی از متغيرها و ترکيب های ممکنی از مقادير برای آن زيرمجموعه هاست.
هر حالت مساله با انتساب مقاديری به چند يا تمام متغيرها تعريف می شود:
{Xi = vi, Xj = vj , …}
اسلاید 4 :
مسئله های ارضای محدوديت (CSP)
انتسابی که هيچ محدوديتی را نقض نکند، انتساب سازگار يا معتبر نام دارد.
انتساب کامل آن است که هر متغيری در آن باشد.
راه حل CSP يک انتساب کامل است اگر تمام محدوديتها را برآورده کند.
بعضی از CSP ها به راه حل هايی نياز دارند که تابع هدف را بيشينه کنند.
عمق هر راه حل، اگر n متغير وجود داشته باشد، n است.
الگوريتمهای عمقی برای CSP ها مناسب اند.
اسلاید 6 :
گراف محدوديت
اسلاید 7 :
فرمول بندی افزايشی
حالت اوليه: انتساب خالی {} بدون متغير
تابع جانشين: انتساب يک مقدار به يک متغير به شرط رعايت محدوديت
آزمون هدف: انتساب کامل
هزينه مسير: هزينه ثابت برای هر مرحله
چون مسير رسيدن به راه حل مهم نيست می توان از فرمول بندی کامل نيز استفاده کرد.
اسلاید 8 :
يک نمونه راه حل
اسلاید 9 :
ساده ترين نوع CSP ها شامل متغيرهايی است که گسسته اند و دامنههای متناهی دارند. مثل رنگ آميزی نقشه و مساله هشت وزير
محدوديتها به گونههاي مختلفي ظاهر ميشوند:
محدوديتهاي يگاني:كه فقط مقدار يك متغير را محدود مي كند.
محدوديتهاي دودويي :كه به دو متغير مربوط مي شود.
محدوديت هاي سراسري:كه حاوي تعداد دلخواهي از متغيرها است.
محدوديت هاي مطلق:كه نقض هركدام از آنها از جواب بالقوه جلوگيري مي كند.
محدوديت هاي ترجيحي:كه نشان مي دهند كدام جواب ها بهتر هستند.
اسلاید 10 :
انتشار محدوديت:
سازگاري گره: اگر تمام مقادير موجود در دامنه ي متغيرمحدوديت هاي يگاني مربوط به آن متغير را برآورده كند مي گوييم اين متغير داراي سازگاري گره است.
سازگاري يال:اگر هر مقدار موجود در دامنه ي متغيري در مسئله ي ارضاي محدوديت محدوديت هاي دودويي اين متغير را ارضا كند مي گوييم اي متغير داراي سازگاري يال است.
سازگاري مسير: با استفاده از محدوديت هاي ضمني كه بادر نظر گرفتن سه تايي هايي از متغيرها استنتاج شدند محدوديت هاي دوتايي را تنگ تر مي كند.
اسلاید 11 :
CSPها ميتوانند توسط الگوريتمهاي جستجوي general-purpose حل شوند، اما به علت ساختار خاص آنها، الگوريتمهايي صرفاً براي CSP ها طرح ميشوند که از الگوريتمهاي عمومي کارآيي بهتري دارند.
اسلاید 12 :
جست و جوی عقبگرد برای CSP
تعويض پذيری يکی از خواص مهم CSP
جستجوی عقبگرد، با استفاده از روش يک مقدار در هر زمان
اسلاید 13 :
مقادير باقيمانده کمينه (MRV)
مقادير باقيمانده کمينه (Minimum Remaining Values)
پس از انتسابWA = red
NT = green
فقط يک مقدار برای SA وجود دارد
به جای Q قدم بعدی SA = blue انجام می شود.
اسلاید 14 :
بررسی پيش رو (Forward)
وقتی انتساب به X صورت می گيرد، فرآيند بررسی پيش رو، متغيرهای بدون انتساب مثل Y را در نظر می گيردکه از طريق يک محدوديت به X متصل است و هر مقداری را که با مقدار انتخاب شده برای X برابر است، از دامنه Y حذف می کند.
اسلاید 15 :
جست و جوی محلی برای مسئله های CSP
جست و جوی محلی با اکتشاف کمترين برخورد
انتخاب مقداري كه كمترين برخورد را با متغيرهاي ديگر ايجاد كند
اسلاید 16 :
مقايسه الگوريتم های مختلف CSP بر روی چند مساله
