زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۳:۳۰ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مسئله ی ارضای محدودیت - سراسری ۸۹

ارسال:
  

ali.majed.ha پرسیده:

مسئله ی ارضای محدودیت - سراسری ۸۹

با عرض سلام
این سوال رو تو یه کتاب من دیدم، آخرش نوشته که با روش سازگاری مرتبه ۲ نمی شه این رو حل کرد. تو یه کتاب دیگه نوشته می شه حل کرد. مگه سازگاری مرتبه ۲، همون سازگاری کمانی نیست ؟
بی زحمت یه توضیح مختصر هم راجع به بررسی جلو سو بدید، البته اگه زحمتی نیست.
با تشکر


فایل‌(های) پیوست شده


نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

پرهوده پاسخ داده:

RE: مسئله ی ارضای محدودیت - سراسری ۸۹

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


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

۰
ارسال:
  

kilookiloo پاسخ داده:

RE: مسئله ی ارضای محدودیت - سراسری ۸۹

(۱۵ فروردین ۱۳۹۶ ۰۷:۱۵ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
این سوال رو تو یه کتاب من دیدم، آخرش نوشته که با روش سازگاری مرتبه ۲ نمی شه این رو حل کرد. تو یه کتاب دیگه نوشته می شه حل کرد. مگه سازگاری مرتبه ۲، همون سازگاری کمانی نیست ؟
بی زحمت یه توضیح مختصر هم راجع به بررسی جلو سو بدید، البته اگه زحمتی نیست.
با تشکر
سلام , روش سازگاری برای حل کردن مساله نیست و فقط تشخیص میده که بعدا ممکنه تناقض پیش بیاد یا نه . بعد سازگاری مسیر سازگاری مرتبه ۳ هستش. سازگاری مرتبه ۳ میگه که اگه به ۲ شهر x1 و x2 هر مقدار معتبر داخل دامنه شان بدی برای شهر سوم y که همسایه مشترک x1 و x2 ( مجاوره این ۲تا) است مقداری پیدا میشه که بدی! خب با این شرایط اولیه که گفته شده برای D فقط سبز میمونه و برای E و B هم سبز باقی مونده اگه برای B یا E سبز انتخاب کنی دیگه نمیشه به D رو هیچ رنگی کرد! پس سازگاری مسیر conflict رو تشخیص میده

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

۰
ارسال:
  

ali.majed.ha پاسخ داده:

RE: مسئله ی ارضای محدودیت - سراسری ۸۹

مرسی دوستان
خیلی لطف کردید، موفق و پیروز باشید
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: مسئله ی ارضای محدودیت - سراسری ۸۹

سلام؛ پاسخ دوستان کاملا درسته؛
شما کافیه رنگ بکنید ؛ بعد بر طبق همسایگی ترتیب حذف با همسایه ها رو در نظر بگیرید؛ همیشه هم بدترین حالت از بین انتخاب ها رو در نظر بگیرید
یعنی اگه مسیری دارید و کمانی؛ شما مسیری که بدترین حالت انتخاب هاست رو در نظر بگیرید
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کمک به حل مسئله Moha33 ۰ ۱,۱۱۸ ۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ
آخرین ارسال: Moha33
Shocked کامپیوتر یا هنر، مسئله این است arian_61 ۲ ۴,۲۰۴ ۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ
آخرین ارسال: packationmachinery
  مسئله n_وزیر Sanazzz ۲ ۲,۸۷۹ ۱۱ بهمن ۱۳۹۷ ۰۳:۰۳ ب.ظ
آخرین ارسال: Sanazzz
  فروش کتاب ۳۰۰۰ مسئله حل شده شبکه فقط ۱۵۰۰۰ تومن کاملا نو Maral93 ۰ ۱,۵۷۱ ۲۵ مهر ۱۳۹۶ ۱۰:۴۰ ب.ظ
آخرین ارسال: Maral93
  آزاد یا غیرانتفاعی یا پردیس؟ مسئله این است! setayesh20 ۰ ۱,۹۷۳ ۱۳ شهریور ۱۳۹۶ ۱۰:۵۷ ق.ظ
آخرین ارسال: setayesh20
  مسئله Betweenness درس شبکه های اجتماعی fo-eng ۱ ۲,۷۴۷ ۰۵ شهریور ۱۳۹۶ ۰۸:۰۷ ق.ظ
آخرین ارسال: M.Amin.M
  ۱۸۰ معماری، ۷۷۹ هوش، ۵۸۹ نرم افزار، ۸۹۳ الگوریتم uzarcf ۲ ۳,۴۵۲ ۲۰ خرداد ۱۳۹۶ ۱۱:۰۵ ق.ظ
آخرین ارسال: f.amirdadi
  مسئله کشیشان و آدمخواران zahramousavi ۱ ۱,۸۷۸ ۰۴ اسفند ۱۳۹۵ ۱۲:۰۲ ب.ظ
آخرین ارسال: zahramousavi
  سوال اول ۶۰۰ مسئله ! M a h d i ۳ ۲,۷۸۵ ۲۵ بهمن ۱۳۹۵ ۰۴:۵۹ ب.ظ
آخرین ارسال: Behnam‌
  نظرتون در مورد کتاب ۶۰۰ مسئله از داده ساختارها و الگوریتم ها - دکتر قدسی ؟ tarane.68 ۲۶ ۳۰,۶۹۷ ۲۵ بهمن ۱۳۹۵ ۱۲:۱۹ ب.ظ
آخرین ارسال: taha_h

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close