Hi @ All.
Ich habe folgende Klasse (vereinfacht)
class Node {
string Name;
Node[] Nodes;
}
Nun muss ich eine Methode implementieren, die mir den Pfad zwischen zwei Nodes berechnet:
Node[] FindPath(Node start, Node end) {
}
Wie kann ich das bewerkstelligen? Ist da ein Pfadfinder-Algorithmus (A*) angebracht? Oder geht es einfacher?
Gruß, Christian.
Hallo Schamese,
Ist da ein Pfadfinder-Algorithmus (A*) angebracht?
wenn es nicht gerade um winzige oder ganz spezielle Graphen geht, ist natürlich ein normaler Pfadfinder-Algorithmus wie A* angebracht.
herbivore
wenn es nicht gerade um winzige oder ganz spezielle Graphen geht...
Der Graph hat eine maximale Tiefe von 25 und ist ähnlich wie ein TreeNode.
Ist das winzig oder speziell? 🤔
Bzw. was wäre denn dann angebracht?
Gruß, Christian.
Hi Schamese,
wenn er ähnlich zu einem TreeNode ist, dann könnte das ganze schon ein Baum sein. Und das ist ein spezieller Graph. Da er Zyklenfrei und zusammenhängend ist, gibt es zwischen zwei Knoten genau einen Pfad.
Und den bekommst du, wenn du von beiden Knoten aus aufwärts zur Wurzel hin immer zu den Eltern hinläufst. Irgendwann stellt sich raus, dass in ihrer Vorfahrenlinie (Eltern, ureltern, ...) die selben Personen drin sind (spätestens bei der Wurzel).
Im Grunde doch so, wie man selbst im Dateisystem navigieren würde.
Man ist in "c:\foo\bar\test\knoten.txt" und möchte zu "c:\foo\knacks\baz.mp3"
Dann geh ich solange aufwärts bis ich bei "c:\foo" bin (dem längsten Teilpfad zu beiden Knoten ausgehend von der Wurzel) und navigier wieder abwärts zum Ziel.
Hierfür ist natürlich ein "Vorgänger"/"Eltern"-Knoten hilfreich.
Entweder nimmst du das direkt in deine Datenstrukturen mit auf, oder du ermittelst es vorher für alle Knoten, sollte ebenfalls in O(n) gehen.
beste Grüße
zommi
Mh. Dachte ich mir.
Habs jetzt so gelöst (Rück- / Aufwärts). Wollte es zwar ohne Eltern-Property hinkriegen, also (Vor- / Abwärts), aber so ist wahrscheinlich performanter.
Danke & Gruß, Christian.
Bei der Größe darf man noch nicht an Performance denken, daran kannst du denken wenn es langsam wird. Dann gibt es auch ganz andere Ansätze das zu Lösen. (Indizierung, Bin. Suchbäume, ...)
Die Parent Property ist dennoch nicht verkehrt in Bäumen und macht vieles einfacher. Also durchaus sinnvoll.
Hallo Tarion,
wenn man ohne Probleme die _Aufwandsklass_e reduzieren kann (hier von O(n) auf O(log n)) sollte man das immer sofort tun. Das ist kein Widerspruch zu "premature optimization is the root of all evil".
herbivore
Hi,
wenn es sich um einen ungerichteten Graphen handelt, dann sollte doch eh jeder Knoten alle seine Kanten kennen, oder? Dann kannst du das doch ganz einfach mit Backtracking lösen. Ich kenne zwar die Struktur deines Graphen nicht, aber in einem ungerichteten Graphen gibt es ja keine Parents und Children, sondern eben nur Knoten und Kanten.
Hallo Corpsegrinder,
Ich kenne zwar die Struktur deines Graphen nicht
es wurde mitterweile gesagt, dass es sich um einen Baum handelt. Diese Tatsache hat es sogar in den Titel geschafft. Und für Bäume wurde schon eine optimale Lösung angegeben.
Für "echte" Graphen wäre jedoch einfaches Backtracking ein sehr schlechter Vorschlag. Da gibt es deutlich besseres. Wurde auch schon genannt.
herbivore
ich wollte auch nicht sagen, dass es die beste ist, sindern eine einfache, in der man keine parent verbindung braucht. außerdem hieß es ähnlich einer treenode weshalb ich mich noch einmal erkundigen wollte.