(۲۳ بهمن ۱۳۹۲ ۱۲:۲۲ ق.ظ)hosein_khoshdel نوشته شده توسط: معمولا ( یا همیشه؟) از جستجوی محلی برای مسائلی استفاده می شه که هدفشون پیدا کردن حالتی با شرایط مطلوبه.یعنی مسیر رسیدن به جواب مهم نیست.مهم خود جوابه. مثل مسائل n وزیر. حالا سوال من اینه که کامل و بهینه بودن تو جستجوی محلی به چه معنیه و این دو تا با هم چه فرقی دارن؟
کامل بودن یعنی اگر جوابی باشه آن را پیدا کند و در جستجوی محلی یعنی اگر ماکس مطلق را پیدا کند
بهینه بودن یعنی اگر چندین جواب باشد، جستجو کم هزینه ترین (یا ماکس ترین) یا بهترین جواب را پیدا کند
انواع تپه نوردی
۱/ تپه نوردی ساده یا تندترین شیب
۲/ تپه نوردی اولین انتخاب
۳/ تپه نوردی غیرقطعی
۴/ تپه نوردی با شروع مجدد
که سه تای اول، نه کامل هستند و نهایتا بهینه هم نیستند
ولی چهارمی با احتمال نزدیک به یک، هم کامل و هم بهینه است
جالب اینجاست که جستجوی محلی الگوریتمی برای مسائل بهینه سازی است ولی با اینکه سعی میکنه بهینه ترین جواب را بده ولی بازم ممکنه بهینه ترین جواب را نده (منظورم همون سه تای اولی بود)
Saman، در تاریخ ۲۲ مهر ۱۳۹۵ ۰۱:۴۸ ب.ظ برای این مطلب یک پانوشت گذاشته است:
ضمن سپاس از پاسخ درست ایشان.
مراجعه به لینک زیر نیز توصیه می شود.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
