Gerichteter ungewerteter Graph - Alle Wege

Listing

Hallo,

ich suche eine Methode mir mit einer möglichst geringen Laufzeit
alle möglichen Wege, die zwei verschiedene Knoten verbinden ausgeben
zu lassen.

Ich benutze die Boost Bibliothek um den graph zu erzeugen, bin aber
auch für neue Vorschläge offen.

Hier ist mal eine Veranschaulichung wie ich mir das vorgestellt habe:

http://img3.imagebanana.com/view/vqyhiz1/graph.png

Dann kann ich mit einer eigenen Klasse alle Wege direkt auswerten, also kürzester Weg, längster Weg, Weg mit den geringsten Knoten, etc.

Bin leider noch etwas Neu auf dem Gebiet und würde mich bereits über Quellen freuen, mit denen ich mir selbst helfen kann. Google habe ich selbstverständlich schon oft zu dem Thema befragt, aber leider nichts ansprechendes gefunden.

Ich hätte die Idee einen Tiefensuchen-Algorithmus so zu modifizieren, dass alle Wege ausgegeben werden.

Die Tiefe des Graphen ist maximal ~200.

Vielen Dank schonmal für eure Hilfe,
Listing

Fellhuhn

Wenn du die Tiefe des Zielknoten weist, kannst du ja ne simple Tiefensuche nehmen, die abbricht wenn du tiefer als der gesuchte Knoten kommst. In dem Fall geht auch eine Breitensuche gut. Wenn die Tiefe nicht bekannt ist wäre eine Breitensuche oder eine begrenzte Tiefensuche sinnvoller, bei der die Tiefe dann während der Suche bzw. beim ersten Finden ermittelt wird.

Listing

Fellhuhn schrieb:

Wenn du die Tiefe des Zielknoten weist, kannst du ja ne simple Tiefensuche nehmen, die abbricht wenn du tiefer als der gesuchte Knoten kommst. In dem Fall geht auch eine Breitensuche gut. Wenn die Tiefe nicht bekannt ist wäre eine Breitensuche oder eine begrenzte Tiefensuche sinnvoller, bei der die Tiefe dann während der Suche bzw. beim ersten Finden ermittelt wird.

Der Graph wird so generiert, dass die maximale Suchtiefe immer die Tiefe des Graphen sein muss (->Bild).

Also muss ich den Algorithmus dann selber schreiben?
Welchen Algorithmus würdest du mir als Grundlage empfehlen?

Vielen Dank schonmal

Fellhuhn

Im Grunde ist es doch nur folgendes:

function such(vector<Node*> &path, Node *current, Node *target)
  if (target == current) 
    path + current ausgeben
  else
    path += current
    für alle children x
      such(path, current->child[x], target)
    path -= current

Zumindest grob.

Bitte ein Bit

Also ich würde den A* Algorithmus vorschlagen. Man kann zwar damit nicht alle Wege eines Graphen durchlaufen, aber man kann damit effizient den kürzesten Weg bzw. den Weg mit den niedrigsten Kosten bestimmen.

Fellhuhn

Bitte ein Bit schrieb:

Also ich würde den A* Algorithmus vorschlagen. Man kann zwar damit nicht alle Wege eines Graphen durchlaufen, aber man kann damit effizient den kürzesten Weg bzw. den Weg mit den niedrigsten Kosten bestimmen.

Ist hier eher unangebracht.
a) er will alle Wege
b) es fehlt eine sinnvolle Heuristik

Listing

Ja, das von Fellhuhn sieht mir schon sehr vielversprechend aus,
danke dafür

Leider schlage ich mich noch mit boost herum.
Wo kann man da eine Anlaufstelle bekommen, damit ich die Klassen kennen ( und hoffentlich lieben ) lerne?

Hast du den pseudo-code jetzt auf boost ausgelegt (z.B. den child[] array im Node struct) oder muss ich mir doch lieber selbst eine graphen-klasse basteln?

Und was soll ich am Anfang übergeben, einen leeren path, oder schon den Startknoten einfuegen?

Danke schonmal

Fellhuhn

Das ist im Grunde dir überlassen wann du wie den "aktuellen" Knoten in den Pfad reinschreibst. Bei meinem Pseudocode würdest du mit einem leeren Pfad anfangen, da der aktuelle angehängt wird, wenn man sein Ziel erreicht oder eben bevor man zum nächsten geht.
Wenn man durchgehend mit nur einem Pfad (also vector) arbeitet ist es dabei wichtig nach der Bearbeitung der child-Nodes den aktuellen Knoten wieder runterzunehmen, bevor man die Funktion verläßt.

Listing

Tausend Dank, jetzt rennt es

Musste noch ein paar sachen anpassen aber hier nun mein code:

void suche(Path * MyPath, Node *current, Node *target)
{
	if (target->GetId() == current->GetId())
	{
		MyPath->AddNode(target);
		cout << "Weg gefunden!" << endl;
		for(int i = 0; i < MyPath->GetPathLength(); ++i)
		{
			cout << "Knoten " << (i+1) << " = " << (char)MyPath->GetNodeAt(i)->GetId() << " !" << endl;
		}
		MyPath->RemoveLastNode(); 
	}
	else
	{
		MyPath->AddNode(current);
		for(int i = 0; i < current->GetChildAmount(); ++i)
		{
			suche(MyPath, current->GetChild(i), target); //Rekursion
		}
		MyPath->RemoveLastNode(); 
	}
}

Und die Ausgabe zu meinem Beispiel:

Weg gefunden!
Knoten 1 = A !
Knoten 2 = B !
Knoten 3 = C !
Knoten 4 = G !
Weg gefunden!
Knoten 1 = A !
Knoten 2 = B !
Knoten 3 = G !
Weg gefunden!
Knoten 1 = A !
Knoten 2 = C !
Knoten 3 = G !
Weg gefunden!
Knoten 1 = A !
Knoten 2 = D !
Knoten 3 = G !

Bin also wunschlos Glücklich,
vielen Dank an Fellhuhn