A* langsam mit großen Graphen

[Nasenbaer]

Hi,
implementiere seit einigen Tagen ne Wegfindealgo nach A* für schachbrettartige Graphen wie z.B. bei Strategiespielen.
Wenn ich ein Spielfeld mit 200*200 Zellen nehme und Start und Ziel durch ne Mauer bis auf nen kleinen Spalt komplett abschotte, dann brauch er schon etliche Sekunden bis er das Ziel findet.
Mit 60*25 geht das ganz fix und er findet auch nen ordentlichen Pfad. (lass das in der Konsole ausgeben)

Also Frage ich mich ob ich vielleicht irgendwas falsch mache oder ob ich einfach nicht zuviel von A* erwarten sollte ohne spezielle Vorkehrungen zur Optimierung zu treffen.

Hier mal meint Code. Vielleicht hab ich ja nur nen Denkfehler:

bool CGraphs::AStar()
{
// Priority Queue für offene Nodes
std::priority_queue<CAStarNode*,std::vector<CAStarNode*> ,PrioOrderAStarNode> PQueue;
// Startknoten erstellen
CAStarNode* StartNode = new CAStarNode(this->Start.X, this->Start.Y, 0, GetDistance(this->Start));
PQueue.push(StartNode);

// Menge mit bereits explorierten Knoten
CSet *VisitedNodes = new CSet();

while( PQueue.size() != 0 )
{
CAStarNode* Node = PQueue.top();
PQueue.pop();

// Am Ziel angelangt?
if( Node->CurrentPosition == this->Destination )
{
// Ausgabe des Pfads
MarkGraph(Node->Actions);
return true;
}
else if (!VisitedNodes->find(*Node) ) // Wenn Node noch nicht exploriert
{
// Füge sie zu explorierten hinzu
VisitedNodes->Add(*Node);
MarkNode(Node->CurrentPosition.X,Node->CurrentPosition.Y,this->VISITED);
// Erstelle Liste mit möglichen Aktionen (4 horizontale/vertikale + 4 diagonale Bewegungen möglich)
std::list<Point> Actions = GetActions(Node->CurrentPosition);
std::list<Point>::iterator iter;

for(iter=Actions.begin(); iter != Actions.end();++iter)
{
// Erstelle neuen Knoten
CAStarNode* NewNode = new CAStarNode();
// Figur befindet sich nun dan der neuen Stelle
NewNode->CurrentPosition.X = iter->X;
NewNode->CurrentPosition.Y = iter->Y;
// Speichere bisherige Aktionen + neue Aktion
NewNode->Actions = Node->Actions;
NewNode->Actions.push_back(*iter);

// Wenn sich Figur diagonal bewegt, dann bewerte es mit 14
if ((abs(NewNode->CurrentPosition.X - Node->CurrentPosition.X) +
abs(NewNode->CurrentPosition.Y - Node->CurrentPosition.Y))
> 1)
{
NewNode->Costs = Node->Costs + 14;
}
else // für horizontale/vertikale Bewegungen nimm 10 als Kosten
{
NewNode->Costs = Node->Costs + 10;
}

// Berechne die Geasamtkosten mittels aktueller Kosten + geschätze Entfernung
NewNode->TotalCosts = NewNode->Costs + GetDistance(NewNode->CurrentPosition);
// Speichere neuen Knoten im PQueue
PQueue.push(NewNode);
}

}
}
return false;
}

[del_4901]

Warum nimmst du nicht Kruskals, Priens .. etc. Algorithmus zur Wegfindung?

[Nasenbaer]

Kruskal und Prim nutzt man um minimale Spannbäume gegebener Graphen zu finden. Zur Wegfindung sind die meines Erachtens gänzlich ungeeignet. Dijkstra käme noch in Frage aber der ist im allgemeinen langsamer da es sich um ein uninformierte Suche handelt, A* dagegen um eine informierte, was der Geschwindigkeit zu Gute kommt.

[gereggter Gast]

Das 200er Spielfeld ist auch gleich 26mal größer als das Kleine. Länger wird es also schon brauchen. Bei so einfachen Fällen dürfte es allerdings nicht im Sekundenbereich liegen.
Die Geschwindigkeit von A* hängt aber auch immer von der Art des Hindernisses ab. Ist zwischen Start und Ziel eine kleine Trennwand, wird A* schnell einen Weg drum rum oder mglw. hindurch finden.
Ist der Start allerdings von oben unten und vorne (relativ zum Ziel) getrennt, dauert A* mitunter länger als mit dem ansonsten langsameren Dijkstra.

Poste mal deine Heuristik in GetDistance(..).
Und nur um sicher zu gehen (programmiere nicht mehr in C++)...
Die PriorityQueue läßt du richtig sortieren. Und nimmst auch immer das Feld mit dem kleinsten und nicht dem größten Wert. ;D

[Nasenbaer]

Jo der PQueue arbeitet richtig - das war auch mein Verdacht aber hab es überprüft und er schmeißt die Node aufsteigend sortiert nach Gesamtkosten raus.

Hier die Heuristik:
Für diagonale Schritte nehme ich 14 als Kosten (sprich trunc(sqrt(2)*10) ) und für gerade 10. Ist dan die Diagonaldistanz die berechnet wird und somit die optimale Schätzung der Weges, wenn keine Hindernisse das sind.

int CGraphs::GetDistance(const Point& p)
{
int DiagonalMoves = min(abs(p.X-this->Destination.X), abs(p.Y-this->Destination.Y));
// StraightMoves = Manhattan Distance - Diagonal Moves
int StraightMoves = abs(p.X - this->Destination.X) + abs(p.Y - this->Destination.Y)
- DiagonalMoves;
// 14 is a weight for Diagonal moves, because a diagonal move is longer than a straight one
// 10 is a weight for straight moves
return 14 * DiagonalMoves + 10 * StraightMoves;
}

[gereggter Gast]

Ich weiß zwar nicht, was die Manhattan-Distanz ist, aber sie scheint mir etwas unoptimal zu sein.
Nimm mal:

int CGraphs::GetDistance(const Point& p)
{
int deltaX = abs(p.X-this->Destination.X);
int deltaY = abs(p.X-this->Destination.X);
/* delta diagonalMoves left + the difference between the new position (after diagonal moving) and the destination */
if(deltaX < deltaY)
return 14*deltaX + 10*(deltaX - deltaY);
else
return 14*deltaY + 10*(deltaY - deltaX);
}

[registrierter Gast]

Ich weiß zwar nicht, was die Manhattan-Distanz ist, aber sie scheint mir etwas unoptimal zu sein.
Nimm mal:

int CGraphs::GetDistance(const Point& p)
{
int deltaX = abs(p.X-this->Destination.X);
int deltaY = abs(p.X-this->Destination.X);
/* delta diagonalMoves left + the difference between the new position (after diagonal moving) and the destination */
if(deltaX < deltaY)
return 14*deltaX + 10*(deltaX - deltaY);
else
return 14*deltaY + 10*(deltaY - deltaX);
}
Das kommt davon, wenn man sich nicht einloggt. Man kann es nachträglich nicht mehr editieren. :rolleyes:
deltaY ist natürlich abs(p.Y-this->Destination.Y);

[Nasenbaer]

So habs mal ausprobiert aber hat sich nichts wirklich verändert (den Fehler in Zeile 2 hab ich natürlich korrigiert gehabt).
Mit meiner Heuristik ca. 2 Minuten und bei deiner hab ich kurz nach 2 Minuten dann abergebrochen, da sich ja nix verändert hat.

Also das kann nicht mein Problem sein. Ich werd nochmal den Code von Wikipedia genau nachcoden und gucken obs dann besser wird.

[Trap]

Im schlimmsten Fall muss der Algorithmus alle 40.000 Knoten einmal besuchen, das sollte auf einem aktuellen Rechner keine 2 Minuten dauern, eigentlich nichtmal 1 Sekunde.

Guck mal nach wie oft jeder Teil vom Code ausgeführt wird.

[Gast]

Hi,
implementiere seit einigen Tagen ne Wegfindealgo nach A* für schachbrettartige Graphen wie z.B. bei Strategiespielen.
Wenn ich ein Spielfeld mit 200*200 Zellen nehme und Start und Ziel durch ne Mauer bis auf nen kleinen Spalt komplett abschotte, dann brauch er schon etliche Sekunden bis er das Ziel findet.

Man kann das sicher noch wesentlich effizienter programmiereren (verpointerte Datenstrukturen sind auf einem PC fast immer mies, wenn man auch Speicherverbrauch dagegen eintauschen kann).
Aber dir sollte auch klar sein, dass A* u.U. den ganzen Suchbaum durchsuchen muss, wenn man eine solch allgemeine Heuristik nutzt. Beliebtes Beispiel ist da eine U Form. Wenn du auch mit kleinen Fehlern zufrieden bist, würde ich dir einen hierarchischen A* vorschlagen. Damit findest um Größenordnungen schneller eine Lösung.
Allgemein kann man mit mehr Zwischenpunkten die Suche des A* extrem optimieren, da weniger in eine komplett falsche Richtung gesucht wird.

[Nasenbaer]

Ne er besucht tatsächlich jeen Knoten nur einmal. Ich werd jetzt mal den etwas anderen Alo umsetzen und gucken was passiert.

Ansonsten werd ich mal gprof drauf ansetzen.

[gereggter Gast]

Ne er besucht tatsächlich jeen Knoten nur einmal. Ich werd jetzt mal den etwas anderen Alo umsetzen und gucken was passiert.

Ansonsten werd ich mal gprof drauf ansetzen.Wie? Er besucht jeden Knoten einmal? Das darf aber nicht sein!


Hätte gedacht, die andere Heuristik würde zu einer schnelleren Lösung führen, weil sie im Grunde keine Heuristik darstellt, sondern der Distanz des optimalen Weges (ohne Hindernis) entspricht.

[Gast]

Wie? Er besucht jeden Knoten einmal? Das darf aber nicht sein!
Doch. Hängt von Startpunkt, Enpunkt und Hindernissen ab.


Hätte gedacht, die andere Heuristik würde zu einer schnelleren Lösung führen, weil sie im Grunde keine Heuristik darstellt, sondern der Distanz des optimalen Weges (ohne Hindernis) entspricht.
Es ist eine Heuristik. Und eine recht schlechte dazu. Aber leider so ziemlich die Beste, wenn man sich weiteres Preprocessing ersparen will.

[gereggter Gast]

Doch. Hängt von Startpunkt, Enpunkt und Hindernissen ab.Das muss schon ein reines, konstruiertes Hindernisparcour sein, dass er mit A* wirklich das ganze Feld durchsucht.
Nixdestotrotz würde ich für das Indexieren des ganzen 200er Feldes vielleicht 5, maximal 15 Sekunden mit Dijkstra veranschlagen.

Es ist eine Heuristik. Und eine recht schlechte dazu. Aber leider so ziemlich die Beste, wenn man sich weiteres Preprocessing ersparen will.Ist klar! :rolleyes:

[Nasenbaer]

Man kann das sicher noch wesentlich effizienter programmiereren (verpointerte Datenstrukturen sind auf einem PC fast immer mies, wenn man auch Speicherverbrauch dagegen eintauschen kann).
Aber dir sollte auch klar sein, dass A* u.U. den ganzen Suchbaum durchsuchen muss, wenn man eine solch allgemeine Heuristik nutzt. Beliebtes Beispiel ist da eine U Form. Wenn du auch mit kleinen Fehlern zufrieden bist, würde ich dir einen hierarchischen A* vorschlagen. Damit findest um Größenordnungen schneller eine Lösung.
Allgemein kann man mit mehr Zwischenpunkten die Suche des A* extrem optimieren, da weniger in eine komplett falsche Richtung gesucht wird.
Jo bei mir muss er nämlich ne U-Form laufen. Bei kleinen unzusammenhängenden Hindernissen ist er auch recht schnell, dass hab ich schon rausgefunden. Aber ich brauch ja nen Worst-Case Szenario, wenn man das mal in nem Spiel einsetzen will.
Ich hab jetzt mal nen Profiler drüber gejagt und folgendes kostet bei mir am meisten Zeit:

..
else if (!VisitedNodes->find(*Node) ) // Wenn Node noch nicht exploriert
..

Da ich das Set selbst implementiert hab und da auch nichts spannendes gemacht hab braucht find() O(n ). Meine Barriere ist ungefähr in der Mitte und führt von ganz oben nach fast ganz unten. D.h. es werden etwa Höhe*(Breite/2) exploriert. Und da wirkt sich O( n ) dann aber doch schon aus.
Vielleicht sollte man die bereits explorierten Nodes nach Entfernung vom Startknoten speichern so könnte man O(log n ) draus machen.

Zusätzlich sollt ich mir mal wohl den hierarchischen A* mal anschauen. Ich weiß nicht wie der arbeitet aber es würde ja schon wesentlich schnell sein wenn ich ihn vom Start erst zur Verbindung der beiden Hälften laufen lasse und dann von dort zum Ziel.

[Nasenbaer]

So hier auch mal eine Skizze zur Szene damit man sich das vorstellen kann:
S = Start
Z= Ziel
Roter Strich = Barriere

[Nasenbaer]

Das muss schon ein reines, konstruiertes Hindernisparcour sein, dass er mit A* wirklich das ganze Feld durchsucht.
Nixdestotrotz würde ich für das Indexieren des ganzen 200er Feldes vielleicht 5, maximal 15 Sekunden mit Dijkstra veranschlagen.

Ist klar! :rolleyes:
Ich meinte er besucht jeden Knoten den er untersucht nur einmal. Also, dass er nicht mehrmal den selben Knoten untersucht. Ingesammt untersucht wie gesagt ungefähr die Hälfte aller Knoten. Nämlich fast alle auf der linken Seite der Barriere und dann noch die Paar zum Ziel vom unteren Durchgang aus.

Der andere Gast hat aber recht. Die Heuristik ist schlecht aber dennoch die beste. :D Man könnte ne Heuristik schreiben die A* dazu veranlasst nur die Knoten, die letzlich zum Pfad gehören auch zu untersuchen. Aber die Suche nach dieser Heuristik ist genauso aufwendig wie die Pfadsuche selbst.
Sie halt deswegen die beste weil sie optimal ist (sprich den Weg nie überschätzt).

[Gast]

Ich hab jetzt mal nen Profiler drüber gejagt und folgendes kostet bei mir am meisten Zeit:

..
else if (!VisitedNodes->find(*Node) ) // Wenn Node noch nicht exploriert
..

Da ich das Set selbst implementiert hab und da auch nichts spannendes gemacht hab braucht find() O(n ). Meine Barriere ist ungefähr in der Mitte und führt von ganz oben nach fast ganz unten. D.h. es werden etwa Höhe*(Breite/2) exploriert. Und da wirkt sich O( n ) dann aber doch schon aus.
Vielleicht sollte man die bereits explorierten Nodes nach Entfernung vom Startknoten speichern so könnte man O(log n ) draus machen.
Die Stelle hab ich mir schon gedacht, obwohl ich schon vom STL-Set ausging, der nur O(log( n)) benötigt. Wobei, Achtung Theoriefalle, man schon einige Elemente braucht, um da einen Vorteil zu bekommen. Das Set war bei nem Test auf nem Core2Duo erst bei ~40 Elementen schneller wie die lineare Suche über nem Vektor.

Falls du nicht durch Multithreading ö.ä. mehrere Suchen gleichzeitig laufen lässt, macht es Sinn die Knoten selbst zu markieren, die du schon besucht hast. Schon hast du an der Stellen O(1). Da kannst du entweder ne ID für die Suche drin speichern, zum Vergleichen mit der aktuellen Such-ID, oder du musst die Markierungen hinterher wieder löschen.

[ethrandil]

Nur als Info: Mit einem HashSet bekommst du für die .contains(XY)-Methode eine Laufzeit von durchschnittlich O(1) hin!
Das solltest du wirklich nochmal überdenken.

Ansonsten multiplizier doch mal deine Heuristik mit einer großen Zahl, dann findet er nicht den kürzesten Weg aber imho schneller einen nicht optimalen.

Was du auch machen kannst, was aber Softwaretechnisch nicht so schön ist: Ein Flag am Knoten setzen, ob er bereits exploriert wurde. Das kanst du dann in WorstCase O(1) testen. (Das Flag kann auch die Nummer der Suche sein, dann musst du das Flag nie zurücksetzen.)

Wenn du wirklich einen schlimmen Fall testen willst:

http://img261.imageshack.us/img261/6428/astarbadcaseuy2.png (http://imageshack.us)

- eth

EDIT: Eine Anmerkung hat mir der Gast vorweggenommen ;)

[Nasenbaer]

Das Problem warum ich das STL Set nicht genommen hab war, dass es eine totale Relation auf den in ihr gespeicherten Elementen benötigt. Es wird halt nicht auf Gleichheit sondern auf "<" getestet. Ist ja auch nachvollziehbar, da ich dann nen Suchbaum aufbauen kann den ich in logarithmischer Zeit durchsuchen kann.

Ich werd jetzt mal die STL Hash_Set testen, weil die wohl genau das hat was dafür sinnvoll ist. :)

[Gast]

Das Problem warum ich das STL Set nicht genommen hab war, dass es eine totale Relation auf den in ihr gespeicherten Elementen benötigt.
Ein Set hat die Angewohnheit, dass ein Element nur einmal darin vorkommt.
Das ist beim auch beim STL Set so.
Gleichheit lässt sich schliesslich ja auch sehr einfach mit dem < Operator überprüfen und kostet bei der Implementierung nicht mal mehr Zeit.

Ich werd jetzt mal die STL Hash_Set testen, weil die wohl genau das hat was dafür sinnvoll ist.
Das Hash-Set in allen Ehren. Aber es produziert dir einen unnötigen Overhead, den du durch Einfärben(= Such-ID) der Knoten umgehen kannst. Einfärben von Knoten ist auch Softwaretechnisch vollkommen sauber und kommt in sehr sehr vielen Graphalgorithmen vor.

[Nasenbaer]

Ein Set hat die Angewohnheit, dass ein Element nur einmal darin vorkommt.
Das ist beim auch beim STL Set so.
Gleichheit lässt sich schliesslich ja auch sehr einfach mit dem < Operator überprüfen und kostet bei der Implementierung nicht mal mehr Zeit.

Das man damit auch die Gleichheit testen kann ist mir klar aber manchmal ist eine sinnvolle Ordnung zu definieren als die reine Gleicheit.

Das Hash-Set in allen Ehren. Aber es produziert dir einen unnötigen Overhead, den du durch Einfärben(= Such-ID) der Knoten umgehen kannst. Einfärben von Knoten ist auch Softwaretechnisch vollkommen sauber und kommt in sehr sehr vielen Graphalgorithmen vor.
Jo Tiefen- und Breitensuche färben letzlich ja auch nur. Werd ich jetzt auch so machen da hash_set nicht Teil des C++ Standards ist.
Es ist zwar bei Visual C++ und GCC verfügbar aber dennoch muss ich es ja nicht unbedingt nehmen wenns anders ähnlich schnell geht.

[gereggter Gast]

Hab es auch mal fix in Java nachprogrammiert und bin bei circa 0.4 Sekunden für ein 200er Feld und das U-Hindernis wie oben beschrieben.

[Nasenbaer]

Habs jetzt mit markierungen gemacht und unoptimierte code liefert 1,5Sekunden.
Optimiert für Athlon64 mit IA32 sinds 0,5Sekunden.

Kannste mir mal den source deiner Java app zukommen lassen?

[gereggter Gast]

Ohhh, muss ich erst hübsch machen. ;D
Gib mir 20 Minuten.

[Nasenbaer]

Jo danke. Wundert mich nämlich schon etwas gerade weil man ja immer meint, dass java nich so super schnell ist. Warscheinlich einer dieser Mythen die längst überholt sind. :)

[Gast]

Jo danke. Wundert mich nämlich schon etwas gerade weil man ja immer meint, dass java nich so super schnell ist. Warscheinlich einer dieser Mythen die längst überholt sind. :)
Naja das ist immer eine Sache der Programmierung.
Wenn man sich bewusst ist, wie schnell die einzelnen Container sind und noch einen Speichermanager einsetzt, sieht es im Vergleich schon wieder ganz anders aus. Bei dir ist noch verdammt viel Optimierungspotential.

[Gast]

Wieso lasst ihr nicht einfach erstmal einen Profiler laufen um zu sehen wo die hotspots sind, bevor ihr dann die Kristalkugel anwerft und massig nutzlose Arbeit vorschlägt?

[Nasenbaer]

Wieso lasst ihr nicht einfach erstmal einen Profiler laufen um zu sehen wo die hotspots sind, bevor ihr dann die Kristalkugel anwerft und massig nutzlose Arbeit vorschlägt?
Hab ich getan (siehe oben gprof). Hab damit ja auch meinen Hauptrechenzeitschlucker ausfindig machen können. Mittlerweile hab ich keine großen Probleme mehr im Code. Nur ich hab ihn halt immer mehr zusammengeschustert und müsste mal ein Refactoring vornehmen und noch etwas aufräumen. Möglichweise ist der STL priority_queue auch nicht der performanteste. Bei einem großen n rentiert sich dann ein Fibonacci-Heap und ich denke 200*200 = 40'000 ist dann auch schon ein großes n. :)
Gibt das sicher Bibs die besser optimiert sind.
Ich müsste auch noch überprüfen ob ich nicht irgendwo Call-By-Value nutze. Und wenn man dann noch preprocessing mit einsetzt ist der Aufwand wesentlich zu verringern.

Die meisten Infos zu dem Gebiet hab ich von Amit's A* Pages (http://theory.stanford.edu/~amitp/GameProgramming/) und es steckt auf jedenfall noch viel Optimierungpotenzial konzeptioneller (weniger programmiertechnischer) Art in der ganzen Geschichte.

[registrierter Gast]

Jo danke. Wundert mich nämlich schon etwas gerade weil man ja immer meint, dass java nich so super schnell ist. Warscheinlich einer dieser Mythen die längst überholt sind. :)Das hat mich vor anderthalb Jahren - als ich das erste Mal A* programmiert habe - auch gewundert. Habe für C++ und Java je eine Beispielimplementation programmiert und penibel darauf geachtet, dass beide von der Struktur her gleich/ähnlich sind. D.h. gleicher Aufbau der Klassen, des Verfahrens, gleiche Datenstrukturen verwendet, etc.
Als beide Poragmme dann fertig waren, habe ich auch nicht schlecht gestaunt, als Java bei einem Testlauf 40 Sekunden benötigte und C++ 110 Sekunden (keine Compileroptimierungen, gcc) bzw. 45 Sekunden (mit Compileroptimierungen, gcc). :eek: Durch allerlei (teils schon sehr wilder) Optimierungen konnte ich die Zeit des C++ Programmes noch auf 65 Sekunden drücken. Mit Compileroptimierungen lief es dann nur noch 35 Sekunden und hatte Java geschlagen. Der Visual Compiler war dann noch einmal 5 Sekunden schneller.
Das ist dann halt der Vorteil von Java, dass immer optimierte Klassen zur Verfügung stehen und jede gescheit programmierte Applikation von Anfang an relativ schnell ist, während man bei C++ noch drei, vier Tage reinsteckt und es erst dann rennt, dafür aber richtig.
Was aber gleichzeitig auch ein Nachteil von Java ist. Optimierungen sind nur an der Oberfläche möglich.

Hab ich getan (siehe oben gprof). Hab damit ja auch meinen Hauptrechenzeitschlucker ausfindig machen können. Mittlerweile hab ich keine großen Probleme mehr im Code. Nur ich hab ihn halt immer mehr zusammengeschustert und müsste mal ein Refactoring vornehmen und noch etwas aufräumen. Möglichweise ist der STL priority_queue auch nicht der performanteste. Bei einem großen n rentiert sich dann ein Fibonacci-Heap und ich denke 200*200 = 40'000 ist dann auch schon ein großes n. :)
Gibt das sicher Bibs die besser optimiert sind.Wenn du deine Heuristik noch nicht angepasst hast, so liegt dort noch sehr viel Potential.
Zuerst bestimmst du das Minimum von abs(x1-x2) und abs(y1-y2).
Dann addierst du abs(x1-x2) und abs(y1-y2) und ziehst gleichzeitig nochmal das Minimum von den beiden ab (also entweder abs(x1-x2) oder abs(y1-y2) :biggrin:).
Einmal beide Deltas ausrechnen und per if-else die Kosten zurückgeben. Das spart drei Methodenaufrufe und vier Additionen.

Kenne die Priority Queue zwar nicht, aber wenn man dort einen Wert hinzufügt, muss sie doch jedesmal überprüfen, ob der Wert nicht schon einmal darin vorkommt. Da dies bei A* oft nicht der Fall ist, muss die Priority Queue oft unnütz nach dem Wert suchen.
Wie sieht es mit dem Fibonacci-Heap aus? :)

[Nasenbaer]

Nein ich schmeiß es immer alles in den PQueue rein. Einen Priority Queue implementiert man ja im allgemeinen als Heap - der Bequemlichkeit halber als binären Heap. Der Fibonacci-Heap hat halt bessere Laufzeiten für einige Operationen wodurch Dijkstra und A* natürlich profitieren. Aber der Overhead soll wohl für andere Operationen höher sein und deswegen sind größere n's wichtig um Vorteile drauß zu ziehen.

[PH4Real]

Nein ich schmeiß es immer alles in den PQueue rein.

Bist Du Dir sicher, dass das mit deiner PQueue so richtig funktioniert? Bzw. wie sich der Kram verhält, wenn das Element schon drin ist? Ich denke da hat der registrierte Gast schon Recht, dass die Suche durch die Queue mit O( n ) sehr ungünstig sein kann.

Also ich hatte auch mal in Java so ein A* implementiert und dort für das OpenSet eben ein R/B-Tree und für das Closed Set ein HashSet (aus der Java API) benutzt. Jedenfalls habe ich dein Szenario mal kurz nachgebaut (200x200 mit dem Hindernis von Dir) und er braucht knapp 30 ms.

Nachdem ich dann einfach mal das TreeSet durch eine PriorityQueue ersetzt habe (aus der Java API; auch als Heap implementiert) hat sich die Laufzeit auf knapp 500-600ms erhöht. Ein Blick in Profiler zeigt: fast die komplette Laufzeit verbringt er in den equals-Methoden (werden beim Durchlauf durch die Queue aufgerufen) ;).

[Nasenbaer]

Bist Du Dir sicher, dass das mit deiner PQueue so richtig funktioniert? Bzw. wie sich der Kram verhält, wenn das Element schon drin ist? Ich denke da hat der registrierte Gast schon Recht, dass die Suche durch die Queue mit O( n ) sehr ungünstig sein kann.

Also ich hatte auch mal in Java so ein A* implementiert und dort für das OpenSet eben ein R/B-Tree und für das Closed Set ein HashSet (aus der Java API) benutzt. Jedenfalls habe ich dein Szenario mal kurz nachgebaut (200x200 mit dem Hindernis von Dir) und er braucht knapp 30 ms.

Nachdem ich dann einfach mal das TreeSet durch eine PriorityQueue ersetzt habe (aus der Java API; auch als Heap implementiert) hat sich die Laufzeit auf knapp 500-600ms erhöht. Ein Blick in Profiler zeigt: fast die komplette Laufzeit verbringt er in den equals-Methoden (werden beim Durchlauf durch die Queue aufgerufen) ;).
Also ein PQueue darf durchaus mehrmals das gleiche Element enthalten. Da ich immer das Element aus der OPEN-Menge mit den geringsten Gesamtkosten suche bieten sich PQueues halt an. Dort ist das oberste Element halt immer das mit den geringsten Gesamtkosten. Beim entfernen dieses Elementes muss dann aber die Heap-Eigenschaft wieder hergestellt werden. Wie das in der C++ Standdardbibliothek alles von statten geht ist implementationsspezifisch da nicht vorgeschrieben. Also die gesamt Datenstruktur wird nicht vorgeschrieben ist aber wohl in der Regel ein Heap - was für einer weiß ich leider nicht.

Achso Zugriff auf das Element mit niedrigsten Gesamtkosten ist O(1) für (pqueue.top()) aber pqueue.pop() zum entfernen des selbigen weiß ich halt nicht. Aber bei Zeiten werd ich mich auch genauer damit befasssen.
Morgen muss ich erstmal meine Programmierungstechnik/Softwaretechnik mündl. Prüfung machen - hoffentlich kommen Fragen zu A*. *ggg*

[PH4Real]

Also ein PQueue darf durchaus mehrmals das gleiche Element enthalten. Da ich immer das Element aus der OPEN-Menge mit den geringsten Gesamtkosten suche bieten sich PQueues halt an. Dort ist das oberste Element halt immer das mit den geringsten Gesamtkosten. Beim entfernen dieses Elementes muss dann aber die Heap-Eigenschaft wieder hergestellt werden. Wie das in der C++ Standdardbibliothek alles von statten geht ist implementationsspezifisch da nicht vorgeschrieben. Also die gesamt Datenstruktur wird nicht vorgeschrieben ist aber wohl in der Regel ein Heap - was für einer weiß ich leider nicht.
Stimmt, es sollte dann eigentlich egal sein, ob das Element öfters drin ist. Schon läuft das ganze mit 120ms statt mit 600ms :biggrin: (wobei immer noch sehr viel langsamer als ein R/B-Baum mit 30ms). Wahrscheinlich braucht er (minimal) mehr Speicher, aber da hatte ich jetzt nicht Lust zu testen.


Achso Zugriff auf das Element mit niedrigsten Gesamtkosten ist O(1) für (pqueue.top()) aber pqueue.pop() zum entfernen des selbigen weiß ich halt nicht. Aber bei Zeiten werd ich mich auch genauer damit befasssen.


Hmm... in Java (und bestimmt auch in C++) mit log( n ):

Implementation note: this implementation provides O(log( n )) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

log( n ) ist ja auch ok.


Morgen muss ich erstmal meine Programmierungstechnik/Softwaretechnik mündl. Prüfung machen - hoffentlich kommen Fragen zu A*. *ggg*
Denk an Murphy's Law :biggrin:.

[Nasenbaer]

So gleich ist Prüfung aber erstmal noch den Code optimiert. :D
Brauchst jetzt mit optimiertem Code 0,25 Sekunden. Hatte immer pro Knoten ne Listen mit Opterationen mitgeführt, wie der Algo dorthin kam. Dadurch konnte ich dann leicht den Pfad rausholen. Jetzt speicher ich nur noch den Vorgänger wodurch das erstellen der neuen Nodes natürlich viel schneller geht und zuweisungen auch viel fixer sind da weniger kopiert werden muss.
Jetzt müsste ich das Feld halt mal viel größer gestalten um zeitfressende Routinen besser zu identifizieren - aber erstmal Prüfung. *g*

[Senior Sanchez]

Viel Glück bei der Prüfung.

Sag dann aber bescheid, wie es war.

[Nasenbaer]

Bestanden aber hätte mehr erwartet als 2,7. Naja fürs Vordiplom zählt eh nur bestehen. :)
Wer merkt sich schon wie Radixsort funktioniert und wohin man bei R/B Trees die Unausgeglichenheit durch Rotationen hinschiebt. *g*

[Senior Sanchez]

Es gibt wohl gemerkt zwei Radixsort verfahren ;) (Straight-Radix und Radix-Exchange)

Das weiß sogar ich! *g*

Aber Red-Black-Trees finde ich eklig, das bekomme ich dann im nächsten Semester zu hören.

[Nasenbaer]

Es gibt wohl gemerkt zwei Radixsort verfahren ;) (Straight-Radix und Radix-Exchange)

Das weiß sogar ich! *g*

Aber Red-Black-Trees finde ich eklig, das bekomme ich dann im nächsten Semester zu hören.
Dann viel Spaß mit den etlichen Fällen, die man behandeln muss um nach einfügen/löschen aus dem Baum wieder nen R/B Tree zu machen. ;)

[Senior Sanchez]

Ich weiß ;) Darauf freue ich mich schon :/

Ich hatte es sogar mal halbwegs verstanden, wie es funktioniert, aber auch nur halbwegs.

Da hat sich der Herr Sedgewick echt ne Grütze ausgedacht.

[ethrandil]

Da hat sich der Herr Sedgewick echt ne Grütze ausgedacht.
Kann man so nicht sagen ;o)
Das coole am RB-Baum ist einfahc, dass er immer mindestens halb balanciert ist. Cooler Weise geht trotzdem alles in O(log( n )) - mit ein paar Fallunterscheidungen ;). Einfügen hab ich noch im Kopf, aber Löschen hab ich mir nicht gegeben *g*.

- eth

[Senior Sanchez]

Das er Vorteile hat wollte ich ja auch gar nicht bestreiten - ansonsten hätte er keine Daseinsberechtigung ;)

Aber gut, man programmiert ihn vllt einmal, sonst nie mehr.

[PH4Real]

Das er Vorteile hat wollte ich ja auch gar nicht bestreiten - ansonsten hätte er keine Daseinsberechtigung ;)

Aber gut, man programmiert ihn vllt einmal, sonst nie mehr.

Ähm... das ist aber bei allen API Konstrukten so :| . Ich habe doch auch nicht jedesmal Lust einen Hashtable oder einen AVL Tree zu programmieren. Und der R/B hat sehr wohl schon seine Daseinsberechtigung ;):

A Red-Black tree based [...] implementation.

[Senior Sanchez]

Ähm... das ist aber bei allen API Konstrukten so :| . Ich habe doch auch nicht jedesmal Lust einen Hashtable oder einen AVL Tree zu programmieren. Und der R/B hat sehr wohl schon seine Daseinsberechtigung ;):

Ich sehe nicht, dass ich irgendwo etwas anderes behauptet habe, oder?

[PH4Real]

Ich sehe nicht, dass ich irgendwo etwas anderes behauptet habe, oder?

Oh ja, das stimmt ... Du hast geschrieben:

...ansonsten hätte er keine Daseinsberechtigung...

Ich habe gelesen:

...ansonsten hat er keine Daseinsberechtigung...

Okay... das nächste Mal lese ich lieber zweimal :ugly:.

[Senior Sanchez]

Oh ja, das stimmt ... Du hast geschrieben:

Ich habe gelesen:

Okay... das nächste Mal lese ich lieber zweimal :ugly:.

Dachte ich mir schon fast, aber ist kein Problem :)
Ich hätte mich ja tatsächlich irgendwo falsch ausgedrückt haben können.

[Nasenbaer]

Und im Normalfall muss mans ja nicht mal selbst implementieren - außer um es natürlich kennenzulernen - danach greift man vertraut auf robuste und opimierte Implementierungen zurück und freut sich. :)
Soviel Bugs wie sich da einschleichen können, wäre alles andere auch ziemlich leichtsinnig.

[Gast]

Ähm... das ist aber bei allen API Konstrukten so :| . Ich habe doch auch nicht jedesmal Lust einen Hashtable oder einen AVL Tree zu programmieren. Und der R/B hat sehr wohl schon seine Daseinsberechtigung ;):
Nur zur Vollständigkeit: std::set und std::map sind normal auch Red-Black-Trees.