توضیحات

در جلسه هشتم هوش مصنوعی استاد انصاری با عنوان «ارضای محدودیت، جستجوی عقبگرد و انتشار محدودیت»، فصل ششم درس هوش مصنوعی (مسائل ارضای محدودیت) آغاز می‌شود. دو مطلب مهم در این جلسه مورد بحث و بررسی قرار می‌گیرند: 1) تعریف مسائل ارضای محدودیت 2) جستجوی عقبگرد و انتشار محدودیت. ابتدا مسائل ارضای محدودیت تعریف و تشریح می‌گردد و مسئله نمونه رنگ آمیزی نقشه در مورد آن به طور دقیق مطرح، فرموله و حل می‌شود. همچنین گراف محدودیت برای حل آن شرح داده می‌شود. سپس مسئله نمونه N وزیر مطرح و انواع محدودیت‌ها در مورد آن بیان می‌گردد. پس از آن، مسئله نمونه معمای اعداد مطرح شده و متغیرها، دامنه‌ها و محدودیت‌های آن شرح داده می‌شود. چهارمین مسئله نمونه، جدول سودوکو خواهد بود که متغیرها، دامنه‌ها و محدودیت‌های آن نیز تشریح می‌گردد. سپس انواع مسائل CSP (مسائل با متغیرهای گسسته و مسائل با متغیرهای پیوسته) شرح داده می‌شود. آنگاه به حل مسائل ارضای محدودیت پرداخته می‌شود. الگوریتم جستجوی عمقی که از دو ایده استفاده می‌کند با ذکر ایده‌های مربوطه با نام جستجوی عقبگرد به طور دقیق شرح داده شده و جزئیات آن در قالب شبه‌کد بیان می‌گردد. سپس به عنوان تمرین، الگوریتم جستجوی عقبگرد برای مسئله 4-وزیر تا رسیدن به یک جواب اجرا می‌شود. آنگاه هیوریستیک‌های ترتیب‌دهی مطرح و شرح داده می‌شود. در ادامه، فیلتر کردن، فیلتر کردن فوروارد چکینگ، فیلتر کردن انتشار محدودیت، سازگاری یال و الگوریتم سازگاری یال (𝐴𝐶 − 3) با جزئیات بسیار دقیق مورد بحث و بررسی قرار می‌گیرند. سپس با یک مثال، الگوریتم AC-3 روی یک گراف نمونه اعمال می‌شود. پس از آن به عنوان تمرین، جستجوی عقبگرد به همراه سازگاری یال برای مسئله 4-وزیر اجرا می‌گردد. در انتها 3 تست مهم هوش مصنوعی در خصوص مطالب این جلسه که در کنکور کارشناسی ارشد مهندسی کامپیوتر یا فناوری اطلاعات آمده‌اند مطرح شده و پاسخ تشریحی آنها ارائه می‌گردد.