Arama algoritmalarını anlamak için yardıma ihtiyacınız var (A *, IDA *, DFS, BFS, IDDFS, vb.)

Question

Yapay zekada (AI) kullanılan arama algoritmalarını anlamakta bazı sıkıntılarım var.

• A* ve IDA* (Iterative Deeping A Star) arasındaki tam fark nedir? Sadece sezgisel işlev mi? Eğer öyleyse, ben hala IDA * nasıl çalıştığını düşünemiyorum ..:/
IDA * BFS (Breadth-First search) aynı (mı genişleyen derinliği sadece 1 seviye olduğunda, yani - sadece bir tek düzeyine göre hareket "aşağı", IDDFS 0 olarak eşdeğerdir buluşsal işlevi dışında IDA * ve BFS)
• mi IDDFS (Iterative-Deeping Depth-First Search) arasındaki fark IDA * aynı,()
• vardır ne tam olarak IDDFS - aşağı doğru sadece bir seviyesine geçmek, daha sonra DFS (Depth-First Search) kullanıyor musunuz? Eğer öyleyse, bu şekilde bir çok devlet hesaplanır (genişler). Bunlardan çok daha fazlası .. Ya da bunun gibi - DFS'u belirli bir derinlikte kullanın, sonra "yaprakları" (son genişletilmiş düğümleri) saklayın ve bunların üzerinden yineleyin dan
• nerede " yinelemeli" geliyor (ki, aslında, BFS? olan) tekrar DFS kullanılır? Gördüğüm gibi, IDDFS yinelemeli değil, hala yinelemeli, sadece BFS ve DFS? Ya da ben hatalıyım? Veya bu "yinelemeli" ifadesinin, yinelemenin tersiyle alakası yok mu?
• IDA * için "yineleme" nedir?

Bazı örnekler sağlayabilir misiniz? Bütün gün bu algoritmalar hakkında okudum, onların avantajlarını ve dezavantajlarını, karmaşıklığı vb. Biliyorum, ama iyi bir örnek bulamadım (A * hariç, BFS ve DFS'yi biliyorum, diğerleri beni rahatsız ediyor). Farklı yerlerde IDA * için bazı sahte kodlar buldum, ama hepsi tamamen farklıydı.

Örnekler, algoritmaları anlamanın en iyi yolu olabilir ... ama bulamıyorum. TopCoder numaralı telefondan bile IDA * ile ilgili hiçbir şey bulamadım. çok

Teşekkür

---

DÜZENLEME: (

ben wiki makaleleri okudum ve yeni bir şey arıyorum!.Here some nice articles, ama çok teorik kim olursa örnekler (Hayır, herhangi bir özel şey yok. Ama yine de çok yararlı. Onları tavsiye ederim (=

Answer 1

Tekrarlayan derinlemesine ilk arama ile başlayalım.

Buradaki fikir, derinlik-ilk aramanın verimli olması, ancak her zaman yakın zamanda doğru cevaba ulaşmamasıdır. Yani, 1 derinliğine DFS yapın.Cevabı bulamadıysanız, 2. derinliğe kadar yapın. Cevabı bulana kadar tekrarlayın veya pes etmeye karar verin. Bu, arama ağacında en kısa yolu otomatik olarak verir, çünkü N uzunluğunda bir tane varsa, N + 1 uzunluğunda bir yol ararsınız.

Uygulamanız gerekenler, önce bir derinliği değiştirmektir. arama N düğümleri derin olacak (yani, N derinseniz yeni düğümler oluşturmayın) ve N'yi artırarak söyleyin. N değerinden daha fazlasını saklamayın ve ne yaparsanız yapın DFS için.

Yineleme, arama derinliğini yinelemeli olarak arttırır. Performans, ikiden büyük bir dallanma faktörü göz önüne alındığında, şaşırtıcı bir şekilde iyi olabilir, çünkü bu durumda derinlik-sınırlanmış bir DFS'nin maliyeti, ulaşılan en düşük seviyededir.

İlk önce yinelenen DFS'yi öğrenin, ardından bunu IDA * 'ya uygulayın. On beş yıl önce bu aramalarda erken bir Korf makalesini okudum ve IDA * 'nın nasıl iyi çalıştığını hatırlamıyorum, ama asıl sorunun, ilk etapta yinelemeli derinleşmeyi anlamamanızdır.