Tip:
Highlight text to annotate it
X
Derinlik Öncelikli Arama'nın optimal olmadığını düşünürsek,
bu algoritma ne için tercih edilebilir?
Yanıt alan gereksinimiyle ilgili.
Burada, çok geniş veya sonsuz büyüklükte
bir ikili ağaca karşılık gelen bir durum uzayı gösteriliyor.
1'inci, 2'nci, 3'üncü düzeyden, n'inci düzeye inerken,
ağaç gittikçe genişliyor.
Şimdi her bir algoritma için sınırın nasıl olacağına bakalım.
Genişlik Öncelikli Arama için sınırın böyle olacağını biliyoruz,
bunun için, n'inci düzeye indiğimizde, 2 üzeri n'lik bir
alana gereksinim duyacağız.
Ucuzluk Öncelikli Arama için sınır biraz daha karmaşık olacak.
Maliyete göre bunun gibi bir kenar oluşturacak,
ama sonuçta yakın miktarda düğümü tutması gerekecek.
Ama Derinlik Öncelikli Arama için, alt düzeylere indikçe, bu dalda devam ediyoruz,
burası bittiğinde geri çıkıyoruz, ve her noktada sınırımızda en fazla n düğüm oluyor.
2 üzeri n düğüm yerine n düğüm olması, Derinlik Öncelikli Arama'nın büyük bir tasarrufu.
Tabii, aynı zamanda keşfedilmiş durumlar kümemiz varsa,
pek de tasarruf yapamıyoruz.
Ama bu kümeyi tutmuyorsak, saklanan alan açısından, Derinlik Öncelikli Arama'nın
çok büyük bir avantajı oluyor.
Algoritmalarda bakılacak bir özellik de
tamlık özelliğidir. Tamlık, eğer bir yerde bir hedef varsa,
algoritmanın onu bulacağını belirtir.
Şimdi çok büyük yerine sonsuz büyüklükteki ağaçları düşünelim,
ve ağacın derinliklerinde bir yerde gizli bir hedefin bulunduğunu varsayalım.
Soru şu: Bu algoritmaların her biri tam mıdır?
Yani hedefe bir yol bulacakları kesin midir?
Bu anlamda tam olduğunu düşündüğünüz algoritmaların kutucuklarını işaretleyin.