TechCodeview

Bilgilendirilmemiş arama, kaba kuvvet yöntemiyle çalışan bir genel amaçlı arama algoritmaları sınıfıdır. Bilgisiz arama algoritmaları, ağacın nasıl geçileceği dışında durum veya arama alanı hakkında ek bilgiye sahip değildir, bu nedenle buna kör arama da denir.

Bilgisiz arama algoritmalarının çeşitli türleri şunlardır:

Genişliğe Öncelikli Arama Derinlik öncelikli arama Derinlik Sınırlı Arama Yinelemeli derinleşen derinlik öncelikli arama Tek tip maliyet araması Çift Yönlü Arama

1. Genişliğe Öncelikli Arama:

• Genişlik öncelikli arama, bir ağaç veya grafikte gezinmek için en yaygın arama stratejisidir. Bu algoritma bir ağaçta veya grafikte geniş kapsamlı arama yapar, dolayısıyla buna genişlik öncelikli arama denir.
• BFS algoritması aramaya ağacın kök düğümünden başlar ve bir sonraki seviyedeki düğümlere geçmeden önce mevcut seviyedeki tüm ardıl düğümleri genişletir.
• Genişlik öncelikli arama algoritması, genel grafik arama algoritmasının bir örneğidir.
• FIFO kuyruk veri yapısı kullanılarak uygulanan genişlik öncelikli arama.

Avantajları:

• Herhangi bir çözüm olması durumunda BFS bir çözüm sağlayacaktır.
• Belirli bir problem için birden fazla çözüm varsa, BFS en az sayıda adım gerektiren minimum çözümü sağlayacaktır.

Dezavantajları:

• Ağacın her seviyesinin bir sonraki seviyeye genişletilmesi için belleğe kaydedilmesi gerektiğinden çok fazla hafıza gerektirir.
• Çözüm kök düğümden uzaktaysa BFS'nin çok fazla zamana ihtiyacı vardır.

Örnek:

Aşağıdaki ağaç yapısında, ağacın BFS algoritmasını kullanarak kök düğüm S'den hedef düğüm K'ye geçişini gösterdik. BFS arama algoritması katmanlar halinde geçiş yapacak, böylece noktalı okla gösterilen yolu izleyecek ve geçilen yol şöyle olacaktır:

 S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K 

Zaman Karmaşıklığı: BFS algoritmasının Zaman Karmaşıklığı, BFS'de en sığ Düğüme kadar geçen düğüm sayısıyla elde edilebilir. Burada d=en sığ çözümün derinliği ve b her durumda bir düğümdür.

T(b) = 1+b²+b³+.......+ b^D= Ö (b^D)

Uzay Karmaşıklığı: BFS algoritmasının uzay karmaşıklığı, O(b) olan sınırın Bellek boyutuyla verilir.^D).

maven'i yükle

Tamlık: BFS tamamlandı, yani en sığ hedef düğümü belirli bir derinlikteyse BFS bir çözüm bulacaktır.

Optimumluk: Yol maliyeti düğüm derinliğinin azalmayan bir fonksiyonu ise BFS optimaldir.

2. Derinlik Öncelikli Arama

• Derinlik öncelikli arama, bir ağaç veya grafik veri yapısında gezinmek için kullanılan yinelemeli bir algoritmadır.
• Buna derinlik öncelikli arama denir çünkü kök düğümden başlar ve bir sonraki yola geçmeden önce her yolu en büyük derinlikteki düğüme kadar takip eder.
• DFS, uygulanması için bir yığın veri yapısı kullanır.
• DFS algoritmasının süreci BFS algoritmasına benzer.

Not: Geri izleme, özyinelemeyi kullanarak tüm olası çözümleri bulmaya yönelik bir algoritma tekniğidir.

Avantajı:

• DFS, yalnızca kök düğümden geçerli düğüme giden yol üzerindeki düğüm yığınını depolaması gerektiğinden çok daha az bellek gerektirir.
• Hedef düğüme ulaşmak BFS algoritmasına göre daha az zaman alır (eğer doğru yolda giderse).

Dezavantajı:

• Birçok durumun tekrar ortaya çıkma ihtimali vardır ve çözümü bulmanın garantisi yoktur.
• DFS algoritması derinlemesine aramaya gider ve bazen sonsuz döngüye girebilir.

Örnek:

Aşağıdaki arama ağacında, derinlik öncelikli aramanın akışını gösterdik ve şu sırayı izleyecektir:

Kök düğüm ---->Sol düğüm ----> sağ düğüm.

Kök düğüm S'den aramaya başlayacak ve A'yı, ardından B'yi, ardından D ve E'yi geçecek, E'yi geçtikten sonra, E'nin başka ardılı olmadığı ve hala hedef düğüm bulunmadığı için ağacı geri izleyecektir. Geriye doğru takip ettikten sonra C düğümünü ve ardından G düğümünü geçecek ve burada hedef düğümü bulduğunda sona erecektir.

Tamlık: DFS arama algoritması, sınırlı bir arama ağacındaki her düğümü genişleteceğinden sonlu durum uzayında tamamlanır.

Zaman Karmaşıklığı: DFS'nin zaman karmaşıklığı, algoritmanın geçtiği düğüme eşdeğer olacaktır. Şunlar tarafından verilmektedir:

T(n)= 1+ n²+ n³+......+ n^M=O(n^M)

Burada, m= herhangi bir düğümün maksimum derinliği ve bu, d'den (En sığ çözüm derinliği) çok daha büyük olabilir.

Uzay Karmaşıklığı: DFS algoritmasının kök düğümden yalnızca tek bir yolu depolaması gerekir, dolayısıyla DFS'nin alan karmaşıklığı saçak kümesinin boyutuna eşdeğerdir; O(bm) .

En uygun: DFS arama algoritması, hedef düğüme ulaşmak için çok sayıda adım veya yüksek maliyet oluşturabileceğinden optimal değildir.

3. Derinlikle Sınırlı Arama Algoritması:

Derinlik sınırlı arama algoritması, önceden belirlenmiş bir limitle derinlik öncelikli aramaya benzer. Derinlikle sınırlı arama, Derinlik öncelikli aramadaki sonsuz yolun dezavantajını çözebilir. Bu algoritmada, derinlik sınırındaki düğüm, daha sonra ardıl düğümleri olmadığı için işlem yapacaktır.

Derinlikle sınırlı arama iki başarısızlık koşuluyla sonlandırılabilir:

• Standart başarısızlık değeri: Sorunun herhangi bir çözümü olmadığını gösterir.
• Kesme hatası değeri: Belirli bir derinlik sınırı dahilinde soruna yönelik hiçbir çözümü tanımlamaz.

Avantajları:

Derinlik sınırlı arama Bellek açısından verimlidir.

Dezavantajları:

• Derinlik sınırlı aramanın aynı zamanda eksiklik dezavantajı da vardır.
• Sorunun birden fazla çözümü varsa optimal olmayabilir.

Örnek:

Tamlık: Çözüm derinlik sınırının üzerindeyse DLS arama algoritması tamamlanır.

Zaman Karmaşıklığı: DLS algoritmasının zaman karmaşıklığı O(b^ℓ) .

Uzay Karmaşıklığı: DLS algoritmasının uzay karmaşıklığı O'dur (b�ℓ) .

java'da while döngüsü yapmak

En uygun: Derinlik sınırlı arama, DFS'nin özel bir durumu olarak görülebilir ve ℓ>d olsa bile optimal değildir.

4. Tekdüzen Maliyetli Arama Algoritması:

Tek tip maliyetli arama, ağırlıklı bir ağaç veya grafiğin üzerinden geçmek için kullanılan bir arama algoritmasıdır. Bu algoritma her kenar için farklı bir maliyet mevcut olduğunda devreye girmektedir. Tekdüzen maliyetli aramanın temel amacı, en düşük kümülatif maliyete sahip olan hedef düğüme giden yolu bulmaktır. Tek tip maliyetli arama, düğümleri kök düğümdeki yol maliyetlerine göre genişletir. Optimum maliyetin talep edildiği herhangi bir grafiği/ağacı çözmek için kullanılabilir. Öncelik kuyruğu tarafından tekdüze maliyetli bir arama algoritması uygulanır. En düşük kümülatif maliyete maksimum öncelik verir. Tek tip maliyet araması, tüm kenarların yol maliyetinin aynı olması durumunda BFS algoritmasına eşdeğerdir.

Avantajları:

• Tek tip maliyet araması optimaldir çünkü her durumda en az maliyetli yol seçilir.

Dezavantajları:

• Aramanın içerdiği adımların sayısını umursamaz ve yalnızca yol maliyetiyle ilgilenir. Bu algoritmanın sonsuz bir döngüde sıkışıp kalmasından dolayı olabilir.

Örnek:

Tamlık:

Tek tip maliyet araştırması tamamlandı, örneğin bir çözüm varsa UCS onu bulacaktır.

Zaman Karmaşıklığı:

C* olsun Optimum çözümün maliyeti , Ve e hedef düğüme yaklaşmak için atılan her adımdır. O zaman adım sayısı = C*/ε+1 olur. Burada 0 durumundan başlayıp C*/ε noktasına kadar devam ettiğimiz için +1 aldık.

Bu nedenle, Tekdüzen maliyetli aramanın en kötü durum zaman karmaşıklığı O(b^{1 + [C*/e]})/ .

Uzay Karmaşıklığı:

Aynı mantık uzay karmaşıklığı için de geçerlidir, dolayısıyla Tekdüzen maliyetli aramanın en kötü durum uzay karmaşıklığı şöyledir: O(b^{1 + [C*/e]}) .

En uygun:

Tek tip maliyetli arama, yalnızca en düşük yol maliyetine sahip yolu seçtiğinden her zaman en uygunudur.

5. Yinelemeli derinleşme, derinlik öncelikli Arama:

Yinelemeli derinleştirme algoritması, DFS ve BFS algoritmalarının birleşimidir. Bu arama algoritması en iyi derinlik sınırını bulur ve bunu bir hedef bulunana kadar sınırı kademeli olarak artırarak yapar.

Bu algoritma, belirli bir 'derinlik sınırına' kadar derinlik öncelikli arama gerçekleştirir ve hedef düğüm bulunana kadar her yinelemeden sonra derinlik sınırını artırmaya devam eder.

Bu Arama algoritması, Genişlik öncelikli aramanın hızlı araması ile derinlemesine öncelikli aramanın bellek verimliliğinin avantajlarını birleştirir.

bir sınıf birden fazla sınıfı genişletebilir mi

Yinelemeli arama algoritması, arama alanının büyük olduğu ve hedef düğümün derinliğinin bilinmediği durumlarda bilgisiz arama için kullanışlıdır.

Avantajları:

• Hızlı arama ve bellek verimliliği açısından BFS ve DFS arama algoritmasının avantajlarını birleştirir.

Dezavantajları:

• IDDFS'nin ana dezavantajı, önceki aşamanın tüm çalışmalarını tekrarlamasıdır.

Örnek:

Aşağıdaki ağaç yapısı yinelemeli derinleşen derinlik öncelikli aramayı göstermektedir. IDDFS algoritması hedef düğümü bulana kadar çeşitli yinelemeler gerçekleştirir. Algoritmanın gerçekleştirdiği yineleme şu şekilde verilmektedir:

1. Tekrar-----> A
2. Tekrar ----> A, B, C
3. Tekrar---------->A, B, D, E, C, F, G
4'üncü Tekrar---------->A, B, D, H, I, E, C, F, K, G
Dördüncü yinelemede algoritma hedef düğümü bulacaktır.

Tamlık:

Bu algoritma, dallanma faktörünün sonlu olması durumunda tamamlanır.

Zaman Karmaşıklığı:

B'nin dallanma faktörü ve derinliğin d olduğunu varsayalım, o zaman en kötü durum zaman karmaşıklığı şöyle olur O(b^D) .

Uzay Karmaşıklığı:

IDDFS'nin alan karmaşıklığı O(bd) .

En uygun:

Yol maliyeti düğüm derinliğinin azalmayan bir fonksiyonu ise IDDFS algoritması optimaldir.

6. Çift Yönlü Arama Algoritması:

Çift yönlü arama algoritması, hedef düğümü bulmak için biri ileri arama olarak adlandırılan başlangıç ​​durumundan, diğeri ise geriye doğru arama olarak adlandırılan hedef düğümden olmak üzere iki eşzamanlı arama gerçekleştirir. Çift yönlü arama, tek bir arama grafiğini, birinin aramaya başlangıç ​​noktasından, diğerinin ise hedef tepe noktasından başladığı iki küçük alt grafikle değiştirir. Bu iki grafik birbiriyle kesiştiğinde arama durur.

Çift yönlü arama, BFS, DFS, DLS vb. gibi arama tekniklerini kullanabilir.

Avantajları:

Java'da a'nın ascii'si

• Çift yönlü arama hızlıdır.
• Çift yönlü arama daha az bellek gerektirir

Dezavantajları:

• Çift yönlü arama ağacının uygulanması zordur.
Çift yönlü aramada hedef durumun önceden bilinmesi gerekir.

Örnek:

Aşağıdaki arama ağacında çift yönlü arama algoritması uygulanmıştır. Bu algoritma bir grafiği/ağacı iki alt grafiğe böler. Düğüm 1'den ileri yönde ilerlemeye başlar ve hedef düğüm 16'dan geriye doğru yönde başlar.

Algoritma, iki aramanın buluştuğu 9. düğümde sona erer.

Tamlık: Her iki aramada da BFS kullanırsak Çift Yönlü Arama tamamlanır.

Zaman Karmaşıklığı: BFS kullanarak çift yönlü aramanın zaman karmaşıklığı O(b^D) .

Uzay Karmaşıklığı: Çift yönlü aramanın uzay karmaşıklığı O(b^D) .

En uygun: Çift yönlü arama Optimaldir.