به نظر من می تونه تشخیص بده. الگوریتم AC-3 برای همینه که ناسازگاری های یال رو تشخیص بده و رفع کنه
این جا یال ED ناسازگاری داره که با حذف Green از دامنه E رفع میشه. یال DB ناسازگاری داره که با حذف Green از دامنه B رفع میشه. یال BE هم ناسازگاری داره که اگه مقدار Blue رو تو یکی از طرفین حذف کنیم تناقض رخ میده. پس سازگاری یال برقرار نیست.


برای سوال دوم منظورتوی الگوریتم FC هست؟

(۱۵ فروردین ۱۳۹۶ ۰۷:۱۵ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
این سوال رو تو یه کتاب من دیدم، آخرش نوشته که با روش سازگاری مرتبه ۲ نمی شه این رو حل کرد. تو یه کتاب دیگه نوشته می شه حل کرد. مگه سازگاری مرتبه ۲، همون سازگاری کمانی نیست ؟
بی زحمت یه توضیح مختصر هم راجع به بررسی جلو سو بدید، البته اگه زحمتی نیست.
با تشکر

سلام , روش سازگاری برای حل کردن مساله نیست و فقط تشخیص میده که بعدا ممکنه تناقض پیش بیاد یا نه . بعد سازگاری مسیر سازگاری مرتبه ۳ هستش. سازگاری مرتبه ۳ میگه که اگه به ۲ شهر x1 و x2 هر مقدار معتبر داخل دامنه شان بدی برای شهر سوم y که همسایه مشترک x1 و x2 ( مجاوره این ۲تا) است مقداری پیدا میشه که بدی! خب با این شرایط اولیه که گفته شده برای D فقط سبز میمونه و برای E و B هم سبز باقی مونده اگه برای B یا E سبز انتخاب کنی دیگه نمیشه به D رو هیچ رنگی کرد! پس سازگاری مسیر conflict رو تشخیص میده

forward checking : هیچ ترتیبی مشخص نمیکنه و فقط وجود conflict رو در قدم بعدی مشخص میکنه . چجوری ؟ میاد هر گره که رنگ میشه , اون رنگ رو از دامنه ی بقیه گره های مجاور این گره حذف میکنه و دییگه رنگ هایی که از دامنه حذف شده برای گره ها بررسی نمیشه . بعد اگه رنگ کردن یه گره باعث بشه که دامنه ی یکی از گره های دیگه تهی بشه نشانه ی conflict هستش .پس برمیگرده عقب