Tepe Tırmanma Algoritması Nedir?

Tepe tırmanma algoritması (hill climbing), bir çözümü küçük değişikliklerle adım adım iyileştiren yerel arama yöntemidir. Adı şu benzetmeden gelir: Sisli bir dağda zirveye çıkmak isteyen biri, etrafını göremediği için her adımda yalnızca en dik yokuş yukarı yönü seçer ve artık yukarı giden bir yön kalmadığında durur.

Tepe tırmanma algoritması nedir?

Algoritma bir başlangıç çözümüyle başlar ve bu çözümün "komşularını", yani küçük değişikliklerle elde edilen alternatifleri inceler. Daha iyi bir komşu varsa ona geçer. Bu döngü, hiçbir komşu mevcut çözümden daha iyi olmayana kadar sürer. Bellek ihtiyacı çok düşüktür, çünkü yalnızca mevcut çözümü saklar.

Nasıl çalışır?

1. Bir başlangıç çözümü seç ve kalitesini ölç.
2. Komşu çözümleri üret ve değerlendir.
3. En iyi komşu mevcut çözümden iyiyse ona geç; değilse dur.

Varsayımsal bir örnek: 8 vezir bulmacasında vezirlerin birbirini tehdit etme sayısını azaltmak için her adımda bir veziri, çakışmayı en çok azaltan kareye taşımak bir tepe tırmanma uygulamasıdır.

Zayıf yönleri ve çözümleri

• Yerel tepe: Algoritma, en yüksek zirve olmayan küçük bir tepede takılabilir.
• Düzlük: Komşuların hepsi aynı değerdeyse hangi yöne gideceğini bilemez.
• Sırt: Dar sırtlarda ilerlemek zorlaşır.

Bu sorunları hafifletmek için algoritma farklı başlangıç noktalarından tekrar tekrar çalıştırılabilir (rastgele yeniden başlatma) ya da kötü hamlelere kontrollü izin veren benzetimli tavlama kullanılabilir. Tepe tırmanma, gradyan inişi ile de akrabadır: biri yukarı, diğeri hatayı azaltmak için aşağı doğru ilerler.