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