Implementierung eines Stern (A *) Algorithmus in Java

Haftungsausschluss: Ich habe wenig Hintergrund in Java, da ich überwiegend ein C# -Entwickler bin.Implementierung eines Stern (A *) Algorithmus in Java

Möchte die Java-Implementierung von A * -Algorithmus haben.
Ja, ich sah viele Versionen des gleichen online und ich kann nicht zwischen ihnen wählen.

Ich bin auf der Suche nach einer A * -Algorithmus-Implementierung, die alle neuen Funktionen von Java verwendet, die den Algorithmus schneller macht (auch wenn ein bisschen Bit). Der Grund ist, dass wir dies für die Pfadsuche auf einem MMO implementieren, und so hat die Leistung oberste Priorität.

Irgendwelche Zeiger (auf atleast, wo man sucht)?

Quelle

2011-01-07 naveen

Können Sie uns Links zu Versionen geben, die Sie bereits gefunden haben? Und die Verwendung von "neuen Features von Java" wird übrigens keinen Algorithmus schneller machen. – darioo

Link wieder abgelaufen, hier ist das neueste für jeden wie mich, der das findet: https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/AStar.java –

@BattleBarnes das mitgelieferte bidirektionale A * ist noch schneller – Karussell

Probieren Sie mehrere, messen, wählen Sie die schnellste, passen Sie sich an Ihre Bedürfnisse. Die Leistung wird hauptsächlich durch die Wahl der heuristischen Funktion bestimmt, die unabhängig von A * ist.

Wenn die Heuristik fest ist, wird die Implementierung der Prioritätswarteschlange wahrscheinlich zum Engpass, versuchen Sie also pairing heaps. Dies sind einige der schnellsten Heap-Datenstrukturen in der Praxis, und sie haben den Vorteil gegenüber binären Heaps, dass sie O (1) -Einfügungszeit + amortisierten O (log n) pop-min erlauben. Dies ist im erwarteten Fall vieler A * -Schleifen wichtig, wo die Warteschlange gefüllt ist, aber niemals vollständig geleert wird, d. H. Die Anzahl von Einfügungen ist viel größer als die Anzahl von Einbrüchen.

Wenn der Speicher ein Problem wird, wechseln Sie zu Iterative-Vertiefung A * (IDA *) oder rekursive Best-First-Suche (RBFS).

Wenn nichts funktioniert, erwägen Sie einen Approximationsalgorithmus (gierige Suche). Einfach eine anständig geschriebene A * Schleife zu optimieren, wird dir keine enormen Beschleunigungen bringen.

Siehe Russell and Norvig für Algorithmen und eine gute Diskussion der Probleme.

Quelle

2011-01-07 11:25:54

Welche Datenstruktur sollte für die 'closedList' verwendet werden? – st0le

Eine Hash-Tabelle. Oder ein rot-schwarzer Baum. Oder ein Splay-Baum. Oder was sich als am schnellsten herausstellt. @st0le, du hast recht, dass das wichtig ist, aber meiner Erfahrung nach sind schnelle Sets leichter zu bekommen als schnelle Priority Queues. –

@ sk0le: Wenn ein geschlossener Satz überhaupt benötigt wird, ist das. –

Wenn Leistung oberste Priorität hat, ist A * wahrscheinlich nicht Ihre beste Wahl. A * bietet eine genaue Lösung und wird daher weiter verarbeitet, bis die richtige Antwort gefunden ist. Es gibt andere leichte Lösungen, die gut genug Lösungen in viel schnellerer Zeit geben: z. B. Zwangsbergsteigen oder Best-First, sogar eine einfache Tiefe zuerst.

Quelle

2011-01-07 11:36:46 Robert

+1. Durch die Optimierung des A * -Codes wird das OP nicht zu einer Leistungspokal. –

-0, wie ja, A * ist wahrscheinlich nicht so effizient, aber die Alternativen, die Sie brauchen, sind Beschleunigungstechniken, die spezifisch für Pfadfindung wie Kontraktionshierarchien und Ähnliches sind. – Karussell

Implementierung eines Stern (A *) Algorithmus in Java

Antwort

Verwandte Themen