Sığ öncelikli arama

Sığ öncelikli arama
Düğümlerin ziyaret etme sıraları
Sınıf	Arama algoritması
Zaman karmaşıklığı	$O(\|V\|+\|E\|)$
Alan karmaşıklığı	$O(\|V\|)$

Bilgisayar biliminde, sığ öncelikli arama^[1] ya da enine arama,^[2] 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.^[1]

Sığ öncelikli arama 1945'te Michael Burke ve Konrad Zuse tarafından çizgelerde bağlı bileşenleri tespit etmek için geliştirilmiştir. Ancak, bu algoritmanın sunulduğu doktora tezi kabul edilmemiştir ve 1972 yılında yayınlanmıştır.^[3] 1959'da E. F. Moore tarafından, bir labirentteki en kısa yolu bulmak için,^[4]^[5] 1961 yılında ondan bağımsız bir şekilde C. Y. Lee tarafından devrelerde bağlantıların belirlenmesi amacıyla tekrar icat edilmiştir.^[6]^[7]

Sözde kod

Canlandırmalı sığ öncelikli arama örneği.

Girdi olarak başlagıç düğümünü (ilk_düğüm) ve hedeflenen düğümü (son_düğüm) alan ve çıktı olarak bu ikisi arasındaki en kısa yolu bulmak için gerekli olan bilgiyi (yol_listesi) döndüren sözde kod aşağıdaki gibidir. Daha sonra yol_listesi kullanılarak, son_düğüm'den geriye doğru her düğümün öncülü takip edilerek tam yol bulunabilir.

fonksiyon sığ_öncelikli_arama (ilk_düğüm, son_düğüm):
  
  # listeleri yarat
  açık_liste := yeni kuyruk
  kapalı_liste := yeni kuyruk
  yol_listesi := yeni sözlük
  
  # aramayı başlat
  ilk_düğüm'ü açık_liste'ye ekle
  
  # ana döngü
  döngü (açık_liste boş değilse):
    
    # açılacak düğümü kuyruktan al
    açılan_düğüm := açık_liste'den çıkar
    
    # hedefi kontrol et
    eğer (açılan_düğüm = son_düğüm):
      
      döndür yol_listesi
      
    eğer_sonu
    
    komşu_listesi := açılan_düğüm'ün komşuları
    
    # komşu döngüsü
    döngü (komşu_listesi boş değilse):
    
      mevcut_komşu := komşu_listesi'nden çıkar
      
      eğer (mevcut_komşu kapalı_liste'de ve açık_liste'de yoksa):
        
        mevcut_komşu'yu açık_liste'ye ekle
        
        (mevcut_komşu: açılan_düğüm) ikilisini yol_listesi'ne ekle
              
      eğer_sonu
      
      açılan_düğüm'ü kapalı_liste'ye ekle
    
    döngü_sonu # komşu döngüsü
    
  döngü_sonu # ana döngü
  
  döndür boş liste
  
fonksiyon_sonu

Ayrıca bakınız

Kaynakça

^ ^a ^b Şeker, Şadi Evren. "Şekillerde Sığ Öncelikli Arama". bilgisayarkavramlari.sadievrenseker.com. Şadi Evren Şeker. 14 Haziran 2017 tarihinde kaynağından arşivlendi. Erişim tarihi: 19 Şubat 2018.
^ Morin, Pat; Tunç, Ayşegül (Ocak 2016). Açık Veri Yapıları (Java ile). İstanbul: ekitapprojesi.com. s. 416. Erişim tarihi: 18 Şubat 2018.
^ Zuse, Konrad (1972). Der Plankalkül (Tez) (Almanca). Konrad Zuse Internet Archive. ss. 96-105. 6 Mayıs 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 19 Şubat 2018.
^ Moore, Edward F. (1959). Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. ss. 285-292.
^ Skiena, Steven (2008). The Algorithm Design Manual. Springer. s. 480. doi:10.1007/978-1-84800-070-4_4.
^ Leiserson, Charles E.; Schardl, Tao B. (2010). A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) (PDF). ACM Symp. on Parallelism in Algorithms and Architectures. 15 Aralık 2017 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 19 Şubat 2018.
^ Lee, C. Y. (1961). "An Algorithm for Path Connections and Its Applications". IRE Transactions on Electronic Computers.

İlgili Araştırma Makaleleri

İngilizce Router Information Protocol, yani Yönlendirme Bilgi Protokolü anlamına gelen RIP, bir TCP/IP ağındaki router'ların birbirini otomatik olarak tanımasında kullanılan bir iç yönlendirme protokoldür. Aynı zamanda uzaklık vektör algoritmasına dayanır ve IGP 'nın bir uygulamasıdır. Yönlendirme kararları, düğümler arasındaki sıçramaların sayısına dayanır. Yönlendiriciden geçmek bir sıçrama sayılır. İlk olarak XNS protokol kümesinde kullanılmış olup daha sonra IP ağ uygulamalarında kullanılmıştır.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

Gerçek Zamanlı İşletim Sistemi (RTOS), verileri ve önemli zaman kısıtlamalı olayları işleyen gerçek zamanlı uygulamalar için işletim sistemi'dir.

Konrad Ernst Otto Zuse, Alman inşaat mühendisi, mucit ve iş insanıdır. 1936 yılında Z1 adlı programlanabilir bilgisayarı geliştirmiştir.

İkili arama ağacı, verileri organize etmek için kullanılan bir çeşit ikili ağaçtır. İkili ağaçtan temel farkı, verilerin sıralanmış bir şekilde tutulmasıdır, bu sayede ikili arama algoritmasının kullanılmasına imkân verir.

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.

<span class="mw-page-title-main">Bataklık</span> odunsu bitki türlerinden ziyade otsu bitki türlerinin yaygın olarak yaşadığı sulak alan

Bataklık, yer altı sularının çok yüksek olduğu, çoğu zaman yüzeye çıktığı, toprağı aşırı ıslak olduğu, su göllenmelerinin görüldüğü yerlerdir. Bataklıklar çevrelerine göre alçakta, çanak-çukur şeklinde yerlerdir. Donmuş sahaların yüzeyinde yazın çözülmeye bağlı bataklık oluşabilir. Kurak alanlarda tuzlu bataklıklar oluşabilir.

Düğüm; ip vb. doğrusal cisimleri, birbirine tutturmak için kullanılan yöntemdir. Düğüm, bir veya birden fazla ipten, dokumalardan, sicim ve kayışlardan, zincirlerden, hatta birbirine bağlanmış hatlardan meydana gelen dokumalardan meydana gelebilir. Düğümler, bağlama yöntemleri, kullanımları, hikâyeleri, kökenleri ve düğüm teorisinin matematiksel gözlemleri nedeniyle ilginç nesneler olarak tanınırlar.

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

Köşe Örtme, bir çizge (graf) içerisindeki tüm kenarların en az sayıda seçilebilecek düğüm ile kapsanabilir olup olmadığının bulunması problemidir. Bu problemin NP sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin NP-Tam sınıfında olup olmadığının ispatıdır.

Distance-vector Routing Protocol paket-anahtarlamalı ağlarla ilgili bilgisayar Iletişim(computer communication) kuramında yer alan iki ana sınıftan biridir. Diğeriyse bağlantı-durum (link-state) protokolüdür. Distance-vector yönlendirme protokolü yolların hesaplanmasında Bellman-Ford algoritmasını kullanır.

At nalı yörünge, kendisine göre çok daha büyük bir cisimle eş-yörünge hareketi yapan cismin yörüngesine verilen addır. Küçük cismin yörünge periyodu neredeyse büyük cismin yörünge periyoduna eşittir ve büyük cisimden bakıldığında dönen referans çerçevesinde izlediği yol at nalına benzer.

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

Paket anahtarlama uygun boyuttaki bloklar içerisinde tüm verilerin aktarıldığı bir dijital ağ iletişimi yöntemidir. Aktarılan verinin küçük parçalara bölünmüş hali paket olarak isimlendirilir. Paketlerde kullanıcı verisi, yönlendirme, hata düzeltme ve akış kontrolü işlemleri için alanlar mevcuttur.

Hisse ispatı, (PoS) bir kripto para blok zinciri ağının dağıtık fikir birliğine ulaşmayı amaçladığı bir algoritma türüdür. PoS tabanlı kripto para birimlerinde, bir sonraki bloğu oluşturan, rassal seçim ve zenginliğin ya da yaşın çeşitli kombinasyonları yoluyla seçilir. Aksine, bitcoin gibi emek ispatınadayanan kripto paraların algoritması, madencilik kullanır. Yani, kayıtları (transaction) doğrulamak ve yeni bloklar oluşturmak için yoğun hesaplamalı bulmacaların çözümünü gerektirir.

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">Derin öncelikli arama</span>

Bilgisayar biliminde, derin öncelikli arama, ağaç ya da çizge veri yapılarında arama yapmak için kullanılan bir algoritmadır. Algoritma aramaya başladığı düğümden ulaşabileceği en derin düğüme kadar gider, gidecek daha derin bir düğüm kalmadığında geri sarar ve derin düğümlere öncelik vererek gezmeye devam eder.

Bilgisayar biliminde, Floyd-Warshall algoritması kenar ağırlıkları artı ya da eksi değere sahip çizgelerde en kısa yolları bulma algoritmasıdır. Algoritma uygulandığında her düğüm çifti için en kısa yol uzunluklarını bulur. Özgün algoritma yol detaylarını döndürmese de, küçük değişikliklerle yolların oluşturulması da mümkündür. Çizge kuramında ve diğer matematik uygulamalarında kullanılır.

Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Ç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.

Otomatik kümeleme algoritmaları, veri kümeleri hakkında önceden bilgi sahibi olmadan kümeleme yapabilen algoritmalardır. Diğer küme analizi tekniklerinin aksine, otomatik kümeleme algoritmaları, gürültü ve aykırı noktaların varlığında bile en iyi küme sayısını belirleyebilir.

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.