سلام دوستان
از روی این مثالی که توی لینک زیر اومده کسی میتونه توضیح بده که چجوری با تپه نوردی حل شده و اصولا فرق تپه نوردی و الگوریتم حریصانه چی هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۹ آذر ۱۳۹۲ ۱۲:۱۷ ق.ظ)sepid نوشته شده توسط: سلام دوستان
از روی این مثالی که توی لینک زیر اومده کسی میتونه توضیح بده که چجوری با تپه نوردی حل شده و اصولا فرق تپه نوردی و الگوریتم حریصانه چی هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
در این مثال
مسیر در حریصانه اینه
s-->A-->I--->J--->L-->K--->L--->K--->M--->G
در تپه نوردی این
s-->A-->I--->J--->L-->K--->M--->G
از S تا L فرآیند انتخاب مسیر در هر دو الگوریتم یکی هست در هر مرحله کمترین هیوریستیک انتخاب شده و اون گره باز میشه. حالا در تپه نوردی وقتی در گره L (هیوریستیک =۴) هستیم از بین همسایه هاش کمترین هیوریستیک مربوط به گره K (هیوریستیک =۶) هست. اونو باز میکنیم. چه اتفاقی می افته؟ مقدار هیوریستیک بیشتر شد، الگوریتم به حالت بدتری رفت. پس بر می گردیم سرجامون یعنی همون گره L و همسایه بعدی اش رو باز می کنیم (M) و بعد هم G و تمام.
و اما تفاوت این دو تا الگوریتم
یک تفاوت آشکارشون که توی همین مثال بالا مشخصه.
و دیگه اینکه تپه نوردی با یک حالت اولیه که به صورت تصادفی انتخاب میشه شروع میکنه و از اونجایی که ممکنه در بیشینه محلی گیر کنه، جوابی که به دست میاره قطعی نیست. اما حریصانه اگر داخل حلقه گیر نکنه و به جواب برسه. اون جواب قطعی هست چون در هر مرحله نزدیک ترین نود به هدف رو باز میکنه.