(۲۴ فروردین ۱۳۹۵ ۰۱:۴۰ ب.ظ)shirin0101 نوشته شده توسط:  سلام
تست ارضای محدودیت سال ۸۹ گروه هوش....که نقشه کشیده و گزینه هاش:
۱)forward checking
۲)path consistency
۳)node consistency
۴(تناقض کشف نمیشه
این سوال کدوم درست ؟ سنجش کدوم گفته جواب؟ راهیان و پارسه هرکدوم یکی گفتن
ببخشید نمیتونم عکس بندازم
مرسی

سلام سنجش گزینه ۲ رو اعلام کرده

سلام
سنجش درست اعلام کرده (گزینه دو)، اجازه بدید ابتدا گراف محدودیت رو رسم کنیم.


الزامات اولیه مسئله:
- A قرمز است.
- C آبی است.
- M قرمز است.

خب، ما الزامات اولیه رو در ابتدا اعمال می‌کنیم، پس طبیعتا B و E به علت مجاورت با A نمی‌تونن قرمز باشن و باید سبز یا آبی باشن و D هم نمی‌تونه به دلیل مجاورت با C و M آبی و قرمز باشه و فقط باید سبز باشه. پس ما نهایتا سه متغیر مقدار نگرفته داریم: D که صرفا می‌تونه سبز باشه و B و E که یا باید آبی و یا سبز باشن. خب اگه خودمون بخوایم بدون الزامات اولیه مسئله این گراف رو رنگ کنیم حتما می‌تونیم انجامش بدیم اما با این الزامات یقینا شکست می‌خوریم.

ما هدفمون بررسی نقص قبل از شکست هست و برای این کار باید از متدهای انتشار محدودیت استفاده کنیم. طبق تعریف چون هر کدوم از گره‌های ما دارای حداقل یک مقدار مجاز هستن و دامنه متغیرهاشون خالی نیست و محدودیت یکتایی هم نداریم پس گزینه‌های ۱ و ۳ یعنی به ترتیب Forward و Node Consistency قادر به کشف ناسازگاری نیستند.

برای بررسی سازگاری مسیری: اگه E سبز (آبی) شه، پس B حتما باید آبی (سبز) بشه و در این صورت دیگه رنگی برای D نداریم >> بروز تناقض، چرا که به ازاری هر دو ناحیه مجاور رنگ آمیزی معتبری برای دو تاشون وجود داره ولی برای سومی وجود نداره بنابراین گره‌های B و D و E (دو به دو مجاور) با هم ناسازگاری دارند. البته بین B و E سازگاری کمانی داریم چون به ازای هر مقدار X از دامنه B یک مقدار Y از دامنه E وجود داره که با هم متناقض نباشن، ولی بین این سه نداریم که متد Path Consistency قادر به پیش بینی وقوع این تناقض هست.

(۲۴ فروردین ۱۳۹۵ ۰۵:۱۳ ب.ظ)Black.Star نوشته شده توسط:  برای بررسی سازگاری مسیری: اگه E سبز (آبی) شه، پس B حتما باید آبی (سبز) بشه و در این صورت دیگه رنگی برای D نداریم >> بروز تناقض، چرا که به ازاری هر دو ناحیه مجاور رنگ آمیزی معتبری برای دو تاشون وجود داره ولی برای سومی وجود نداره بنابراین گره‌های B و D و E (دو به دو مجاور) با هم ناسازگاری دارند. البته بین B و E سازگاری کمانی داریم چون به ازای هر مقدار X از دامنه B یک مقدار Y از دامنه E وجود داره که با هم متناقض نباشن، ولی بین این سه نداریم که متد Path Consistency قادر به پیش بینی وقوع این تناقض هست.

پس این گفته ی راهیان درباره ی اینکه توی path consistency مقادیر غیرمجاز از دامنه ی متغیرهای باقیمانده حذف نمیشن، درست نیست؟

(۲۴ فروردین ۱۳۹۵ ۰۶:۰۴ ب.ظ)Nesyan نوشته شده توسط:  

(24 فروردین ۱۳۹۵ ۰۵:۱۳ ب.ظ)Black.Star نوشته شده توسط:  برای بررسی سازگاری مسیری: اگه E سبز (آبی) شه، پس B حتما باید آبی (سبز) بشه و در این صورت دیگه رنگی برای D نداریم >> بروز تناقض، چرا که به ازاری هر دو ناحیه مجاور رنگ آمیزی معتبری برای دو تاشون وجود داره ولی برای سومی وجود نداره بنابراین گره‌های B و D و E (دو به دو مجاور) با هم ناسازگاری دارند. البته بین B و E سازگاری کمانی داریم چون به ازای هر مقدار X از دامنه B یک مقدار Y از دامنه E وجود داره که با هم متناقض نباشن، ولی بین این سه نداریم که متد Path Consistency قادر به پیش بینی وقوع این تناقض هست.

پس این گفته ی راهیان درباره ی اینکه توی path consistency مقادیر غیرمجاز ار دامنه ی متغیرهای باقیمانده حذف نمیشن، درست نیست؟

مبنای استدلالش مشخص نیست.

مرسی از دوستان که ج دادن بهم
اا پس ۲ میشه؟ خوبه ب خودم امیدوار شدم منم ۲ حل کرده بودم
مرسیییی

---

(۲۴ فروردین ۱۳۹۵ ۰۵:۱۳ ب.ظ)Black.Star نوشته شده توسط:  سلام
سنجش درست اعلام کرده (گزینه دو)، اجازه بدید ابتدا گراف محدودیت رو رسم کنیم.

الزامات اولیه مسئله:
- A قرمز است.
- C آبی است.
- M قرمز است.

خب، ما الزامات اولیه رو در ابتدا اعمال می‌کنیم، پس طبیعتا B و E به علت مجاورت با A نمی‌تونن قرمز باشن و باید سبز یا آبی باشن و D هم نمی‌تونه به دلیل مجاورت با C و M آبی و قرمز باشه و فقط باید سبز باشه. پس ما نهایتا سه متغیر مقدار نگرفته داریم: D که صرفا می‌تونه سبز باشه و B و E که یا باید آبی و یا سبز باشن. خب اگه خودمون بخوایم بدون الزامات اولیه مسئله این گراف رو رنگ کنیم حتما می‌تونیم انجامش بدیم اما با این الزامات یقینا شکست می‌خوریم.

ما هدفمون بررسی نقص قبل از شکست هست و برای این کار باید از متدهای انتشار محدودیت استفاده کنیم. طبق تعریف چون هر کدوم از گره‌های ما دارای حداقل یک مقدار مجاز هستن و دامنه متغیرهاشون خالی نیست و محدودیت یکتایی هم نداریم پس گزینه‌های ۱ و ۳ یعنی به ترتیب Forward و Node Consistency قادر به کشف ناسازگاری نیستند.

برای بررسی سازگاری مسیری: اگه E سبز (آبی) شه، پس B حتما باید آبی (سبز) بشه و در این صورت دیگه رنگی برای D نداریم >> بروز تناقض، چرا که به ازاری هر دو ناحیه مجاور رنگ آمیزی معتبری برای دو تاشون وجود داره ولی برای سومی وجود نداره بنابراین گره‌های B و D و E (دو به دو مجاور) با هم ناسازگاری دارند. البته بین B و E سازگاری کمانی داریم چون به ازای هر مقدار X از دامنه B یک مقدار Y از دامنه E وجود داره که با هم متناقض نباشن، ولی بین این سه نداریم که متد Path Consistency قادر به پیش بینی وقوع این تناقض هست.

مرسی...جامع بود..حله