مسایل ارضای محدودیت
جواب فوری
مسئله ارضای محدودیت برای اختصاص کلاس ها به اساتید را در نظر بگیرید فرض کنید 4 استاد p1 تا p4 و سه کلاس C1 تا C3 داریم می خواهیم اتاق ها را به اساتید اختصاص بدهیم و می دانیم استاد ها در زمان های زیر به کلاس احتیاج دارند:
9 صبح تا 11 صبح=p1
10 صبح تا 2 ظهرp2
1ظهر تا 5 عصر p3
1 ظهر تا 3 ظهرp4
می دانیم هر کلاس در یک زمان, فقط توسط یک استاد قابل استفاده است و کلاس C3 برای برای دانشجویان استاد p1 و کلاس های C2 و C3 برای دانشجویان استاد p3 ظرفیت لازم را ندارند.
الف) گراف محدودیت را برای این مسئله رسم کنید.
ب) به روش backtraching و با forward checking دامنه هر یک از متغیرها را در هر مرحله و هر یک از تخصیص ها یی را که در هر گام رخ می دهند در جدول زیر بنویسید . در موارد با اولویت برابر , به عدد کوچکتر اولویت دهید.
تخصیص ها p4 p3 p2 p1
دامنه اولیه C1,C2,C3 C1,C2
C1 C1=p1
|