الگوریتم تپه نوردی

الگوریتم تپه‌نوردی (Hill climbing) الگوریتمی است که برای یافتن بهترین پاسخ یک مسئله یا برای پیدا کردن پاسخی از مسئله که به اندازهٔ کافی مناسب و بهینه باشد، استفاده می‌شود.

یک محیط جستجوی محدب.

تپه‌نوردی یک تکنیک بهینه‌سازی متعلق به خانواده الگوریتم‌های جستجوی محلی است؛ یک تکنیک تکرارشونده که با یک راه‌حل دلخواه شروع به کار کرده و سپس تلاش می‌کند تا با تغییر بر روی یک عنصر از راه حل، به پاسخ بهتری دست پیدا کند. اگر این تغییر منجر به ایجاد یک راه حل بهتر شود، تغییر دیگری بر روی این راه حل جدید انجام خواهد گرفت. این روال تا زمانی که بهبود بیشتری در راه حل میسر نباشد ادامه می‌یابد.

برای مثال، تپه‌نوردی می‌تواند در حل مسئله فروشنده دوره‌گرد مورد استفاده قرار گیرد. یافتن راه حل اولیه‌ای که تمام شهرها را ملاقات کرده اما در مقابل راه حل بهینه مسئله بسیار ضعیف باشد کار آسانی‌ست. الگوریتم با راه حلی مشابه، شروع به کار کرده و بر روی آن بهبودهای کوچکی همچون تعویض ترتیب ملاقات دو شهر ایجاد می‌کند. سرانجام، یک مسیر بسیار کوتاه‌تر از راه حل اولیه به دست خواهد آمد.

تپه‌نوردی برای یافتن بهینه محلی مناسب است اما تضمین نمی‌کند که بهترین راه حل ممکن (بهینه سراسری) از بین تمام راه‌حل‌های ممکن (فضای جستجو) پیدا شود. در مسائل محدب، تپه‌نوردی بهترین انتخاب است. مثال‌های از الگوریتم‌هایی که مسائل محدب را با تپه‌نوردی حل می‌کنند شامل الگوریتم سیمپلکس برای برنامه‌ریزی خطی، و جستجوی باینری است. اگر محیط جستجو محدب نباشد، این الگوریتم اغلب در یافتن ماکزیموم سراسری شکست خواهد خورد.

سادگی این تکنیک آن را در دسته الگوریتم‌های بهینه‌سازی بسیار محبوب کرده است. از تپه‌نوردی به شکل گسترده‌ای در هوش مصنوعی برای یافتن هدف از یک نود آغازگر استفاده می‌شود. تپه‌نوردی اغلب در شرایطی که زمان اجرای جستجو محدود است (همچون سیستم‌های بلادرنگ)، نتیجه بهتری از سایر الگوریتم‌های هم‌نوعش تولید می‌کند. تپه‌نوردی یک الگوریتم “همه زمانی” است: حتی اگر پیش از رسیدن به پایان نیز قطع شود یک جواب قابل قبول تحویل می‌دهد.

2070 بازدید