Brauchen Sie Hilfe für das Verständnis Suchalgorithmen (A *, IDA *, DFS, BFS, IDDFS, etc.)

Question

Ich habe einige Probleme einige der Algorithmen für die Suche zu verstehen, verwendet in AI (künstliche Intelligenz).

• Was ist der genaue Unterschied zwischen A * und IDA * (Iterative Deeping A Star) ? Ist nur die heuristische Funktion? Wenn ja, noch kann ich mir einfach nicht vorstellen, wie IDA * Werke ..: /
• Sie IDA * die gleiche wie BFS (Breadth- erste Such) (wenn die Tiefe der Erweiterung nur 1 Ebene ist, meine ich - nur ein um eine Stufe „nach unten“ bewegt wird, gibt es einen Unterschied zwischen IDA * und BFS )
• IDDFS (Iterative-Deeping Tiefensuche) die gleichen wie IDA * , mit Ausnahme der heuristischen Funktion (die in 0 IDDFS )
• Was genau ist IDDFS - nach unten bewegen nur ein Ebene, dann mit DFS (Tiefensuche) ? Wenn ja, werden auf diese Weise viele der Staaten berechnet (erweitert) viel mehr als diejenigen .. Oder es ist wie dieser - Verwendung DFS mit bestimmten Tiefe, dann speichern Sie die „Blätter“ (die letzten erweiterten Knoten) und durchlaufen, sie zu nutzen DFS wieder (was eigentlich ist BFS ?)
• Wo " iterative " kommt? Wie ich sehe, IDDFS ist iterativ haupt nicht, es ist immer noch recursiive, nur Mischungen BFS und DFS ? Oder irre ich mich? Oder dieser " iterative " hat nichts mit dem Gegenteil von Rekursion zu tun?
• Was ist " iterative " für IDA * ?

Könnten Sie bitte geben Sie einige Beispiele nennen? Ich lese den ganzen Tag über diese Algorithmen, ich kenne ihre Vor- und Nachteile, die Komplexität, etc., aber ich konnte einfach keine gute Beispiele finden (mit Ausnahme von A *, ich weiß, BFS und DFS, die anderen stört mich). Ich fand einige Pseudo-Code für IDA * an verschiedenen Orten, aber sie waren alle ganz anders aus.

Beispiele wären die beste Art und Weise zu verstehen, algorithms..but ich nicht finden kann. Auch in TopCoder Ich habe nichts über IDA finden *.

Ich habe den Wiki-Artikel gelesen, und ich bin auf der Suche nach etwas Neuem (:

Vielen Dank!

---

EDIT: Hier ein paar schöne Artikel , aber sie zu theoretisch sind. Keine Beispiele, keine irgendwelche speziellen Dinge. Aber immer noch sehr nützlich. Ich würde ihnen empfehlen (=

Answer 1

Beginnt sie mit iterativer Tiefensuche Vertiefung.

Die Idee ist, dass die Tiefensuche effizient ist, aber nicht unbedingt trifft die richtige Antwort in absehbarer Zeit. Also, eine DFS zu einer Tiefe von 1. Wenn Sie die Antwort nicht gefunden, tun Sie es bis zu einer Tiefe von 2. Wiederholen Sie, bis Sie die Antwort finden, oder entscheiden, bis zu geben. Dies gibt Ihnen automatisch den kürzesten Weg auf dem Suchbaum, da man nie für einen Pfad der Länge sucht N + 1, wenn es eine der Länge N.

Was Sie brauchen, zu implementieren, zu tun ist, eine Tiefensuche zu ändern, so wird es gehen N-Knoten tief (dh erzeugen keine neuen Knoten, wenn Sie N tief), und nennen Sie es mit N. Sie Erhöhung nicht speichert etwas mehr als der Wert von N und was auch immer Sie für DFS tun würde.

Die Iteration wird mit iterativ die Suchtiefe zu erhöhen. Die Leistung kann überraschend gut sein, ein Verzweigungsfaktor größer als zwei gegebenen, wie in diesem Fall der Großteil der Kosten für ein Tiefen begrenzt DFS auf dem niedrigsten Niveau erreicht ist.

Lernen iterative DFS Vertiefung ersten, dann gelten, dass IDA *. Ich las ein frühes Korf Papier auf diesen Recherchen über 15 Jahre her, und kann mich nicht erinnern, wie IDA * funktioniert sehr gut, aber Ihr Hauptproblem ist, dass Sie nicht iteratives verstehen in erster Linie der Vertiefung.