دانلود فایل پاورپوینت مسائل با ارضاء محدودیت

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

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

اسلاید 2 :

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

اسلاید 3 :

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

اسلاید 4 :

انتسابي که هيچ محدوديتي را نقض نکند، انتساب سازگار نام دارد
انتساب کامل آن است که تمام متغيرها در آن باشد
راه حل CSP يک انتساب کامل است با توجه به اینکه تمام محدوديتها را برآورده می کند
بعضي از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنند

اسلاید 5 :

متغيرها: 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) برابر :
{(قرمز,سبز),(قرمز,آبي),(سبز,قرمز)، (سبز,آبي),(آبي,قرمز),(آبي,سبز)}

اسلاید 6 :

حالت اوليه: انتساب خالي{} که در آن، هيچ متغيري مقدار ندارد
عملگر: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطي که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشند
آزمون هدف: انتساب فعلي کامل است؟
هزينه مسير: هزينه ثابت براي هر مرحله

اسلاید 7 :

1- فرمول بندی افزايشی
با استفاده از اين فرمول بندي، هر يک از الگوريتم هاي جستجوي فصل هاي 3 و 4 مي توانند CSP را حل کنند.

2- فرمول بندی حالت کامل
با استفاده از جستجوهای محلی مسئله را حل کنند.

اسلاید 8 :

1- فرمول بندی افزايشی
با استفاده از اين فرمول بندي، هر يک از الگوريتم هاي جستجوي فصل هاي 3 و 4 مي توانند CSP را حل کنند.

2- فرمول بندی حالت کامل
با استفاده از جستجوهای محلی مسئله را حل کنند.

حالت اوليه: انتساب خالي{} که در آن، هيچ متغيري مقدار ندارد
عملگر: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطي که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشند
آزمون هدف: انتساب فعلي کامل است؟
هزينه مسير: هزينه ثابت براي هر مرحله

اسلاید 9 :

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

اسلاید 10 :

يک جست و جوي عمقي است.
انتخاب مقادير يک متغير در هر زمان و عقبگرد در صورت عدم وجود مقداري معتبر براي انتساب به متغير
يک الگوريتم ناآگاهانه است
براي مسئله هاي بزرگ کارآمد نيست.