İçeriğe atla

Derin öncelikli arama

Derin öncelikli arama
Örnek bir aramada düğümlerin ziyaret edilme sıraları
SınıfArama algoritması
Zaman karmaşıklığı
Alan karmaşıklığı

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.

Derin öncelikli aramanın bir biçimi 19. yüzyılda Fransız matematikçi Charles Pierre Trémaux[1] tarafından labirentte yol bulma problemine bir çözüm olarak önerilmiştir.[2][3]

Ayrıca bakınız

Kaynakça

  1. ^ Charles Pierre Trémaux (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph
    in Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN 0980-6032)
  2. ^ Even, Shimon (2011). Graph Algorithms (2. bas.). Cambridge University Press. ss. 46-48. ISBN 978-0-521-73653-4. 23 Şubat 2017 tarihinde kaynağından arşivlendi. Erişim tarihi: 1 Ağustos 2018. .
  3. ^ Sedgewick, Robert (2002). Algorithms in C++: Graph Algorithms (3. bas.). Pearson Education. ISBN 978-0-201-36118-6. .

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Asal sayı</span> sadece iki pozitif tam sayı böleni olan doğal sayılardır

Bir asal sayı, yalnızca 1'den büyük olup kendisinden küçük iki doğal sayının çarpımı olarak ifade edilemeyen bir doğal sayıdır. 1'den büyük ve asal olmayan doğal sayılara bileşik sayı adı verilir. Örneğin, 5 bir asal sayıdır çünkü onu bir çarpım olarak ifade etmenin mümkün olan yolları, 1 × 5 veya 5 × 1, yalnızca 5 sayısını içermektedir. Ancak, 4 bir bileşik sayıdır çünkü bu, her iki sayının da 4'ten küçük olduğu bir çarpım şeklindedir. Asal sayılar, aritmetiğin temel teoreminden ötürü sayı teorisi alanında merkezi öneme sahiptir: 1'den büyük her doğal sayı, ya bir asal sayıdır ya da asal sayıların çarpımı olarak, sıralamalarından bağımsız bir şekilde, benzersiz olarak çarpanlarına ayrılabilir.

<span class="mw-page-title-main">Algoritma</span> bir problem sınıfının nasıl çözüleceğine dair kesin bir tarif

Algoritma, belli bir problemi çözmek veya belirli bir amaca ulaşmak için tasarlanan yol. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesidir. Genellikle bilgisayar programlamada kullanılır ve tüm programlama dillerinin temeli algoritmaya dayanır. Aynı zamanda algoritma tek bir problemi çözecek davranışın, temel işleri yapan komutların veya deyimlerin adım adım ortaya konulmasıdır ve bu adımların sıralamasına dikkat edilmelidir. Bir problem çözülürken algoritmik ve sezgisel (herustic) olmak üzere iki yaklaşım vardır. Algoritmik yaklaşımda da çözüm için olası yöntemlerden en uygun olan seçilir ve yapılması gerekenler adım adım ortaya konulur. Algoritmayı belirtmek için; metinsel olarak düz ifade ve akış diyagramı olmak üzere 2 yöntem kullanılır. Algoritmalar bir programlama dili vasıtasıyla bilgisayarlar tarafından işletilebilirler.

<span class="mw-page-title-main">Lineer cebir</span> Uzay matematiği

Doğrusal cebir ya da lineer cebir; matematiğin, vektörler (yöney), vektör uzayları, doğrusal dönüşümler, doğrusal denklem takımları ve matrisleri (dizey) inceleyen alanıdır. Vektör uzayları, modern matematiğin merkezinde yer alan bir konudur. Bundan dolayı doğrusal cebir hem soyut cebirde hem de fonksiyonel analizde sıkça kullanılır. Doğrusal cebir, analitik geometri ile de alakalı olup sosyal bilimlerde ve fen bilimlerinde yaygın bir uygulama alanına sahiptir.

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

<span class="mw-page-title-main">Karolenj İmparatorluğu</span>

Karolenj İmparatorluğu, 8. ve 9. yüzyıllarda Frank kökenli Karolenj Hanedanı üyesi krallar tarafından yönetilmiş ve başkenti Metz olan bir imparatorluktur. Hanedanın en tanınmış üyesi olan Şarlman döneminde Karolenj İmparatorluğunun sınırları günümüzdeki Fransa, Almanya, Kuzey İtalya, Hollanda, Belçika ve İsviçre dahil Batı ve Orta Avrupa'nın büyük bir bölümünü kapsamaktaydı. Karolenj İmparatorluğu daha sonra kurulacak olan Kutsal Roma Cermen İmparatorluğu'nun başlangıcı sayılabilir. Karolenj döneminin simgesi Aachen Kilisesi'dir.

<span class="mw-page-title-main">Doğal seçilim</span> fenotipteki farklılıklar nedeniyle bireylerin farklı şekilde hayatta kalması ve üremesi; evrimin temel mekanizması

Doğal seçilim, canlıların fenotiplerindeki farklılıklardan ötürü hayatta kalma şansının ve üreme başarısının değişkenlik göstermesidir. Evrimin esas mekanizmalarından biri olup, bir popülasyonun nesiller boyunca karakteristik olan kalıtsal özelliklerindeki değişimdir. Charles Darwin, kendi görüşüne göre kasıtlı olarak gerçekleştirilen yapay seçilime karşılık kendiliğinden gerçekleşen "doğal seçilim" terimini popülerleştirmiş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.

<span class="mw-page-title-main">Hızlı Fourier dönüşümü</span>

Hızlı Fourier dönüşümü bir dizinin ayrık Fourier dönüşümünü (DFT) ya da ters ayrık dönüşümünü hesaplayan bir algoritmadır. Fourier analizinde bir sinyal bulunduğu uzaydaki gösteriminden frekans uzayıki gösterimine ya da tersine dönüştürülür. DFT'de ise ayrık veri dizileri farklı frekans öğelerine ayrılır. Bu operasyon her ne kadar birçok alanda kullanışlı olsa da, doğrudan formüllerle hesabı hızlı ve pratik değildir; bu nedenle DFT hesabı için FFT algoritmaları kullanılmaktadır.

<span class="mw-page-title-main">III. Charles</span> Birleşik Krallık kralı (2022–günümüz)

III. Charles, Birleşik Krallık ve diğer 14 İngiliz Milletler Topluluğu bölgesinin kralı. Annesi II. Elizabeth'in ölümü sonrasında 8 Eylül 2022 tarihinde tahta çıktı. 1952'den tahta çıkışına kadar Cornwall Dükü ve Rothesay Dükü olarak Britanya tarihindeki en yaşlı ve en uzun süre görev yapan veliaht ve aynı zamanda 26 Temmuz 1958'den tahta çıkışına kadar bu unvanı taşıyan en uzun süre görev yapan Galler prensi olmuştur. Görevi devraldığı sırada Charles aynı zamanda 73 yaşında Britanya tahtına geçen en yaşlı isim olmuştur.

<span class="mw-page-title-main">Makine öğrenimi</span> algoritmaların ve istatistiksel modellerin kullanımıyla bilgisayarların yapacakları işleri kendileri çözebilmeleri

Makine öğrenimi (ML), veriden öğrenebilen ve görünmeyen verilere genelleştirebilen ve dolayısıyla açık talimatlar olmadan görevleri yerine getirebilen istatistiksel algoritmaların geliştirilmesi ve incelenmesiyle ilgilenen, yapay zekâda akademik bir disiplindir. Makine öğrenimi, bilgisayarların deneyimlerinden öğrenerek karmaşık görevleri otomatikleştirmeyi sağlayan bir yapay zeka alanıdır. Bu, veri analizi yaparak örüntüler tespit etme ve tahminlerde bulunma yeteneğine dayanır. Son zamanlarda yapay sinir ağları, performans açısından önceki birçok yaklaşımı geride bırakmayı başardı.

<span class="mw-page-title-main">Hash tablosu</span>

Bilişim bilimlerinde komut çizelgesi, komut işlevini tanıyıcı değer olarak bilinen benzersiz anahtarı bir değerle eşleyen bir veri yapısıdır. Böylece komut çizelgesi bir birleşik dizidir. Komut işlevi, ilişkin değerin arandığı anahtarı bir dizi elemanının indisine çevirir.

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

<span class="mw-page-title-main">İki parçalı graf</span>

Graf teorisinde, düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrılabilen graflara iki parçalı graf adı verilir.

<span class="mw-page-title-main">Düğüm (matematik)</span> grafik teorisinde, bir grafikteki diğer birimlerle, kenarlarla bağlantılı birim

Düğüm matematikte ve özellikle çizge teorisinde, bir çizgeyi oluşturan temel elemandır. Bir çizge temel olarak düğüm ve kenarlardan oluşur. Çizge görselleştirilirken genellikle düğümler çember, kenarlar da çizgi veya ok şeklinde gösterilir.

<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.

<span class="mw-page-title-main">Temsil teorisi</span>

Temsil teorisi soyut cebirdeki cebirsel yapıları, daha somut olan matematiksel nesnelerin dönüşümleri olarak tasvir etmeye çalışan bir matematik dalıdır. Örneğin soyut bir grubunu bir vektör uzayı 'nin eşyapı dönüşüm grubunun() içinde görmeye çalışır. Böyle temsillere doğrusal temsil denir, çünkü bu temsil aslında grubundan genel lineer grup 'ye bir morfizma yazmak demektir. Böyle bir temsil bulmaktaki amaç, grubunu çalışmak için lineer cebir kullanmaktır. Soyut gruplardaki çarpma işlemi, özellikle bir bilgisayar için matris çarpmasından daha zordur. Soyut bir grubun doğrusal temsillerini kullanarak, gruptaki kimi hesaplamaları bilgisayara yaptırmak daha kolay olur.

<span class="mw-page-title-main">Yapı</span> bir nesne veya sistemdeki birbiriyle ilişkili unsurların düzenlenmesi ve organizasyonu veya bu şekilde organize edilmiş nesne veya sistem

Yapı, maddi bir nesne veya sistemdeki birbiriyle ilişkili unsurların düzenlenmesi ve organizasyonu veya bu şekilde organize edilmiş nesne veya sistemdir. Maddi yapılar, binalar ve makineler gibi insan yapımı nesneleri ve biyolojik organizmalar, mineraller ve kimyasallar gibi doğal nesneleri içerir. Soyut yapılar bilgisayar bilimlerindeki veri yapılarını ve müzik formunu içerir. Yapı türleri arasında bir hiyerarşi, çoktan çoğa bağlantılar içeren bir bağlantı veya uzayda komşu olan bileşenler arasındaki bağlantıları içeren bir kafes bulunur.

<span class="mw-page-title-main">Graf (matematik)</span> kenarlarla çiftler halinde bağlanmış köşeler

Matematikte graf ya da çizge, nesne çiftlerinin bir anlamda "ilişkili" olduğu bir dizi nesne kümesini belirleyen bir yapıdır. Nesneler, köşeler adı verilen matematiksel soyutlamalara karşılık gelir ve ilgili düğüm çiftlerinin her birine bir kenar, ayrıt adı verilir. Tipik olarak bir graf, kenarları için çizgiler veya eğriler ile birleştirilen, düğümler için bir nokta veya daire kümesi olarak diyagram şeklinde gösterilir. Graflar ayrık matematikte çalışmanın amaçlarından biridir.

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.

<span class="mw-page-title-main">IV. Urbanus</span> Papa

IV. Urbanus, doğum ismiyle Jacques Pantaléon, 29 Ağustos 1264'ten ölümüne kadar Katolik Kilisesinin papası ve Papalık Devleti'nin başıydı. Kendisi bir kardinal değildi, o zamana kadar kardinal olmadan papa olan sadece birkaç papa bulunmaktaydı.