İçeriğe atla

Tepe Tırmanma Algoritması

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

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

Basit Tepe Tırmanma Algoritması

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ı

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ı

Tepe Tırmanma Algoritmasına ait Akış Diyagramı

Algoritmaya ait akış diyagramı yan tarafta görüldüğü gibidir.

Seyyar Satıcı Probleminin Tepe Tırmanma Algoritması Kullanarak Çözülmesi

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]

Gezgin Satıcı Probleminin Tepe Tırmanma Algoritması kullanılarak C # programlama dili ile çözülmesi

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.

Gezgin Satıcı Probleminin Tepe Tırmanış Algoritması kullanılarak C # programlama dili ile çözülmesi

Kaynakça

  1. ^ "Tepe Tırmanma Algoritması Nedir ?". 6 Eylül 2020 tarihinde kaynağından arşivlendi. 
  2. ^ "Tepe Tırmanma Algoritmasının Özellikleri?". 26 Mayıs 2021 tarihinde kaynağından arşivlendi. 
  3. ^ "Stokastik Nedir ?". 15 Aralık 2005 tarihinde kaynağından arşivlendi. 
  4. ^ "Gezgin Satıcı Problemi". 14 Nisan 2020 tarihinde kaynağından arşivlendi. 

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Çizge teorisi</span> nesneler arasındaki ikili ilişkileri modellemek için kullanılan matematiksel yapılar olan grafiklerin incelenmesi

Graf teorisi, çizge teorisi veya çizit teorisi, grafları inceleyen matematik dalıdır. Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf, çizge veya çizit, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan oluşur.

Seyyar satıcı problemi yöneylem araştırması ve teorik bilgisayar bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir.

Prim Algoritması ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaç problemine çözüm bulma algoritmalardan birisidir.

İngilizce Open Shortest Path First, yani "En kısa yola Öncelik" anlamına gelen OSPF, bir TCP/IP ağındaki router'ların birbirini otomatik olarak tanımasında kullanılan bir protokoldür. OSPF yönlendirme internette intra-AS yönlendirme için RIP gibi yaygınca kullanılan bir yöntemdir. OSPF temelde internet servis sağlayıcılarının (ISP) üst-tabakalarında kullanılır. OSPF kelimesindeki ilk O harfi yönlendirme protokolü şartlarının açık olduğunu gösterir. OSPF'nin en güncel versiyonu ikincisidir[RFC 2328].

<span class="mw-page-title-main">Benzetilmiş tavlama</span>

Benzetilmiş tavlama ya da benzetimli tavlama algoritması, eniyileme problemi için tasarlanmış olasılıksal yaklaşımlı bir algoritmadır. Diğer olasılıksal yaklaşımlar gibi en iyi çözümün en kısa zamanda üretimini hedefler. Bu sebeple, özellikle matematiksel modellerle çözülmesi maliyetli olan kombinasyonel eniyileme problemlerinde kullanılır. Benzetilmiş tavlama algoritması; elektronik devre tasarımı, görüntü işleme, yol bulma problemi, gezgin satıcı problemi, malzeme fizigi simulasyonu, kesme ve paketleme problemi, akış çizelgeleme ve iş çizelgeleme problemlerinin çözümlerinde başarılı sonuçlar vermiştir.

<span class="mw-page-title-main">Genetik algoritma</span>

Genetik algoritmalar, doğada gözlemlenen evrimsel mekanizmalara benzer mekanizmalar kullanarak çalışan eniyileştirme yöntemidir. Çok boyutlu uzayda belirli bir maliyet fonksiyonuna göre en iyileştirme amacıyla iterasyonlar yapan ve her iterasyonda en iyi sonucu üreten kromozomun hayatta kalması prensibine dayanan en iyi çözümü arama yöntemidir.

Matematikte matematiksel programlama, eniyileme ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tam sayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder. Örneğin bu problem şöyle olabilir:

Ağ modeli yöneylem araştırmasında belirlenmiş bir sıra problemin düğümler ve dal veya bağlantilardan oluşan bir şebeke halinde tanımlanıp modellemesi türü olup ve tanımlanan sebeke problemlerinin çözümlenmesi için ortaya çıkartılan özel şebeke problemi algoritmalardan oluşur. Bu türlü çalışmalarda önce problemin ögeleri ve amacı tarif edilir. Sonra problemin şekil olarak veya matris olarak dallar ile birbirlerine bağlı düğümler halinde yapılandırılıp tanımlanması gerekir. Örneğin problem bir şehre kurulacak su borusu şebekesinin, bütün şehre en ucuz maliyet ile nasıl kurulacağıdir. Bu problem bir mümkün olan bütün bağlantı parçalarını, maliyetleri ve kapasiteleri gösteren şebeke halinde ifade edilir. Bu problem ve yapılanan model bir minimum maliyet kapasiteli sebeke problemi olduğu için bu çeşit model problemi çözmek için geliştirilmiş olan özel algoritmalardan birini kullanarak çözülebilir.

<span class="mw-page-title-main">Bağımsız küme problemi</span>

Bağımsız küme bir çizgede birbirleriyle komşu olmayan düğümleri içeren kümedir. çizgede düğümler kümesi 'de arasında ayrıt olan iki düğüm bulunmuyorsa S bağımsızdır denir. Bağımsız küme problemi NP-Tam bir problemdir. Yani Polinomsal zaman'da problemi çözen bir algoritma bulunamamıştır.

<span class="mw-page-title-main">Sırt çantası problemi</span>

Sırt çantası problemi bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonunun doğrusal eşitlik ve/veya eşitsizlik kısıtlamalarını sağlayacak şekilde optimizasyon yapılmasıdır. Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinin ağırlıklı toplamlarından oluşmalıdır.

Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vaz geçerek çözüm zamanını azaltan algoritmalardır.

Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.

Arama algoritmaları, bilgisayar biliminde seçili özelliklere göre istenilen bilgileri bulan algoritmalardır. Listeler, metinler ve şekiller üzerinde çalışırlar.

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, loga(b) ifadesi, ax = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Bilgisayar bilimi, matematik, ekonomi ve biyoinformatikte dinamik programlama karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir. Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar. Dinamik programlama algoritmaları optimizasyon problemlerinin çözümünde yaygın olarak kullanılır.

<span class="mw-page-title-main">Sığ öncelikli arama</span>

Bilgisayar biliminde, sığ öncelikli arama ya da enine arama, bir çizgenin düğümlerini, başlangıç noktasına daha yakın olanlara öncelik vererek arayan bir algoritmadır. Algoritma ziyaret ettiği düğümlerin bütün komşularını bir kuyruğa ekler ve ziyaret edeceği düğümleri kuyruktaki sıraya göre seçer. Eğer arama yapılan çizge bir ağaç ise kuyruk kullanmaya gerek olmaz.

Merkle imzası, anahtarlama ağaçları ve sayısal imza şemalarını birleştiren bir veri doğrulama yapısıdır. Özet değeri tabanlı kriptografidir ve Merkle ağacı da denen özet değeri ağacını kullanmaktadır. Verileri Lampart imza algoritması gibi tek kullanımlık şekilde imzalar. Ralph Merkle tarafından 1970 sonu itibarıyla geliştirilmiştir ve RSA, Dijital İmza Algoritması gibi geleneksel dijital imzalara alternatif olmuştur.

<span class="mw-page-title-main">En kısa yol problemi</span>

Çizge kuramında, en kısa yol problemi, bir çizgedeki iki düğümü bağlayan ve ağırlıkları toplamı en az olan ayrıtlar dizisini bulma problemidir.

Ateşböceği algoritması, doğal olaylardan ilham alınarak tasarlanmış bir optimizasyon algoritmasıdır. Bu algoritma, ateşböceklerin ışık saçma ve karşılıklı etkileşimleri ile çiftleşme davranışlarına dayanır.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.