با عرض سلام
این سوال رو تو یه کتاب من دیدم، آخرش نوشته که با روش سازگاری مرتبه ۲ نمی شه این رو حل کرد. تو یه کتاب دیگه نوشته می شه حل کرد. مگه سازگاری مرتبه ۲، همون سازگاری کمانی نیست ؟
بی زحمت یه توضیح مختصر هم راجع به بررسی جلو سو بدید، البته اگه زحمتی نیست.
با تشکر
به نظر من می تونه تشخیص بده. الگوریتم 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 هستش .پس برمیگرده عقب
مرسی دوستان
خیلی لطف کردید، موفق و پیروز باشید
سلام؛ پاسخ دوستان کاملا درسته؛
شما کافیه رنگ بکنید ؛ بعد بر طبق همسایگی ترتیب حذف با همسایه ها رو در نظر بگیرید؛ همیشه هم بدترین حالت از بین انتخاب ها رو در نظر بگیرید
یعنی اگه مسیری دارید و کمانی؛ شما مسیری که بدترین حالت انتخاب هاست رو در نظر بگیرید