آیا این دو الگوریتم یکی هستند یا با هم فرق دارند؟ random walk و random restart hill climbing
من یه random walk میشناسم که یه فرآیند تصادفیه و هیچ ربطی به hill climbing نداره!
الگوریتم تپه نوردی با شروع مدد تصادفی از یک نقطه تصادفی شروع میکنه اگه به هدف نرسید باز از یک نقطه تصادفی دیگه شروع میکنه..تا به هدف برسه درسته؟ حالا فرقش با random walk چی هست؟من نمیدونم random walk چه جوری کار میکنه؟
گفتم که ربطی له تپه نوردی نداره.
random walk یه فرآنید تصادفیه. فرآیند تصادفی یه درس ارشد برای برق و هوشه.
توی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
، اون قسمتی که تیتر زده برای مشکلات الگوریتم جست و جوی تپه نوردی، من یه همچین جمله ای پیدا کردم :
A problem with hill climbing is that it will find only local maxima. Unless the heuristic is convex, it may not reach a global maximum. Other local search algorithms try to overcome this problem such as stochastic hill climbing, random walks and simulated annealing.
یعنی random walk به عنوان یک الگوریتم جست و جوی محلی، این مزیت رو داره که می تونه global maxima رو پیدا کنه ولی حتی random restart hill climbing این قابلیت رو نداره و باز هم طبق گفته ی ویکی پدیا، فقط مصرف CPU رو بهبود می بخشهالبته اگر اشتباهی تو این جمله هام هست خوشحال میشم آقای blackhalo تصحیح کنند
(۰۳ بهمن ۱۳۹۱ ۰۷:۱۵ ب.ظ)avril22 نوشته شده توسط: من نمیدونم random walk چه جوری کار میکنه؟
یه نقطه رو به عنوان جواب فعلی در نظر میگیره و در یک لوپ هربار یکی از نقاط همسایه فعلی رو به تصادف انتخاب و بررسی میکنه؛ انتخاب همسایه نقطه فعلی کاملا تصادفیه و هیچ کاری به بهتر یا بدتر بودن از نقطه فعلی نداره؛ تنها کاری که میکنه بهترین جوابی که بهش رسیده رو سیو میکنه؛ (الگوریتم کامله اما کارآمد نیست)؛
(۰۴ بهمن ۱۳۹۱ ۱۲:۳۱ ق.ظ)Ghiasoddin نوشته شده توسط:(03 بهمن ۱۳۹۱ ۰۷:۱۵ ب.ظ)avril22 نوشته شده توسط: من نمیدونم random walk چه جوری کار میکنه؟
یه نقطه رو به عنوان جواب فعلی در نظر میگیره و در یک لوپ هربار یکی از نقاط همسایه فعلی رو به تصادف انتخاب و بررسی میکنه؛ انتخاب همسایه نقطه فعلی کاملا تصادفیه و هیچ کاری به بهتر یا بدتر بودن از نقطه فعلی نداره؛ تنها کاری که میکنه بهترین جوابی که بهش رسیده رو سیو میکنه؛ (الگوریتم کامله اما کارآمد نیست)؛
ممنونم از جواب هاتون متوجه شدم..
فقط اینکه RRHC رو هم میشه کامل بگید چه جوری کار میکنه؟از یه نقطه تصادفی شروع میکنه بعد بین همسایه هاش یکی رو تصادفی انتخاب میکنه یا بهترین همسایه رو انتخاب می کنه؟؟و اینکه توی کتاب گفته این الگوریتم با احتمال نزدیک به ۱ کامله اما تست کنکور پارسال گفته تپه نوردی حتما در بهینه ی محلی گیر میکند..مگه rrhc یک نوع از تپه نوردی ها نیست؟ یعنی تست حالت کلی رو در نظر گرفته؟
(۰۳ بهمن ۱۳۹۱ ۰۷:۱۵ ب.ظ)avril22 نوشته شده توسط: فقط اینکه RRHC رو هم میشه کامل بگید چه جوری کار میکنه؟از یه نقطه تصادفی شروع میکنه بعد بین همسایه هاش یکی رو تصادفی انتخاب میکنه یا بهترین همسایه رو انتخاب می کنه؟؟و اینکه توی کتاب گفته این الگوریتم با احتمال نزدیک به ۱ کامله اما تست کنکور پارسال گفته تپه نوردی حتما در بهینه ی محلی گیر میکند..مگه rrhc یک نوع از تپه نوردی ها نیست؟ یعنی تست حالت کلی رو در نظر گرفته؟یه همچین چیزیه:
repeat
startNode=randomSelection();
solution=HC(startNode);//hill climbing
until solution is acceptable
هسته الگوریتم همون تپه نوردیه؛ فقط به جای یکبار اجرای تپه نوردی، تا جائیکه یه جواب خوب پیدا بشه تکرار میشه که چالش اصلی سر تعیین مناسب همین تعداد اجراهای الگوریتمه؛ یعنی برای هر مسئله ای از قبل نمیدونیم چندبار باید تپه نوردی برای رسیدن به یه جواب خوب اجرا بشه؛ و چون تعداد اجراهای کافی رو نمیدونیم نمیشه گفت الگوریتم ۱۰۰ درصد کامله؛ با این حال میشه به یه تقریب مناسب برای تعیین دفعات اجرا رسید؛ ایدش هم اینه که اگه بدونیم احتمال موفقیت تپه نوردی برای یک مسئله برابر p هست، میتونیم تعداد اجراها رو ۱ روی p در نظر بگیریم؛ مثلا p باشه ۰/۰۱ تعداد اجراها میتونه ۱۰۰ بار باشه؛ منتها از اونجائیکه خود این مقدار p احتمالیه و قطعی نیست، باز نمیشه گفت الگوریتم ۱۰۰ درصد کامله؛ بهمین دلیل با احتیاط میگن با احتمال نزدیک به ۱ کامله؛
startNode=randomSelection();
solution=HC(startNode);//hill climbing
until solution is acceptable
خیلی ممنون از جوابتون
