Laden...

Pfadfindung in einem Graphen (eigentlich: Baum)

Erstellt von TheBrainiac vor 13 Jahren Letzter Beitrag vor 13 Jahren 2.242 Views
TheBrainiac Themenstarter:in
795 Beiträge seit 2006
vor 13 Jahren
Pfadfindung in einem Graphen (eigentlich: Baum)

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.

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`
49.485 Beiträge seit 2005
vor 13 Jahren

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

TheBrainiac Themenstarter:in
795 Beiträge seit 2006
vor 13 Jahren

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.

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`
1.361 Beiträge seit 2007
vor 13 Jahren

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

TheBrainiac Themenstarter:in
795 Beiträge seit 2006
vor 13 Jahren

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.

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`
T
381 Beiträge seit 2009
vor 13 Jahren

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.

49.485 Beiträge seit 2005
vor 13 Jahren

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

C
401 Beiträge seit 2007
vor 13 Jahren

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.

49.485 Beiträge seit 2005
vor 13 Jahren

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

C
401 Beiträge seit 2007
vor 13 Jahren

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.