Tepe Tırmanma Algoritması
 | Bu madde, öksüz maddedir; zira herhangi bir maddeden bu maddeye verilmiş bir bağlantı yoktur. (Eylül 2022) |
Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır.[1] Çok sayıda verinin girilmesi ve iyi bir sezgisel fonksiyon verildiğinde, probleme yeterince iyi bir çözüm bulmaya çalışmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. İki boyutlu bir grafikte en düşük noktaları arama esnasında yapmış olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıştır.
Yani bir sistemi veya programı daha verimli hale getirilmesi isteniyorsa, sistemin sonuçlarına göre arama yapılarak iyileştirilmesi hedeflenebilmektedir. Tepe tırmanma algoritması da dahil olmak üzere çeşitli arama algoritmalarının devreye girdiği yer burasıdır. Örneğin literatürde sıklıkla kullanılan seyyar satıcı problemi bu problemlerden biridir.
Özellikleri[değiştir | kaynağı değiştir]
Tepe Tırmanma Algoritmasının 3 ana özelliği şunlardır:
- Üret ve test et varyantı
Tepe tırmanma algoritması Üret (Generate) ve Test Et yönteminin bir çeşididir. Üret ve Test Et yöntemi, arama alanında hangi yöne hareket edileceğine karar vermeye yardımcı olan geri bildirim üretmektedir.[2]
- Açgözlü Yaklaşım (Greedy Approach)*
Tepe tırmanma algoritmasının, arama esnasında maliyeti optimize eden yönde bir özelliği vardır. Başka bir deyişle en kısa mesafeyi bularak o yönde ilerlemektedir.
- Geriye Dönük İşlem*
Tepe tırmanma algoritması kullandığı bir yöntemi, o bölgeyi geçtikten sonra unutur ve hatırlayamaz. Bu da Tepe tırmanma algoritmasının arama alanında geriye dönük işlem yapamamasına neden olmaktadır.
Çeşitleri[değiştir | kaynağı değiştir]
Basit Tepe Tırmanma Algoritması[değiştir | kaynağı değiştir]
Basit tepe tırmanma, tepe tırmanma algoritması uygulamanın en basit yoludur. Bir seferde yalnızca komşu düğüm durumunu değerlendirir ve cari maliyeti optimize etmektedir. Optimizasyon sonucunda komşu düğümler arasından bir tanesini seçmektedir. Ardından bir varis durumu olup olmadığını kontrol eder ve mevcut durumdan daha iyi bulursa, o zaman süreç tekrar başlar ve en iyisini bulana kadar devam etmektedir. Sıralama şu şekildedir;
- Adım 1: Başlangıç durumunu değerlendirin, hedef durumsa, başa dönün ve durdurun.
- Adım 2: Bir çözüm bulunana veya uygulanacak yeni operatör kalmayana kadar bir döngü kurun.
- Adım 3: Mevcut duruma bir operatör seçin ve uygulayın.
- Adım 4: Yeni durumu kontrol edin:
- Hedef durumsa, başa dönün ve çıkın.
- Aksi takdirde mevcut durumdan daha iyiyse, yeni durumu mevcut durum olarak atayın.
- Mevcut durumdan daha iyi değilse, 2. adıma geri dönün.
- Adım 5: Çıkış.
- En Dik Tepe Tırmanma Algoritması
En dik Tepe Tırmanma algoritması, basit tepe tırmanma algoritmasının bir çeşididir. Bu algoritma, mevcut durumun tüm komşu düğümlerini incelemekte ve hedef duruma en yakın olan bir komşu düğümü seçmekte. Bu algoritma, birden çok komşuyu ararken daha fazla zaman tüketmektedir.
Stokastik Tepe Tırmanma Algoritması[değiştir | kaynağı değiştir]
Stokastik[3] Tepe Tırmanma Algoritması, hareket etmeden önce diğer türlerin aksine tüm komşu düğümleri incelememektedir. Daha ziyade, bu arama algoritması bir komşu düğümü rastgele seçmekte, onu mevcut durum olarak seçip seçmemeye veya başka bir durumu inceleyip incelememeye karar vermektedir.
Tepe Tırmanma Algoritmasına ait Akış Diyagramı[değiştir | kaynağı değiştir]
Algoritmaya ait akış diyagramı yan tarafta görüldüğü gibidir.
Seyyar Satıcı Probleminin Tepe Tırmanma Algoritması Kullanarak Çözülmesi[değiştir | kaynağı değiştir]
Optimizasyon problemleri denildiği zaman ilk akla gelen problemlerden birisi de seyyar satıcı problemidir. Gezgin Satıcı Problemi şu şekilde tanımlanabilmektedir.
Bir seyyar satıcı vardır ve mallarını n kadar şehirde satmak istiyor. Diğer bir taraftan, mantıklı bir şekilde, seyyar satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak ürünlerini satmak istemektedir. Bu problem, bir matematiksel problem olarak 1930'lu yıllarda formüle edilmiştir. Optimizasyon konusunda en derin inceleme konularından biridir.[4]
C# programlama dilini kullanarak çözülen bu problem aşağıdaki gibidir.
Seyyar Satıcı 4 adet şehre uğrayacaktır. Şehirler arası mesafeler şu şekildedir;
1-3: 15,
1-4: 20,
1-2: 10,
2-4: 25,
2-3: 35,
3-4:40,
Problem çok boyutlu olduğu için algoritmayı şu şekilde yazmak uygudur; Bir noktanın birden fazla komşusu varsa, o zaman tüm komşular kontrol edilecek ve daha sonra o komşuya gitmek için en iyisine ihtiyaç duyulacaktır.
Yandaki yeni kodda bir noktanın birden fazla komşusu olduğu varsayılmış ve tüm komşular dolaştırılarak en iyi komşu alınmış ve daha sonra daha iyi komşular bulunarak bu süreç devam ettirilmiştir. Sonunda, hiçbir komşu bulunan son komşudan daha iyi olmadığında, program sonlandırılmıştır.
Kaynakça[değiştir | kaynağı değiştir]
- ^ "Tepe Tırmanma Algoritması Nedir ?". 6 Eylül 2020 tarihinde kaynağından arşivlendi.
- ^ "Tepe Tırmanma Algoritmasının Özellikleri?". 26 Mayıs 2021 tarihinde kaynağından arşivlendi.
- ^ "Stokastik Nedir ?". 15 Aralık 2005 tarihinde kaynağından arşivlendi.
- ^ "Gezgin Satıcı Problemi". 14 Nisan 2020 tarihinde kaynağından arşivlendi.