Patricia ağacı (PATRICIA Tree)

Bilgisayar bilimlerinde sıkça kullanılan TRIE ağacının özel bir hali olan patricia ağacında genellikle sözlüksel olarak (lexiconically) veriler tutulur. Radix ağacı (radix tree) ve farklı ikil ağacı (crit bit tree) ile oldukça benzer olan patricia ağacının, TRIE ağacından en büyük farkı tutulan verilerin ortak olan noktalarından sonra farklılaşılan yönlerine göre dallanma olmasıdır.

Aşağıda verilen kelimelerin ağaçta tutulmaları gösterilmiştir:

• Evren
• Evreşe
• Evreka
• Evrensel

Yukarıdaki şekilde de gösterildiği üzere ağacın dallanmaları verilen kelimelerin birbiri ile farklılaştıkları noktalarda olmaktadır.

Yinelemeli Derinleşen Derin Öncelikli Arama Algoritması (Iterative Deepining Depth First Search, IDDFS)

Bilgisayar bilimlerinin Çeşitli alanlarında (örneğin yapay zeka, veri Yapıları VEYA sekil kuramı (grafik teorisi) gibi) Kullanılan arama algoritmalarından birsidir.

Algoritma, derin Öncelikli dram (derinlik ilk arama) Üzerine kurulu oldugu icin, literatürde "yinelemeli derinleşen derinliği ilk arama (yinelemeli derinleşen, derin Öncelikli arama)" Olarak da geçmektedir.  

Algoritma basitçe derinlik değerini Bir ​​değişkende tutmakta bu ona Adımda arttırmaktadır. Değeri ziyaretinde
ona Adımda derinliğin, bir döngü değişkeni (döngü değişkeni) gibi düşünülerek derinleştiği Kabil Edilebilir ziyaretinde Yineleme Yapısı (yineleme) Basit bir döngü (loop) Olarak dusunulebilir.

Örneğin aşağıdaki şekli (grafik) ele alalım:

Ağaçta görüldüğü Üzere İki adet döngü (döngü) bulunmaktadır. İteratif Derinleşme arama algoritmasını bu ağaç uzerinde çalıştıracak olursak, algoritma Öncelikle derinlik değerini (bundan Sonra d değişkeni (değişken) ile ifade edilecektir) ona Adımda Bir ilerletecektir başlatarak 0'dan.  

d = 0 göster arama Click:
Bir
, d = 1 için arama:
A (tekrar A değerine bakar) M.Ö. (sanki ağacın en üstteki üç düğümü, sekılde gösterildiği gibi bağlanmış Kabil Edilebilir, daha alttaki derinliklerde Bulunan DEFG düğümlerine hiç bakamaz)
göster arama Click d = 2 :
ABDECFG (Bu aramada sanki sondaki daireler (döngü) bulunmuyormuş gibi Kabil Edilebilir, göster çünkü belirtilen derinlik bu dairelere Kadar inemez)
d = 3 göster arama Click:
ABDBECFGA
: arama Click d = 4
ABDBDEBCFGABC

Yukarıdaki arma İşlemi, derinlik arttıkça devam etmektedir.

Arama algoritmalarının değerlendirildiği Bazi kriterler bulunmaktadır. Buna Göre IDDFS (iteratif derinleşme derinliği ilk arama) algoriması "tam" algoritma Olarak Kabil Edilebilir. Tamlık Teriminin (tamlık) anlamı aşağıdaki sekılde tanımlanabilir:
 

Bir arama algoritması, bütün düğümleri dolaşarak aranan düğümü bulmayı garanti ediyorsa bu algoritmaya tam arama algoritması ismi verilir.

Örneğin yine yukarıdaki sekil Click klasik derin Öncelikli arama (derinlik ilk arama) algoritmasını ele alsaydık, bu algoritmanın tam olmadığını söyleyebilirdik. Eklendi bunun sebebi DFS algoritmasının dolaşması sırasında, aşağıdaki döngüye girmesidir:

ABDBDBD (BD ikilisi sosuza Kadar tekrar eder)

Kısacası ABD düğümleri dışındaki düğümlere asla bakmaz. Bu anlamda tam olmadığını söyleyebiliriz.

BFS (birinci arama, yayılma Öncelikli VEYA sığ Öncelikli arama genişlik)  her zaman Click tam Kabul Edilebilir ISE algoritması, sebebi Bir ​​Sonraki derinlik seviyesine inmeden sonra, Bulunduğu seviyedeki düğümleri bitirmesi ziyaretinde bu sayede Bütün Ağaca bakmayı garanti etmesidir.

Algoritmanın karmaşıklığına  değinecek olursak. Aşağıdaki sekılde Bir formül ile karşılaşırız.

Bu formülde Görülen terimler sekil kuramında (grafik teorisi) Sıkça Kullanılan Bazi değerlere atıfta bulunur.
d değerinin derinlik oldugunu Daha Önce belirtmiştik. b ile gösterilen Değer imkb dallanma katasyısıdır (faktör dallanma).

Kısaca ona  düğümün kaç çocuğu Olduğu (sipariş üzerinden, kaç düğüme gidilebildiği)  Olarak Tutulur. Örneğin tam dolu ikili arama ağacının (ikili arama ağacı) Değeri 2'dir, b. Genelde en kötü durum analizinde bütün, Çocukların dolu Olması ihtimali uzerinde durulur. AYRICA İstatistiksel Olarak ortalamam çocuk sayısının da Alındığı olur. Örneğin Şehirlerin tutulduğu bır sekılde onu şehirden gidilebilecek Şehir Sayısı değişmektedir. Bu b DURUMDA Değeri Ortalama Değer Olarak hesaplanabilir.  

Bu açıklama Ardından yukarıdaki denkleme tekrar bakarak anlamaya çalışalım.

IDDFS algoritmasında, tr altta Bulunan imkb 2 kere dolaşıldığını ziyaretinde böylece düğümlerin 1 kere (d sabitlendiğinde en altta kalan Düğümler hangileri imkb) dolaşıldığını, d-1 derinliğindeki düğümlerin kök düğüme (kök) Kadar onun düğümün, bulundugu seviyeye Göre kaç kere dolaşıldığını hesaplayabileceğimize Göre yukarıdaki denklem çıkarılabilir.  

Diğer Bir deyişle d = 0 oldugunda kök 2 1 kökün Çocukları 1 ziyaretinde = kök 1 kere dolaşılırken d Click kere dolaşılmış olur. = 3 oldugunda kök 3 kere d çocukları 2 tr ziyaretinde ziyaretinde alttaki Çocuklar imkb 1 kere dolaşılmış olur. Görüldüğü onu artışında kök derinlik Kadar Altındaki onu düğüm imkb birer azalarak en nihayetinde derinliğin Üzere  yapraklar (yaprak)  tek bir kere dolaşılmış olmaktadır.

SONUÇ Olarak Yukarıdaki formülün ilk terimi kök (d + 1) 1 (tek düğüm d + 1 kere dolaşılmıştır), ikinci terimi kökün çocukları (db (kökün çocukları (ki Sayısı b'dir) derinlik Kadar (ki d ile gösterilir) dolaşılmıştır).

Yukarıdaki bu formülü Daha toplu sekılde aşağıda gösterildiği gibi yazabiliriz:

Algoritmanın dolaşma (arama) zamanı karmaşıklığı yukarıda gösterildiği Gibidir. Terimler birleştirildiğinde  en kötü durum analizi (en kötü durum analizi)  Click O (b d ) gösterimi Kullanılabilir.

Hafıza karmaşıklığı imkb O (bd) olarak ifade Edilebilir. Eklendi bunun sebebi d derinliğindeki Bir ağacın b onun seviyesinde adet çocuğu bulunması durumunda bd Kadar düğüm olacağıdır. Algoritma, çalışması sırasında ilave etmek, düğümlere ve İhtiyaç duymaz ziyaretinde şeklin kendisi uzerinde dolaşarak sonuca ulaşır.

Örnek 

Aşağıdaki grafikte İçin:

Bir derinlik Öncelikli arama, bir Başlayan gösterilen grafikte, sol kenarlari Sağ kenarlarına ÖNCE Seçilmiş oldugunu varsayarak, ve, arama varsayarak, daha ÖNCE Ziyaret edilen Düğümler hatırlar ziyaretinde (bu küçük bir grafik olduğundan) Ziyaret edecek, onlari tekrarlamak istemiyorum Aşağıdaki Sırayla Düğümler: A, B, D, F, E, C, G, bu arama geçilen kenarlari Bir ​​formu Trémaux ağacı , Önemli uygulamalarla Bir yapıya grafik teorisi .    

Sipariş, A, B, D, F, E, A, B, D, E, I, vb sonsuza bir yakalanmış, B, D, E düğümleri Ziyaret Daha Önce Ziyaret Düğümler sonuçları hatırlamanıza gerek kalmadan Cardio aramayı Sahne D döngüsü asla Değerlendirmeleri C ziyaretinde VEYA G

Algoritma çalışan Sol-Sağ yukarıdaki gibi devam varsayarak, bu döngü önler ziyaretinde aşağıdaki derinliklerde aşağıdaki düğümleri ulaşacak derinleşme:

• 0: A
• 1: (tekrar), B, C, D,

(Geleneksel derinlik Öncelikli arama vermedi zaman tekrarlamalı derinleşmenin şimdi C gordu Unutmayın).

• 2: A, B, D, F, C, G, I, K

(Hala C görür Unutmayın, ancak Daha Sonra geldi. AYRICA on iki kez Farklı Bir yoldan E görür geri F döngüler Unutmayın ettik.)

• 3: A, B, D, F, E, C, G, I, K, B

Daha Fazla derinlik eklendiğinde algoritma Vazgeçer Başka Bir şube çalışmadan ÖNCE bu grafik Click, iki kür "ABFE" ve "AEFB" sadece sadece uzun alirsiniz ettik.

Aşağıdaki sözde kod özyinelemeli derinliği Sınırlı DFS (denilen DLS) cinsinden Uygulanan IDDFS Gösterir.

Prosedür IDDFS (root)
      Click derinlik dan 0 Kadar ∞ 
        Bulunan ← DLS (kök, derinlik) Eger Bulundu ≠ sıfır
              yield Bulundu Prosedür DLS (düğüm, derinlik)
      imkb derinlik = 0 ziyaretinde düğüm Bir hedeftir
          Dönüş düğümü
      else if derinlik> 0
          foreach düğümün alt 
            Bulunan ← DLS (çocuk, derinlik-1) Eger Bulundu ≠ sıfır
                  yield Bulundu
      Dönüş boş
        


            

Derin Limitli Arama (Depth Limited Search) Algoritması

Bilgisayar bilimlerinde Kullanılan arama algoritmalarından birisidir. Bu algoritma Esas Olarak  derin Öncelikli arama (derinlik ilk arama DFS)  ile Cardio çalışmaktadır ancak tek farkı arama İşlemi sırasında özellikle dairelere (döngü) takılma ihtimaline Karşı sınır onlemi alınmış OLMASIDIR.  

Örneğin aşağıdaki şekli ele alalım:

Yukarıdaki sekil tanım İtibariyle Bir ağaç Özelliği göstermektedir. Yani A.Ş. yönlü daire içermeyen Bir şekildir (yönlendirilmiş Mercury grafik) . Ancak Cardio şekle aşağıdaki gibi Basit bir Bağlantı Daha eklenseydi artık ağaç olmayacaktı: 

Yukarıdaki yeni sekılde derin Öncelikli bir arama yaptığımızı A düğümünden İşleme başladığımızı düşünelim ettik. Örneğin orta Sıra (infix) ziyaretinde L NR (sol Üst sağ, sol düğüm sağ) sırasıyla arama yaptığımızı düşünelim. Daire içermeyen ilk sekılde LNR sırasına Göre aşağıdaki sonucun çıkması beklenir:  

DBEAFC

Ancak ikinci sekilde LNR sırasına Göre ÖNCE en soldaki terim yazılmaya çalışılacak, Böylece A> B-> D> A-> B> D> A-> B> D> A sırasıyla namütenahi dönülecek ziyaretinde hiçbir, zaman Bitmeyecek Bir fasit daireye girilecektir (Sonsuz döngü). Bu durum literatürde sol özyineleme (sol özyineleme) Olarak geçer. Yani şeklimizin (VEYA HERHANGİ Bir yapının) sol tarafında kendini tekrarlayan bir durum bulunmakta dolayısıyla derin Öncelikli arama yapılamamaktadır.

Çözüm Olarak bu Yazının da konusu Olan Sınırlı derin Öncelikli arama (derinlik sınırlı arama, DLS) algoritması Kullanılabilir. Bu algoritmada gidilebilecek düğüm sayısına Bir tahdit konulmakta ziyaretinde ancak Verilen sayıda düğüme gidilebilmektedir.

Algoritmanın kodlanması

Yukarıda izah edilen algoritma aşağıdaki sekılde kodlanabilir:

Yukarıdaki özyineli fonksiyonda (recursive fonksiyon) bakılan düğüm hedef olana Kadar dolaşma İşlemi devam etmektedir. Dolaşma İşlemi sırasında klasik derin Öncelikli aramalarda Kullanılan Yığın (stack) Düğümler geri geçilen ettik kullanılmıs dönülüp aranmak Üzere yığında tutulmuştur.   

Şayet aranan düğüm Verilen derinlikten Daha derin değilse arama İşlemi devam etmektedir ancak Verilen derinlik geçildiği zaman arama İşlemi Daha Derine gitmemekte Ana O artık ettik Kadar aranmak Üzere yığınladığı düğümleri işlemektedir.

Yukarıda anlatılan algoritma bilgisiz bir arama algoritmasıdır (bilgisiz arama algoritması) AYRICA algoritmanın hafıza karmaşıklığı (bellek karmaşıklığı) ziyaretinde sınırlıdır Çünkü algoritmada aranabilecek düğüm sayısında Bir sınır bulunmaktadır.  

Normal derinliği ilk arama gibi, derinlik Sınırlı arama bir olan bilgisiz arama. Bu derinliği ilk arama tam gibi Çalışır, ama arama derinliğine Bir Maksimum Paket limiti koyarak tamlığı Konusundaki sakıncaları önler. Arama hala O derinliğe Ötesinde tepe genişletmek bile, bunu yapmayacağım ettik böylece sonsuz derin takip EDECEK yolları VEYA takılıyorum döngüleri. Tüm Grafikleri en az tamlığını garanti derinlik Sınırı, icinde imkb nedenle derinlik Sınırlı arama Bir Çözüm bulacaksınız.

Arama Maksimum Paket arama derinliği atamanız Gereken yerde tepe belirleyin ziyaretinde başlatmak
Geçerli köşe hedefi devlet OLUP olmadığını Kontrol edin
Hicbir şey yapma: Değilse
Evet imkb: dönmek
Kontrol güncel köşe Maksimum Paket arama derinliği icinde imkb
Değilse: Hicbir şey yapma
Eger öyleyse:
Vertex genişletin ardılları Tüm ONUN ettik Tasarruf yığının
Yığının bütün, Köseler Click özyinelemeli DLS Çağrı Adım 2'ye geri donun A.Ş.

kod

DLS (düğüm, hedef, derinlik) { 
  if (derinlik> = 0) { 
    if (düğüm == gol) 
     x = gol (hedef = derinlik) eğer 
       Dönüş düğümü 

    Onun çocuk olarak Click genişletmek (düğüm) DLS (çocuk, hedef, derinlik -1) 
  } 
} Özellikler Uzay karmaşıklığı Derinlik Sınırlı arama Dahili Olarak Kullandığı bu Yana derinliği ilk arama, uzay karmaşıklığı normal derinliği ilk arama eşdeğerdir. Zaman karmaşıklığı Derinlik Sınırlı arama içten derinlik ilk arama kullandığından, Zaman karmaşıklığı normal derinliği ilk arama eşdeğerdir ziyaretinde ( \ Olduğu O Vert V \ vert + \ vert E \ vert Yerlerde) \ Vert V \ vert köşelerin Sayısı ziyaretinde stantlar Click \ Vert E \ vert keşfedilmeyi kenarların Sayısı Click grafikte. Tüm grafik KEŞFETMEK etmediğini derinlik Sınırlı arama, ancak Bağlı Belirtilen icinde yatıyor Sadece Bir Parçası Unutmayın. Bütünlük Derinlik Sınırlı arama sonsuz uzun yolları takip edemez, ne de genel olarak, Gösterilen döngü sıkışmış olsa bile bu Verilen arama derinliğinin Ötesinde Yatan HERHANGİ Bir Çözüm inançsız olmadigindan algoritma tam Değildir. En Fazla aranan derinliği Bir ​​çözelti derinliğinden Daha Büyük olacak sekılde seçilir Ancak algoritma tamamlandı olur. Optimalite Derinlik SınırlıSorumlu arama optimum Değildir. Hala ilk ziyaretinde böylece muhtemelen Başka yolu Bazi Çözüm Daha Pahalı Bir Çözüm bulma, Sonuna Kadar tek yol araştırıyor derinliği ilk aramanın sorunu Vardır.
      

Derin öncelikli arama (depth first search)

Bir ağaç dolaşma algoritmasının (ağaç travers algoritma, ağaç kastetmek) ilk ÖNCE alt seviyesinde Bulunan komşularını araması durumudur.

Örneğin aşağıdaki ağacı ele alalım:

Ağacı dolaşma sırlaması örneğin 3, 2, 7, 1, 9, 8, 5 şeklindeyse bu dolaşmaya derin Öncelikli arama (derinlik ilk arama) ismi VERİLEBİLİR.

Bu arama sıralamasında, dolaşma Sıralaması aşağıdaki ihtimallerden birisi Olabilir:

LRN: Sol Sağ Düğüm (Sol Sağ Düğüm)

RLN: Sağ Sol Düğüm (Sağ Sol Düğüm)

RNL: Sağ Düğüm Sol (Sağ Düğüm Sol)

RLN: Sağ Sol Düğüm (Sağ Sol Düğüm)

Yani Öncelikle düğüm Sonra Altındaki Üyelere hareket edilir.

Sığ Öncelikli Arama (Genişlik İlk Arama)  algoritma Tipine Göre imkb:

NLR: Düğüm Sol Sağ (Düğüm Sol Sağ)

NRL: Düğüm Sağ Sol (Düğüm Sağ Sol)

ihtimallerinden birisi Tercih Edilebilir. Buradaki fark ilk bakılan düğümün, MEVCUT düğümün Altında Olan Bir düğüm Yerine Cardio seviyede olmasinin. Yani derin Öncelikli aramada, sığ aramadan Farklı Olarak ÖNCE düğümün alt seviyedeki düğümlerden Aramaya başlanır.

başladığımız il merkezinden gidilebilecek en uzak ile  gidilir.Daha  sonda gidecek Başka Yer kalmayınca Bir Önceki ile geri Dönerek oradan gidilebilecek en uzak ile gidilir ziyaretinde Daha Sonra Başlangıç ​​noktasına dönülür.Bu algoritmada hep Daha Derine gitme isteği ile hareket eder.Başka bır sekılde anlatilmak İSTENİRSE Bir ağacın ana köünden beligbli Bir ​​çıkmaza denk gelene Kadar ağacın derinliklerine doğru Işaretleyerek hareket edilir. Sonrasında çıkmaz il karşılaşınca geri dönülüp kardeş Olan düğüm aranır ziyaretinde kardeş Olan ilk düğüme rastlayınca tekrardan Daha derinlere doğru hareket edilir. İlk resimde DFS algoritmasının psuedo kodu bulunmaktadır.  

Aşağıdaki görselde imkb DFS algoritmasının örnek graf uzerinde Anlık çalışma Durumu gösterilmiştir.

Graf dolaşmak Click planlanan bu algoritmalar ile çok Farklı Bir Yol izleyeceğiz.Öncelikle internet Sitelerinin İçeriği de graf Yapısı oluşturmaktadır. Örneğin http://preciselyconcise.com/apis_and_installations/downloadables/jsoup/test.php  şu sitenin kaynak Kodunu inceleyecek olursak

Bu kodlar da Bir ağaç Yapısı olusturmus oluyorlar.

Bu ağaç yapısını oluşturduktan Sonra imkb Jsoup kullanarak bütün, sitelerde istedigimiz graf yapısını kurabilir.BFS DFS A.Ş. Algoritmaları ile aramak istedigimiz kelimelerin HTML kodlarına ulaşabiliriz. Bir site içerisinde Bulunan Tüm kelimelerde gezebilir, siralama arama yapabiliriz ettik.  

Şekillerde (Graph) sığ öncelikli arama (Breadth First Search, BFS)

Bu yazı,  ağaçlardaki sığ Öncelikli arama  ile karıştırılmamalıdır . Ağaçlar (ağaçları)  bilindiği Üzere yönlü dairesel olmayan şekillerdir (yönlendirilmiş Mercury grafik) dolayısıyla ağaçlar uzerinde bu yazıda anlatılan Sıra (kuyruk)  yapısına ve İhtiyaç Duyulmaz.

Sığ Öncelikli arama Bir Başlangıç ​​düğümünden başlayarak Sıradaki Komşuları dolaşan arama algoritmasıdır. Bu arama algoritmasında amaç ÖNCE Başlangıç ​​düğümüne Yakın Manzara düğümlere bakmaktır.

Bu arama şekli suya atılan Bir damlanın suda çıkardığı halkalara benzetilebilir. Başlangıç ​​düğümüne en Yakın Manzara halka Sonra ikinci Yakın Manzara halka Sonra diğerleri şeklinde giden bir arama algoritmasıdır ettik.

Bu Durumu aşağıdaki örnek Üzerinden anlamaya çalışalım:

Örnek Olarak yukarıda Bulunan şekli ele alalım. Örneğimizde Başlangıç ​​düğümü (düğüm) Olarak bir düğümünü seçtiğimizi ziyaretinde aranan düğümün e düğümü oldugunu düşünelim.  

A düğümünün komşuluk listesini (adjacency listesi) çıkarıyoruz:  

komşu (A) = {C, B}

Bu komşulara sırasıyla bakılıyor ziyaretinde bu komşuların komşuluk Listeleri çıkarılıyor:

bakılanlar: {A, B, C}

komşular = komşu (B), komşu (C) = {D, E, E}

Arana düğüm E, bu Adımda bulunmuştur.

Yukarıdaki örnekte görüldüğü Üzere Bir Sonraki derinliğe inilmeden sonra, o derinlikte Olan (Başlangıç ​​düğümüne O UZAKLIKTA Olan) Bütün Düğümler dolaşılıyor Ardından Bir alt seviyeye iniliyor ziyaretinde.

Yukarıdaki örnekte bütün, ağaç dolaşılmış gibi dusunulebilir. Örneğin sekil (grafik) aşağıdaki gibi olsaydı:

Bu DURUMDA Z düğümüne hiçbir, zaman bakılmayacaktı Çünkü aranan düğüm Z düğümünden Daha sığ Bir derinlikte Olacaktı.

Kısacası BFS arama algoritması ile aranan düğümün derinliğine Kadar Olan bütün, düğümlere bakılır ancak bu derinlikten Daha aşağıda Olan düğümlere bakılmasına gerek yoktur.