Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Pfadfindung in einem Graphen (eigentlich: Baum)
TheBrainiac
myCSharp.de - Member

Avatar #avatar-3152.png


Dabei seit:
Beiträge: 795
Herkunft: /dev/null

Themenstarter:

Pfadfindung in einem Graphen (eigentlich: Baum)

beantworten | zitieren | melden

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"
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Schamese,
Zitat
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
private Nachricht | Beiträge des Benutzers
TheBrainiac
myCSharp.de - Member

Avatar #avatar-3152.png


Dabei seit:
Beiträge: 795
Herkunft: /dev/null

Themenstarter:

beantworten | zitieren | melden

Zitat von 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.
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"
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1.361
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
TheBrainiac
myCSharp.de - Member

Avatar #avatar-3152.png


Dabei seit:
Beiträge: 795
Herkunft: /dev/null

Themenstarter:

beantworten | zitieren | melden

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"
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 381

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tarion,

wenn man ohne Probleme die Aufwandsklasse 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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Corpsegrinder,
Zitat
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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Corpsegrinder am .
private Nachricht | Beiträge des Benutzers