Power Point

Report
‫مسائل ارضاء محدوديت‬
‫تهيه کننده‪ :‬عبدالرضا ميرزايي‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سرفصل مطالب‬
‫مسائل ارضاء محدوديت‬
‫كاربرد جستجوهاي عمومي در حل ‪CSP‬‬
‫جستجوي عقبگرد ‪ backtracking‬براي مسائل ارضاء‬
‫محدوديت‬
‫جستجوي محلي براي مسائل ارضاء محدوديت‬
‫‪2‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل ارضاء محدوديت‬
‫• مسأله جستجوي استاندارد‬
‫– حالت يك “ جعبه سياه” است – هر ساختار داده اي كه از تابع‬
‫حاالت بعدي‪ ،‬تابع هيوريستيك و تست هدف پشتيباني كند‪.‬‬
‫• ‪:CSP‬‬
‫– حالت توسط متغيرهاي ‪ Xi‬تعريف مي شود كه هر يك‬
‫مقاديرشان را از يك دامنه ‪ Di‬انتخاب مي کنند‪.‬‬
‫– تست هدف مجموعه اي از محدوديت ها مي باشد كه تركيبات‬
‫مجاز مقادير براي زيرمجموعه اي از متغيرها را مشخص مي‬
‫كند‪.‬‬
‫• امكان استفاده از الگوريتم هاي همه منظوره كه نسبت به‬
‫‪3‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم هاي استاندارد قدرت بيشتري دارند‪.‬‬
‫مثال‪ :‬رنگ آميزي نقشه‬
‫• متغيرها‪WA, NT, Q, NSW, V, SA, T :‬‬
‫• دامنه ها‪Di = {red,green,blue} :‬‬
‫• محدوديت ها‪ :‬نواحي همسايه بايد رنگ متفاوتي داشته باشند مثال‬
‫‪WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red),‬‬
‫})‪(green,blue), (blue,red),(blue,green‬‬
‫‪4‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال‪ :‬رنگ آميزي نقشه‬
‫• راه حل ها انتساب هاي كامل و سازگار مي باشند‪.‬‬
‫• مثال ‪:‬‬
‫‪WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green‬‬
‫‪5‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مزاياي بيان مسأله به صورت ‪CSP‬‬
‫• به دليل نمايش استاندارد حالت ها (مجموعه متغيرهايي با‬
‫مقدارشان)‪ ،‬مي توان تابع‪ Successor‬و آزمون هدف را به‬
‫شكل كلي نوشت به طوريكه براي هر‪ CSP‬قابل اعمال‬
‫باشد‪.‬‬
‫• مي توان هيوريستيك هاي كلي و كارايي ايجاد كرد كه نياز‬
‫به تخصص اضافي در دامنه خاص مسأله نداشته باشند‪.‬‬
‫‪6‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انواع مسائل ‪CSP‬‬
‫• متغيرهاي گسسته‬
‫– دامنه هاي محدود‪:‬‬
‫‪ n‬متغير‪ ،‬اندازه هر دامنه ‪ : d‬تعداد انتساب هاي كامل)‪O(dn‬‬
‫مثال ‪CSP‬هاي بولين‪ n ،‬وزير ‪ ،‬رنگ آميزي نقشه و ‪...‬‬
‫– دامنه هاي نامحدود‪:‬‬
‫اعداد صحيح‪ ،‬رشته ها و ‪...‬‬
‫مثال‪ :‬زمانبندي كارها‪ -‬متغيرها‪ ،‬زمان شروع‪/‬پايان هر كار هستند‪.‬‬
‫نياز به زبان محدوديت دارند‪ .‬مثال‪StartJob1 + 5 ≤ StartJob3 :‬‬
‫• متغيرهاي پيوسته‬
‫– مثال‪ :‬زمان هاي شروع و پايان مشاهدات تلسكوپ فضايي هابل‬
‫– اگر محدوديت ها خطي‪ :‬توسط برنامه ريزي خطي قابل حل در زمان‬
‫چندجمله اي مي باشند‪.‬‬
‫‪7‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انواع محدوديت ها‬
‫• يكاني (‪ )unary‬روي يك متغير تعريف مي شود‪،‬‬
‫• مثال‬
‫‪SA ≠ green‬‬
‫• دوگاني (‪ )binary‬محدوديت شامل يك زوج از متغيرها مي‬
‫باشد‪،‬‬
‫• مثال‬
‫‪SA ≠ WA‬‬
‫• محدوديت مرتبه باالتر(‪ )Higher-order‬شامل سه يا بيشتر‬
‫متغير است‪،‬‬
‫• مثال‪ :‬محدوديت هاي موجود در ستون هاي مسائل رياضيات رمزي‬
‫• در صورت متناهي بودن دامنه‪ ،‬مي تواند به تعدادي محدوديت دوديي‬
‫كاهش يابد‪.‬‬
‫‪8‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انواع محدوديت ها‬
‫• محدوديت مطلق‬
‫• محدوديت هايي که نبايد هيچ يک از آنها در راه حل نقض شود‪.‬‬
‫• محدوديت ترجيحي (نرم)‪:‬‬
‫‪preference constraint‬‬
‫• مثال‪ ،‬استاد تمايل به تدريس در صبح دارد‪.‬‬
‫• اغلب بوسيله در نظر گرفتن هزينه براي انتساب متغيرها‬
‫‪9‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫گراف محدوديت‬
‫• ‪ CSP‬دوگاني (‪)Binary CSP‬‬
‫• ‪ CSP‬که داراي محدوديت هاي دودويي‬
‫باشد‬
‫• گراف محدوديت‪:‬‬
‫ گره ها متغيرها را نشان مي دهند‪.‬‬‫ يالهاي گراف محدوديت ها ي بين‬‫متغيرها را نشان مي دهند‪.‬‬
‫‪10‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫گراف محدوديت مثال‬
‫رنگ آميزي نقشه‬
‫ رياضيات رمزي‬:‫مثال‬
• Variables: F T U W R O X1 X2 X3
• Domains: {0,1,2,3,4,5,6,7,8,9}
• Constraints: Alldiff (F,T,U,W,R,O)
•
•
•
•
O + O = R + 10 · X1
X1 + W + W = U + 10 · X2
X2 + T + T = O + 10 · X3
X3 = F, T ≠ 0, F ≠ 0
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
11
‫مسائل ارضاء محدوديت در دنياي واقعي‬
‫• مسائل انتسابي‬
‫‪Assignment problems‬‬
‫– مثال‪ ،‬چه كسي چه كالسي را درس مي دهد‪.‬‬
‫• مسائل تعيين جدول زمانبندي‬
‫‪Timetabling problems‬‬
‫– مثال‪ ،‬كدام كالس‪ ،‬كجا وكي ارائه مي شود؟‬
‫• زمانبندي حمل و‬
‫• زمانبندي كارخانه ‪Factory scheduling‬‬
‫• توجه‪ :‬بسياري از مسائل در دنياي واقعي شامل متغيرهايي‬
‫با مقادير حقيقي مي باشند‪.‬‬
‫نقل‪Transportation scheduling‬‬
‫‪12‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫فرموله سازي جستجوي استاندارد(افزايشي)‬
‫• حاالت توسط مقاديري كه تا كنون انتساب يافته اند‪ ،‬تعريف مي‬
‫شوند‪.‬‬
‫• حالت اوليه‪ :‬تمام متغيرها بدون مقدار‪ ،‬يعني انتساب تهي‬
‫• عملگرها‪ :‬انتساب مقدار به يك متغير بدون مقدار به طوري كه با انتساب‬
‫فعلي تناقض ايجاد نكند‬
‫• در صورت عدم وجود انتساب هاي مجاز شكست مي خورد‪.‬‬
‫• تست هدف‪ :‬انتساب فعلي كامل باشد‪.‬‬
‫• هزينه مسير‪ :‬هزينه يكسان براي تمام مراحل‬
‫• محدوديت ها را مي توان به دو روش نمايش داد‪:‬‬
‫• صريح‪ :‬به عنوان مجموعه اي از مقادير مجاز‬
‫• ضمني‪ :‬بوسيله تابعي كه ارضاء محدوديت ها را بررسي مي كند‪.‬‬
‫‪13‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫فرموله سازي جستجوي استاندارد(افزايشي)‬
‫•‬
‫•‬
‫•‬
‫•‬
‫براي تمام ‪ csp‬ها يکسان است‪.‬‬
‫هر پاسخ در عمق ‪ n‬و با ‪ n‬متغير ظاهر مي شود‪.‬‬
‫در عمق ‪ l‬فاکتور انشعاب برابر است با ‪(n - l)d‬‬
‫بنابراين تعداد برگهاي درخت جستجو برابر است با ‪n! · dn‬‬
‫‪(nd) * [(n-1)d] * [(n-2)d] * … d = n!dn‬‬
‫مثال در ‪-8‬وزير‪:‬‬
‫اين موارد مي توانند با توجه به نكات زير بهبود يابند‪:‬‬
‫‪8!.88‬‬
‫• ترتيب انتساب مقادير به متغيرها اهميت ندارد‪ ،‬پس بسياري از مسيرها‬
‫معادل يكديگر مي باشند‪ .‬در ‪-8‬وزير اندازه فضاي حالت از ‪ 8!.88‬به‬
‫کاهش ‪ 88‬مي يابد‬
‫کامپيوترشده را تصحيح كنند‪.‬‬
‫محدوديتبرق ونقض‬
‫صنعتييك‬
‫توانند‬
‫‪ •14‬انتساب هاي بعدي نمي‬
‫اصفهان دانشکده‬
‫دانشگاه‬
‫جستجوي ‪Backtracking‬‬
‫• انتساب متغيرها جابه جايي پذير است مثال‬
‫] ‪[ WA = red then NT = green‬برابر است با‬
‫•‬
‫•‬
‫•‬
‫•‬
‫] ‪[ NT = green then WA = red‬‬
‫در هر گره تنها بايد انتساب هاي يك متغير در نظر گرفته شود؛پس‬
‫‪ b=d‬و تعداد برگها برابر است با ‪dn‬‬
‫جستجوي اول‪ -‬عمق با انتساب هاي يك متغير جداگانه در‪ CSP‬ها‬
‫‪ backtracking‬نام دارد‪ .‬جستجوي ناآگاهانه استاندارد‪.‬‬
‫قرار دادن يك آزمون قبل از بسط گره ها كه بررسي مي كند آيا‬
‫تاكنون محدوديتي نقض شده يا خير‪ .‬اگر محدوديتي نقض شده باشد‪،‬‬
‫ديگر اين گره بسط داده نمي شود و جستجو به عقب باز مي گردد‪.‬‬
‫مي تواند ‪-n‬وزير را تا ‪ n‬حدود ‪ 25‬حل کند‬
‫‪15‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي ‪Backtracking‬‬
‫‪16‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال ‪Backtracking‬‬
‫‪17‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال ‪Backtracking‬‬
‫‪18‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال ‪Backtracking‬‬
‫‪19‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال ‪Backtracking‬‬
‫‪20‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫بهبود كارآيي ‪Backtracking‬‬
‫• افزايش سرعت توسط روش هاي جستجوي همه منظوره‪:‬‬
‫• در مرحله بعد بايد به كدام متغير مقدار داده شود؟‬
‫• مقادير آن بايد به چه ترتيبي امتحان شوند؟‬
‫• آيا مي توان شكست هاي حتمي را زودتر تشخيص داد؟‬
‫• فرض كنيد در عقبگرد در مسأله ‪ -8‬وزير‪ 6 ،‬وزير اول به گونه اي‬
‫قرار گرفته اند كه قرار دادن هشتمين وزير را غير ممكن مي سازند‪.‬‬
‫عقب گرد تمام مكانهاي ممكن براي وزير هفتم را چك مي كند‪ ،‬اگرچه‬
‫مسأله غير قابل حل مي باشد‪.‬‬
‫• آيا مي توان از ساختار مسأله بهره گرفت؟‬
‫‪21‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مرتب سازي مقدار و متغير‬
‫• متغير با بيشترين محدوديت ‪:‬‬
‫‪Most constrained variable‬‬
‫– متغيري را انتخاب كن كه كمترين مقادير معتبر را دارد‪.‬‬
‫• هيوريستيك كمترين مقادير باقيمانده (‪)Minimum remaining value‬‬
‫• هيوريستيك اول شکست (‪)Fail first‬‬
‫‪22‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫محدودکننده ترين متغير‬
‫• در حالت تساوي ميان متغيرهايي كه بيشترين محدوديت را‬
‫دارند‬
‫• محدودکننده ترين متغير‬
‫‪Most constraining variable‬‬
‫• هيوريستيك درجه‬
‫• متغير با بيشترين محدوديت را روي مقادير باقيمانده انتخاب كن‬
‫‪23‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مقدار با حداقل محدوديت‬
‫• براي يك متغير‪ ،‬مقداري را كه كمترين محدوديت را ايجاد مي‬
‫كند انتخاب كن‪.‬‬
‫• مقداري كه كمترين مقادير را از متغيرهاي باقيمانده حذف مي كند‬
‫• با تركيب اين هيوريستيك ها مسأله ‪- 1000‬وزير قابل حل مي‬
‫شود‪.‬‬
‫‪24‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫وارسي رو به جلو‬
‫‪Forward checking‬‬
‫• ايده‪:‬‬
‫– سابقه مقادير مجاز باقيمانده براي متغيرهاي بدون مقدار را نگهداري کن‪.‬‬
‫– زماني كه يك متغير هيچ مقدار مجاز باقيمانده اي ندارد‪ ،‬به جستجو پايان‬
‫بده‪.‬‬
‫‪25‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫وارسي رو به جلو‬
‫‪Forward checking‬‬
‫• ايده‪:‬‬
‫– سابقه مقادير مجاز باقيمانده براي متغيرهاي بدون مقدار را نگهداري کن‪.‬‬
‫– زماني كه يك متغير هيچ مقدار مجاز باقيمانده اي ندارد‪ ،‬به جستجو پايان‬
‫بده‪.‬‬
‫‪26‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫وارسي رو به جلو‬
‫‪Forward checking‬‬
‫• ايده‪:‬‬
‫– سابقه مقادير مجاز باقيمانده براي متغيرهاي بدون مقدار را نگهداري کن‪.‬‬
‫– زماني كه يك متغير هيچ مقدار مجاز باقيمانده اي ندارد‪ ،‬به جستجو پايان‬
‫بده‪.‬‬
‫‪27‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫وارسي رو به جلو‬
‫‪Forward checking‬‬
‫• ايده‪:‬‬
‫– سابقه مقادير مجاز باقيمانده براي متغيرهاي بدون مقدار را نگهداري کن‪.‬‬
‫– زماني كه يك متغير هيچ مقدار مجاز باقيمانده اي ندارد‪ ،‬به جستجو پايان‬
‫بده‪.‬‬
‫‪28‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انتشار محدوديت‬
‫‪Constraint propagation‬‬
‫• وارسي رو به جلو محدوديت ها را از متغيرهاي انتساب يافته به متغير هاي‬
‫انتساب نيافته منتشر مي كند‪ ،‬اما تمام شكست ها را نمي تواند در زود ترين‬
‫زمان ممكن تشخيص دهد‪.‬‬
‫• ‪ NT‬و ‪ SA‬هر دو نمي توانند آبي باشند!‬
‫• انتشار محدوديت به طور مكرر بر محدوديت ها به طور محلي تأكيد دارد‪.‬‬
‫‪29‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري كمان‬
‫‪Arc consistency‬‬
‫• ساده ترين شكل انتشار‪ ،‬هر كمان را سازگار مي كند‪.‬‬
‫• ‪ X Y‬سازگار است اگر و فقط اگر بازاء هر مقدار ‪ x‬تعدادي مقدار مجاز‬
‫‪ y‬وجود داشته باشد‪.‬‬
‫‪30‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري كمان‬
‫‪Arc consistency‬‬
‫• ساده ترين شكل انتشار‪ ،‬هر كمان را سازگار مي كند‪.‬‬
‫• ‪ X Y‬سازگار است اگر و فقط اگر بازاء هر مقدار ‪ x‬تعدادي مقدار مجاز‬
‫‪ y‬وجود داشته باشد‪.‬‬
‫‪31‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري كمان‬
‫‪Arc consistency‬‬
‫• ساده ترين شكل انتشار‪ ،‬هر كمان را سازگار مي كند‪.‬‬
‫• ‪ X Y‬سازگار است اگر و فقط اگر بازاء هر مقدار ‪ x‬تعدادي مقدار مجاز‬
‫‪ y‬وجود داشته باشد‪.‬‬
‫• اگر ‪ X‬مقداري را از دست بدهد‪ ،‬همسايه هاي ‪ X‬نياز به بررسي مجدد دارند‪.‬‬
‫‪32‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري كمان‬
‫‪Arc consistency‬‬
‫• ساده ترين شكل انتشار‪ ،‬هر كمان را سازگار مي كند‪.‬‬
‫• ‪ X Y‬سازگار است اگر و فقط اگر بازاء هر مقدار ‪ x‬تعدادي مقدار مجاز‬
‫‪ y‬وجود داشته باشد‪.‬‬
‫• اگر ‪ X‬مقداري را از دست بدهد‪ ،‬همسايه هاي ‪ X‬نياز به بررسي مجدد دارند‪.‬‬
‫• سازگاري كمان شكست ها را زودتر از ‪ forward checking‬تشخيص مي دهد‬
‫و مي تواند به عنوان پيش پردازش و يا بعد از هر انتساب اجرا شود‪.‬‬
‫‪33‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‬
‫‪Arc consistency AC-3‬‬
‫• پيچيدگي زماني )‪O(n2d3‬‬
‫‪34‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري مرتبة ‪ k‬ام‬
‫‪ AC3‬قادر به تشخيص ناسازگاري روبرو نيست‬
‫ناسازگار‬
‫اَشكال قويتري از انتشار محدوديت‬
‫• سازگاري مرتبة ‪ k‬ام‬
‫• يک ‪ CSP‬داراي سازگاري مرتبة ‪ k‬است اگر براي هر مجموعة‬
‫‪ k-1‬عضوي از متغيرها و براي هر انتساب سازگار به آنها‪،‬‬
‫هميشه يك مقدار سازگار يافت شود كه بتوان به هر متغير‪k‬ام‬
‫انتساب داد‪.‬‬
‫‪35‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري مرتبة ‪ k‬ام‬
‫‪ ‬سازگاري مرتبة ‪ 1‬يا سازگاري گره به معناي آن است كه هر متغير‬
‫با خودش سازگار مي باشد‪.‬‬
‫‪ ‬سازگاري مرتبة ‪ 2‬مشابه سازگاري كمان است‪.‬‬
‫‪ ‬سازگاري مرتبة ‪ 3‬به معناي آن است كه هر زوج متغير مجاور‪،‬‬
‫قابل گسترش به سه متغير مجاور باشند؛ كه به سازگاري مسير‬
‫معروف است‪.‬‬
‫‪36‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سازگاري قوي مرتبة ‪ k‬ام‬
‫• يك گراف‪ ،‬داراي سازگاري شديد مرتبة ‪ k‬مي باشد‪ ،‬در صورتي كه‬
‫داراي سازگاري مرتبة سازگاري ‪ ،k-1‬مرتبة ‪ ،k-2‬تا سازگار مرتبة‬
‫‪ 1‬نيز باشد‪.‬‬
‫• يک ‪ CSP‬با ‪ n‬گره داريم كه داراي سازگاري قوي مرتبة ‪ n‬است‬
‫• در ابتدا‪ ،‬يك مقدار سازگار را براي ‪ x1‬انتخاب مي کنيم‪ .‬از آنجا‬
‫كه گراف داراي سازگاري مرتبة ‪ 2‬مي باشد‪ ،‬مطمئن هستيم كه‬
‫مي توان مقداري سازگار يافت كه بتوان به ‪ x2‬اختصاص داد و‬
‫به ترتيب‪ ،‬مي توان مقاديري سازگار براي بقيه متغيرها يافت‬
‫• مي توان اين مسأله را بدون انجام عقب گرد‪ ،‬حل كرد‪.‬‬
‫• راه حل مسأله حداكثر با مرتبة زماني )‪ O(nd‬پيدا مي شود‪.‬‬
‫‪37‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫برخورد با محدوديتهاي ويژه‬
‫• مثال محدوديت ‪Alldiff‬‬
‫• تمامي متغيرها بايد داراي مقادير متفاوتي باشند‪.‬‬
‫• يك شكل ساده از ايجاد ناسازگاري براي اين محدوديت بدين صورت‬
‫است‪ :‬اگر ‪ m‬متغير شامل اين محدوديت باشند ولي تنها ‪ n‬مقدار‬
‫مجموع براي انتساب موجود باشد )‪ ،(n<m‬ديگر اين محدوديت‬
‫نمي تواند برآورده شود‪.‬‬
‫‪38‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫برخورد با محدوديتهاي ويژه‬
‫• مثال محدوديت ‪Alldiff‬‬
‫• راه حل مسئله‪:‬‬
‫• در ابتدا تمام متغيرهايي كه داراي دامنة واحد مي باشند را حذف‬
‫و مقدار مربوط به دامنة آنها را نيز از دامنة ساير متغيرها حذف‬
‫مي كنيم‪.‬‬
‫• اين كار را براي تمام متغيرهاي تك مقداره تكرار مي نماييم‪.‬‬
‫• اگر در پايان دامنة يك متغير تهي شود يا تعداد متغير بيشتري از‬
‫تعداد مقادير دامنه‪ ،‬باقي مانده باشد‪ ،‬ناسازگاري در مسأله‬
‫تشخيص داده خواهد شد‪.‬‬
‫‪39‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫برخورد با محدوديتهاي ويژه‬
‫• مثال محدوديت منبع (محدوديت بيشينه)‬
‫• در نظر بگيريد ‪ PA1,…,PA4‬به تعداد افرادي اشاره مي كند كه براي‬
‫انجام چهار كار متفاوت در نظر گرفته شده اند‪.‬‬
‫• محدوديتي كه براساس آن‪ ،‬تعداد افراد در مجموع نبايد از ‪ 10‬نفر‬
‫تجاوز نمايد به صورت )‪ atmost (10,PA1,PA2,PA3,PA4‬نمايش‬
‫داده مي شود‪.‬‬
‫‪40‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫برخورد با محدوديتهاي ويژه‬
‫• مثال محدوديت منبع (محدوديت بيشينه)‬
‫• مي توان با بررسي مجموع حداقل مقادير دامنه هاي فعلي‪،‬‬
‫ناسازگاري را تشخيص داد‪.‬‬
‫• مثالً اگر هر متغير داراي دامنة { ‪ } 3،4،5،6‬باشد‪ ،‬محدوديت بيشينه‪ ،‬تأمين‬
‫نمي شود‪.‬‬
‫• مي توان براي اعمال سازگاري‪ ،‬مقدار بيشينه در هر دامنه را‪ ،‬به‬
‫شرطي كه با مقدار كمينه در دامنه هاي ديگر ناسازگار باشد‪ ،‬حذف‬
‫نمود‪.‬‬
‫• اگر هر متغيري در مثال فوق‪ ،‬داراي دامنة { ‪ } 2،3،4،5،6‬باشد‪ ،‬مي توان‬
‫به منظور رسيدن به سازگاري‪ ،‬مقادير ‪ 5‬و ‪ 6‬را از دامنة متغيرها حذف‬
‫نمود‪.‬‬
‫‪41‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫عقبگرد هوشمندانه‪ :‬نگاه رو به عقب‬
‫• در الگوريتم ‪ BACKTRACKING-SEARCH‬هنگامي كه يكي از شاخه ها‬
‫با شكست در جستجو مواجه مي شود‪ ،‬الگوريتم به متغير قبلي باز مي‬
‫گردد و مقداري جديد براي آن در نظر مي گيرد‪.‬‬
‫• يك روش پس گرد هوشمندانه تر آن است كه تمام مسير را تا رسيدن به‬
‫مجموعه اي از متغيرها كه باعث شكست شده اند(مجموعة تناقض)‪ ،‬به‬
‫عقب باز گرديم‪.‬‬
‫• مجموعة تناقض براي متغير ‪ x‬عبارت است از مجموعه اي از متغيرهايي كه‬
‫قبالً مقداردهي شده اند و به واسطة يك محدوديت با ‪ x‬در ارتباطند‪.‬‬
‫• اين روش (روش پرش رو به عقب)‪ ،‬مسير پيموده شده را تا رسيدن به‬
‫آخرين متغيري كه در مجموعة تناقض مقداردهي شده است‪ ،‬به عقب‬
‫مي پيمايد‪.‬‬
‫‪42‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫عقبگرد هوشمندانه‪ :‬نگاه رو به عقب‬
‫•‬
‫•‬
‫•‬
‫•‬
‫هيچ مقداري براي ‪ SA‬موجود نيست‬
‫تغيير رنگ ‪ T‬کمکي به‪ SA‬نمي کند‬
‫مجموعه تناقض ‪ SA‬برابر است با }‪{Q, NSW, V‬‬
‫الگوريتم دنبال مقدار جديدي براي ‪ V‬خواهد گشت‬
‫‪43‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫عقبگرد هوشمندانه‪ :‬نگاه رو به عقب‬
‫•‬
‫•‬
‫•‬
‫•‬
‫پرش رو به عقب هنگامي رخ مي دهد كه هر مقدار متعلق به دامنه‬
‫با انتساب انجام شده داراي تناقض باشد‪.‬‬
‫وارسي روبه جلو اين حالت را تشخيص مي دهد و از رسيدن به آن‬
‫جلوگيري مي كند‪.‬‬
‫هر شاخه اي كه به وسيلة پرش رو به عقب هرس مي شود‪ ،‬مي‬
‫تواند به وسيلة انجام وارسي رو به جلو نيز هرس شود‪.‬‬
‫پرش رو به عقب ساده‪ ،‬در جستجوهايي كه از روشهاي قويتر‬
‫بررسي سازگاري نظير ‪ MAC‬استفاده مي كنند زائد است‪.‬‬
‫‪44‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫پس گرد هوشمندانه‪ :‬نگاه رو به عقب‬
‫• الگوريتم پرش رو به عقب هم جهت با تناقض‪:‬‬
‫‪conflict directed backjumping‬‬
‫• روش محاسبة مجموعه هاي تناقض‪ :‬شكست نهايي در يك مسير از‬
‫الگوريتم جستجو هنگامي رخ مي دهد كه دامنة يك متغير‪ ،‬تهي‬
‫تشخيص داده شود‪ .‬آن متغير داراي يك مجموعة تناقض استاندارد‬
‫مي باشد‪.‬‬
‫• در نظر بگيريد كه ‪ Xj‬متغير فعلي و )‪ conf(Xj‬مجموعة تناقض آن‬
‫باشد‪.‬‬
‫• اگر تمام مقادير ممكن براي ‪ Xj‬با با شكست مواجه شوند‪ ،‬الگوريتم‬
‫به ‪ Xi‬برخواهد گشت كه آخرين متغير مقدار داده شده و متعلق به‬
‫کامپيوتر انجام مي دهيم‪:‬‬
‫زير را‬
‫صنعتيو‬
‫دانشگاهباشد‬
‫‪45‬مجموعة تناقض ‪ Xj‬مي‬
‫انتساببرق و‬
‫اصفهان دانشکده‬
‫عقبگرد هوشمندانه‪ :‬نگاه رو به عقب‬
‫•‬
‫•‬
‫•‬
‫•‬
‫انتساب جزئي روبرو ناسازگار است‪.‬‬
‫فرض در مرحله بعد ‪ T=red‬مقداردهي شود و سپس متغيرهاي‬
‫‪ V ،Q ،NT‬و ‪ SA‬مقدار دهي شوند‪.‬‬
‫انتساب همزمان به ‪ 4‬متغير جديد منجر به شکست‬
‫الگوريتم پرش رو به عقب هم جهت با تناقض پس از رسيدن به‬
‫شکست به ‪ NSW‬بر مي گردد‬
‫‪46‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي محلي براي ‪CSP‬‬
‫• ‪ Sa‬و تپه نوردي با حاالت كامل كار مي كنند‬
‫• حالت اوليه‪ ،‬يك مقدار را به هر يك از متغيرها اختصاص مي‬
‫دهد‪.‬‬
‫• تابع پسين معموالً هر بار مقدار يكي از متغيرها را تغيير مي‬
‫دهد‪.‬‬
‫• انتخاب متغير‪:‬‬
‫• به صورت تصادفي يك متغير درگير را انتخاب كن‬
‫• هيوريستيک ‪min-conflicts :‬‬
‫• مقداري را انتخاب كن كه كمترين تعداد محدوديت ها را نقض‬
‫‪ 47‬مي كند‪،‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم ‪Min-Conflicts‬‬
‫‪48‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي محلي براي ‪CSP‬‬
‫• مثال‪ :‬در مساله ‪ 8‬وزير‪:‬‬
‫• حالت اوليه قرار دادن ‪ 8‬وزير در ‪ 8‬ستون جدول به صورت‬
‫تصادفي‬
‫• تابع پسين يكي از وزيرها را انتخاب مي نمايد و موقعيتش را در‬
‫ستون مربوطه تغيير مي دهد‪.‬‬
‫• امكان ديگر آن است كه با هر هشت وزير شروع نماييم و با‬
‫جايگشت رديفها‪ ،‬هر يك را در يك ستون قرار دهيم و پسين‬
‫آنها با عوض كردن موقعيت دو وزير با هم ايجاد شود‪.‬‬
‫‪49‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال ‪- 8 :‬وزير‬
‫• راه حل دو مرحله اي براي مسألة ‪ 8‬وزير با استفاده از‬
‫الگوريتم ‪Min-Conflicts‬‬
‫• اين روش حتي با در نظر گرفتن تعداد يك ميليون وزير‪ ،‬مسأله را‬
‫به طور متوسط در ‪ 50‬مرحله حل مي كند (پس از جايگذاري اوليه‬
‫مهره ها)‪.‬‬
‫• از آنجا كه در مساله ‪ n‬وزير‪ ،‬حالتهاي هدف به طور متراكم در‬
‫فضاي حالت توزيع شده اند‪ ،‬روش جستجوي محلي درمورد آن‬
‫بسيار مفيد واقع مي شود‪.‬‬
‫‪50‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ساختار مسأله‬
‫• ‪ Tasmania‬و جزيره اصلي زيرمسايل مستقل هستند‪.‬‬
‫• با توجه به مولفه هاي همبند در گراف محدوديت قابل‬
‫شناسايي هستند‪.‬‬
‫‪51‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ساختار مسأله‬
‫• فرض كنيد هر زيرمسأله شامل ‪ c‬متغير از ‪ n‬متغير باشد‬
‫• هزينه راه حل در بدترين حالت خطي(برحسب ‪ )n‬و برابر ‪n/c‬‬
‫‪ . dc‬مي باشد‬
‫• مثال ‪n = 80, d = 2, c =20‬‬
‫‪• 280 = 4 billion years at 10 million nodes/sec‬‬
‫‪• 4.220 = 0.4 seconds at 10 million nodes/sec‬‬
‫‪52‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم براي ‪CSP‬هاي داراي ساختار درختي‬
‫•‬
‫يك متغير را به عنوان ريشه انتخاب كن و سپس متغيرها را از‬
‫ريشه تا برگها به گونه اي مرتب كن كه والد هر گره قبل از آن‬
‫گره قرار بگيرد‪.‬‬
‫•‬
‫به ازاي ‪ j‬از ‪ n‬تا ‪ 2‬عمل زير را انجام بده‪.‬‬
‫)‪REMOVEINCONSISTENT(Parent(Xj),Xj‬‬
‫• براي ‪ j‬از ‪ 1‬تا ‪ n‬مقدار ‪ Xj‬را به طور سازگار با )‪ Parent(Xj‬تعيين‬
‫کن‪.‬‬
‫صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫•‪53‬پيچيدگي زماني‪ 2) :‬دانشگاه‬
‫‪O(n.d‬‬
‫تقليل گراف محدوديت به حالت درختي‬
‫• راهکار اول‪ :‬حذف يک سري از نودها‬
‫• زير مجموعه اي از متغيرها (در تمام حاالت ممكن) را مقدار دهي كن به‬
‫طوريكه گراف محدوديت باقيمانده يك درخت شود‪Cycle cutset .‬‬
‫• به يك متغير مقدار بده؛ دامنه همسايه هاي آن را هرس كن‬
‫• اگر اندازه ‪ Cycle cutset‬برابر ‪ c‬باشد زمان اجرا )‪O(dc . (n - c)d2‬‬
‫‪54‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تقليل گراف محدوديت به حالت درختي‬
‫• راهکار دوم‪ :‬تجزيه درختي‬
‫‪55‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تجزيه درختي‬
‫• شرايط تجزيه درختي‪:‬‬
‫– هر متغير در مسأله اصلي بايد حداقل در يك زيرمسأله ظاهر‬
‫شود‬
‫– اگر دو متغير به وسيله محدوديتي در مسأله اصلي متصل شده‬
‫باشند‪ ،‬آنگاه آن دو متغيربا هم(به همراه محدوديت) بايد حداقل‬
‫در يك زير مسأله ظاهر شوند‪.‬‬
‫– اگر متغيري در درخت در دو زير مسأله ظاهر شده باشد‪ ،‬آنگاه‬
‫بايد در هر زيرمسأله در طول مسيري كه زيرمسايل را متصل‬
‫مي كند‪ ،‬ظاهر شود‪.‬‬
‫‪56‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تجزيه درختي‬
‫• حل تجزيه درختي‪:‬‬
‫• هر زير مساله به صورت مجزا حل مي شود‬
‫• اگر هر يک از زير مسائل داراي راه حلي نباشد مساله اصلي‬
‫نيز هيچ راه حلي ندارد‪.‬‬
‫• اگر بتوانيم تمام زيرمسائل را حل کنيم‬
‫‪57‬‬
‫• هر زير مسأله را به صورت يك متغير بزرگ در نظر مي‬
‫گيريم که كه دامنه آن مجموعه تمام راه حل هاي ممكن آن زير‬
‫مسأله مي باشد‪.‬‬
‫• سپس محدوديت هاي ميان زير مسايل را با استفاده از الگوريتم‬
‫كاراي درخت حل مي كنيم‪.‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تجزيه درختي‬
‫راه حلهاي مربوط به هر زير مساله بايد در مقادير انتساب‬
‫داده شده به متغيرهاي مشترک يکسان باشند‪.‬‬
‫مثال اگر پاسخ اولين زير مسأله انتساب زير باشد‪:‬‬
‫}‪{WA = red, SA= blue, NT = green‬‬
‫آنگاه تنها پاسخ سازگار براي زير مسأله بعدي انتساب زير مي‬
‫باشد‪:‬‬
‫}‪{SA = blue, NT = green, Q = red‬‬
‫‪ Tree width=w‬کم کردن يک واحد از اندازه بزرگترين زير‬
‫مساله پس از تجزيه درختي‬
‫‪ 58‬پيچيدگي زماني‪O(n . dw+1) :‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬

similar documents