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