کدامیک از روش های جستجو زیر برای استفاده در یک مسئله ارضای محدودیت مناسبتر است ؟
1- تپه نوردی
2- عرض نخست
3- عمیق سازی تکراری
4- عمق نخست
پوران جواب رو گزینه 4 داده اما توی متن کتاب یه قسمتی درباره فواید الگوریتم های جستجو محلی مانند تپه نوردی با هیوریستیک مینیمم تناقض صجبت کرده و یه سری مزایاش رو به نسبت جستجوی عقب گرد گفته .
چرا اینجا 1 رو انتخاب نمی گنه ؟ ایا کسانی که کتاب دیگه دارن هم این تست رو 4 انتخاب کرده ؟
در کل ، حل مسایل ارضای محدودیت از نوع مسایل جستجو عمقی هستند.
(07 بهمن 1391 10:40 ب.ظ)ana_12345 نوشته شده توسط: [ -> ]کدامیک از روش های جستجو زیر برای استفاده در یک مسئله ارضای محدودیت مناسبتر است ؟
۱- تپه نوردی
۲- عرض نخست
۳- عمیق سازی تکراری
۴- عمق نخست
پوران جواب رو گزینه ۴ داده اما توی متن کتاب یه قسمتی درباره فواید الگوریتم های جستجو محلی مانند تپه نوردی با هیوریستیک مینیمم تناقض صجبت کرده و یه سری مزایاش رو به نسبت جستجوی عقب گرد گفته .
چرا اینجا ۱ رو انتخاب نمی گنه ؟ ایا کسانی که کتاب دیگه دارن هم این تست رو ۴ انتخاب کرده ؟
گزینه درست "4" هست. در کتاب سنجش هم همین رو انتخاب کرده و دلیلش هم اینه که در مسایل ارضای محدودیت زمانی برای مسئله جوابی پیدا میشه که به برگهای درخت جستجو رسیده باشیم (یعنی برای هر متغیر یک انتساب صورت گرفته باشه) که در این حالت بهترین نوع جستجو برای مسائل ارضای محدودیت جستجوی عمقی هستش که استفاده میشه.
جستجوی تپه نوردی ممکنه جواب رو پیدا نکنه و ممکنه جوابی که پیدا میکنه یک ماکزیمم محلی باشه نه ماکزیمم سراسری ولی ما توی ارضای محدودیت به دنبال ماکزیمم سراسری هستیم که الگوریتم قطعا بتونه اون رو پیدا کنه.
حتی اگر عمق مسئله توی تپه نوردی محدود باشه باز هم جواب بهینه تضمین شده نیست.توی تپه نوردی برای اینکه با احتمال نزدیک به 1 بتونیم به جواب بهینه برسیم باید شروعهای مجدد تصادفی داشته باشیم.
ولی توی عمق نخست ، اگر عمق جواب محدود باشه(یعنی جواب توی عمق بی نهایت نباشه)حتما جواب رو پیدا میکنه.نمونه اش رنگ آمیزی گراف هست.درضمن توی عمق نخست ، اگر از یک زیر درختی نتونیم به جواب برسیم دیگه اون رو ادامه نمیدیم و میریم سراغ شاخه های بعدی ، که این بهترین روش برای پیدا کردن جوابهای ارضای محدودیت هست
دوستان خیلی خیلی لطف کردین
ممنونم
