Ich habe es geschafft, Graph Suche damit in C# zu implementieren, mit the PDF.
Ich habe 3 Listen verwendet - Frontier (offene Liste), Blattliste und "Baumzweig" -Liste.
Frontier ist die Warteschlange, in der PDF erwähnt, es ist eine gemeinsame Priorität Warteschlange von besten bis schlechtesten sortiert.
Blattliste hält nur Blätter, sortiert von schlechtesten bis besten, wir werden es brauchen, wenn wir entscheiden, welches Blatt zu vergessen. SMA vergisst nur Blätter, nicht ganze Zweige.
Die Verzweigungsliste enthält vollständig erweiterte Knoten, deren untergeordnete Objekte alle im Speicher vorhanden sind. Wir werden es brauchen, um die Zustandsüberschneidung zu testen.
Ich habe schnelle binäre Heaps für Frontier und Leaf-Liste und Hash-Tabelle für Tree Branch-Liste verwendet.
Knoten sollten die folgenden zusätzlichen Informationen halten:
Successors Iterator mit Position (Position für den Hinweis in Nachfolgern Liste benötigt wird). Wir dürfen unsere Nachfolge-Enumeration auf keinen Fall auf Null zurücksetzen, wenn wir das vergessen, weil es möglich ist, dass wir den gerade hinzugefügten Knoten vergessen. Ich benutze IEnumerator, int für Position und bool für "Fertig" -Flag.
Nachfolgerliste. Wir brauchen dies unweigerlich für die Aufwärtsausbreitung von f-cost. Auch ich behalte einfache Nachfolgestatus-Liste - wie [blockiert, vergessen, existiert]. Es wird benötigt, um vergessene und blockierte Knoten im Auge zu behalten. (Gesperrt - in Graph - von einem Knoten, der schneller expandiert)
Zwei Fs im PDF erwähnt, in unserem aktuellen F und am besten vergessen Nachfolger F.
Knoten Tiefe
Das Sortieren von Knoten sowohl in der Grenz- als auch in der Blattliste sollte wie folgt erfolgen: "Wenn wir Enumerationsflag" beendet "haben, wählen Sie den am besten vergessenen Nachfolger F, ansonsten wählen Sie F, wenn gleich, wählen Sie am tiefsten". Die Blattliste ist in umgekehrter Reihenfolge sortiert, wobei genau die gleiche Bedingung verwendet wird.
Basisalgorithmus Umriss ist wie folgt (ähnlich PDFs):
Wir besten Knoten aus Grenze holen, wenn es „fertig“ Flag - wir wissen, dass wir in Erinnerung rufen, setzen Sie den Iterator, und wir müssen in diesem Fall den besten vergessenen Nachfolger F zurücksetzen (aus komplizierten Gründen).
Wenn wir diesen Nachfolger noch nicht in der Liste haben (kann sein, wenn wir uns erinnern) - erzeugen wir ihn und setzen ihn wie in PDF beschrieben.
Dann folgt die komplexeste Sache - wir testen, ob der Knoten mit dem gleichen Zustand in der Liste der Grenz- oder Baumzweige existiert. Wenn ja, beschreibe ich, was ich später tun soll. Wenn nicht, fügen wir einfach Kind zur Grenze hinzu (und entfernen Eltern von der Blattliste).
In allen Fällen, wenn die Aufzählung der Nachfolger endet - wir tun das sogenannte Backup der f-Kosten, und wenn wir keine vergessenen Knoten haben (und einige Nachfolger haben), entfernen wir den aktuellen Knoten aus der Grenze und fügen Sie es zur Verzweigungsliste hinzu.
Wie vergessen: wir erstes Blatt aus Blattliste (das schlechteste Blatt), entfernen Sie es von der Grenze holen, entfernen Sie sich von den Eltern Nachfolger Liste, update (Abnahme) am besten vergessenen Nachfolgers des F-Mutter, falls erforderlich, und wenn das Elternteil nicht an der Grenze ist - wir entfernen es aus der Liste der Baumzweige und fügen es zur Grenze hinzu und fügen es auch zur Blattliste hinzu, wenn es jetzt ein Blatt ist (hat keine Nachfolger mehr).
Was zu tun ist, wenn wir einen Nachfolger generieren, der bereits in der Grenz- oder Baumzweigliste ist. Zuerst müssen wir es besser testen - wir vergleichen PathCost + H (das "Original" F) der beiden Knoten. Beachten Sie, dass wir gesicherte Fs überhaupt nicht vergleichen können - das wird nicht funktionieren. Wenn es nicht besser ist - wir setzen den Nachfolgerstatus einfach auf blockiert. Wenn es so ist - könnte es der Fall sein, dass der schlechtere Knoten eine Wurzel eines großen Teilbaums ist (zu kompliziert, um es noch einmal zu erklären). In diesem Fall schneiden wir den Teilbaum vollständig und SMA vergisst eine Menge von Knoten auf einmal. Nachdem wir den schlechteren Knoten durch den besseren Knoten ersetzt haben, entfernen wir den schlechteren Knoten aus seiner übergeordneten Nachfolgerliste, aus der Grenz-, Blattliste oder sogar der Baumzweigliste (es könnte sogar dort sein!).), setze den Nachfolgestatus auf blocked für seine Eltern und vergiss nicht zu überprüfen, ob die Eltern des schlechtesten Knotens jetzt alle Knoten blockiert haben - wir müssen ihn auf unendlich setzen, weil er zum Endknoten wurde.
Vielleicht habe ich nicht die einfachste Implementierung, aber es ist das einzige, das für mich funktioniert. Ich habe 8-Puzzles für Tests verwendet - Lösen von n-Schritten mit einem Minimum von (n + 1) -Memory (Startknoten zählend) und Überprüfen der Lösungsoptimalität mit herkömmlichem a-Stern. Ich habe 20-30 Stunden damit verbracht, alle Details herauszufinden - das Hauptproblem lag in der Komplexität der Fail - Testfälle - ich habe die "Ersetze mit besseren Knoten" Logik Bugs nur in 20 + Schritten mit einem umfangreiche Tests von Tausenden zufälligen Samen. Achten Sie auch auf Prioritätswarteschlangen - ich musste das Element in so vielen Fällen neu einfügen, da jede Änderung von F, am besten vergessenes F, oder "Fertig" -Flag - die Sortierreihenfolge ändert. Ich überprüfte schließlich die Konsistenz meiner binären Heaps bei jedem Ausstieg. Und die Hauptidee, den kompliziertesten Bug des endlosen Radfahrens loszuwerden, besteht darin, zu überprüfen, dass Sie in allen Fällen nicht die F-Werte verringern. Auf diese Weise werden die F's weiter zunehmen.
Ich werde die Arbeitsimplementierungsquelle in ein paar Wochen teilen.
ist das eine Art A *? –
Haben Sie die Aima-Talk-Gruppe ausprobiert? http://tech.groups.yahoo.com/group/aima-talk/ –
Warum gehen Sie davon aus, dass jeder dieses Buch hat und lesen, worüber Sie auch sprechen? Und wie hängt diese Programmierung zusammen, wenn eine Beschreibung in einem Buch korrekt ist oder nicht – jitter