|
'''الگوریتم تپه نوردی''' (Hill climbing) الگوریتمی است که برای یافتن بهترین پاسخ یک مسئله یا برای پیدا کردن پاسخی از مسئله که به اندازه یاندازهٔ کافی مناسب و بهینه باشد، استفاده می شود.
در این جا بیش تر مسئله هایی مورد بحث قرار می گیرند که چندین پاسخ با ارزش برابر دارند و هدف ما یافتن یکی از آن هاست.
برای بررسی الگوریتم تپه نوردی مسئله یمسئلهٔ زیر را بررسی می کنیم:
- تابع f به هر یک از اعضای مجموعه یمجموعهٔ متناهی S یک عدد حقیقی نسبت می دهد. هدف ما یافتن عضوی از S است که بیش ترین (یا کم ترین) مقدار به آن نسبت داده شده است.
همان گونه که گفته شد در این جا فرض بر این است که مقدار تابع f برای چندین عضو مختلف S بیشینه است و هدف ما یافتن تنها یکی از آن هاست. (در غیر این صورت معمولاً الگوریتم تپه نوردی، الگوریتم کار آمدی نیست.)
'''الگوریتم''' :
ابتدا یکی از اعضای مجموعه یمجموعهٔ S را (به صورت تصادفی) انتخاب می کنیم و آن را A می نامیم. سپس در میان اعضایی از S که به A نزدیکند به دنبال پاسخ مناسب تری برای مسئله می گردیم. به بیانی دیگر نلاش می کنیم در میان اعضایی که به A نزدیکند عضوی بیابیم که مقدار تابع f برای آن بیش تر از <math>f ( A )</math> باشد. سپس این روند را ادامه می دهیم تا به یک بیشینه یبیشینهٔ نسبی برای f دست یابیم.
بدیهی است که بیشینه یبیشینهٔ نسبی به دست آمده لزوماً پاسخ خواسته شده نیست. ولی اگر الگوریتم گفته شده چندین بار تکرار شود می توان به یافتن پاسخی مطلوب امیدوار بود. (در هر بار اجرای الگوریتم نخستین عضو به صورت تصادفی انتخاب می شود.)
== چند مثال ==
=== [[مسئله فروشنده دوره‌گرد|فروشنده یفروشندهٔ دوره گرد]] : ===
یک گراف ساده همبند را که یال های آن وزن دار است، در نظر بگیرید. هدف یافتن مسیری همیلتونی است که در آن مجموع وزن یال ها کمینه (یا به اندازه یاندازهٔ کافی کم) باشد. (مسیر هامیلتونی مسیری است که شامل همه یهمهٔ راس های گراف باشد.)
برای یافتن چنین مسیری می توان ابتدا یک مسیر هامیلتونی تصادفی انتخاب نمود و سسپس در هر گام با ایجاد تغییری اندک در مسیر، مجموع وزن یال های آن مسیر را بهینه نمود.
=== [[مسئله یمسئلهٔ n وزیر]] : ===
می خواهیم در یک صفحه یصفحهٔ n * n شطرنج، n وزیر شطرنج را به گونه ای قرار دهیم که هیچ دو وزیری یکدیگر را تهدید نکنند. (دو وزیر شطرنج در صورتی یکدیگر را تهدید می کنند که در یک سطر یا یک ستون یا یک قطر باشند.)
برای یافتن چیدمانی از n وزیر که در آن هیچ دو وزیری یکدیگر را تهدید نمی کنند ابتدا n وزیر را به صورتی تصادفی روی یک صفجه یصفجهٔ شطرنج n * n قرار می دهیم. (بهتر است این چیدمان به گونه ای باشد که هیچ دو مهره ای هم سطر یا هم ستون نباشند.) سپس در هر گام با ایجاد تغییراتی اندک در چیدمان مهره ها نلاش می کنیم تعداد زوج مهره هایی که یکدیگر را تهدید می کنند کاهش دهیم.
== الگوریتم های مشابه ==
در بسیاری از موارد یافت بیشینه یبیشینهٔ نسبی یا کمینه یکمینهٔ نسبی با استفاده از الگوریتم تپه نوردی کارساز نیست. در این گونه موارد از الگوریتم های کارآمد تری چون simulated annealing استفاده می شود. در این الگوریتم ها، پیمایش روی اعضای S همواره در جهت افزایش مقدار تابع f نیست.
== منابع ==
| 