Verbindungen in Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich stehe vor dem folgenden Problem, ich habe einen ungewichteten (bzw. alle Kanten mit 1 gewichtet), ungerichteten Graphen und suche nun alle Verbindungen von Knoten x nach Knoten y, die über eine maximale Länge von z Knoten führen.
Gibt es einen anderen Weg / Algorithmus als sozusagen rekursiv die nachfolgenden Knoten von x, dann die jeweils nachfolgenden Knoten dieser Nachfolger, usw. zu überprüfen, ob der Knoten y zu dieser Menge zählt? (Breitensuche)
Vielen Dank für Eure Ideen, Anregungen oder Hinweise, wo ich weitere Informationen dazu finden könnte, es geht mir vielmehr auch um erste Anregungen und keine Komplettlösungen oder auch einfach ein klares "es geht nicht anders" 
Nach etwas weiterer Recherche entspricht meine Fragestellung in etwa der Aufgabe 2 des folgenden PDFs, die nahelegt, dass es wohl doch andere Verfahren gibt, doch welche? ![[]](/images/popup.gif) http://www.math.tu-bs.de/~fekete/Einf2/ueb02.pdf
Viele Grüße, Lars
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Mittag,
fuer das von Dir geschilderte Problem, alle Pfade der vorg. Hoechstlaenge zu berechnen, geht es
nicht besser. Vorsicht: Wenn Du alle solche Pfade generieren moechtest, so sind dies im allgemeinen
exponentiell viele (in der Groesse des Graphen), und Du kannst nicht einfach nur BSF anschmeissen, sondern musst es
so tun, dass auch wirklich alle Pfade gefunden werden (d.h. jeder Knoten hat eine4 Liste von Pointern auf Vorgaengerknoten auf
einem Pfad der Laenge hoechstens z zur Wurzel, die anfangs leer ist und im Laufe von BFS gefuellt wird).
Die Aufgaben auf dem von Dir beigefuegten Blatt beziehen sich mE hingegen auf das Problem, einen (nicht alle)
kuerzesten Wege von x nach y oder so zu berechnen, und dafuer gibt es dann in der Tat wesentlich effizientere Algorithmen
(Dijkstra-Algorithmus zum Beispiel).
Gruss,
Mathias
|
|
|
| |
|
Hallo Mathias,
vielen Dank für Deine schnelle Antwort ... ich denke auch, ich werde mich dann vorerst auf BFS beschränken.
Die Algorithmen von Dijkstra, Ford, Floyd & Co habe ich in den letzten Tagen durchgearbeitet, aber wie Du schon sagst, sie finden eben nur einen kürzesten Pfad.
Ich hatte aufgrund der Aufgabenstellung mit Preprocessing und Queries vermutet, dass es vielleicht doch andere Algorithmen geben könnte, denn so großartig Preprocessing, usw. findet bei BFS eigentlich ja nicht statt, außer mit Preprocessing sind Sachen wie Matrizeninitalisierung, usw. gemeint ... zumal in Aufgabenstellung d) aber ja auch nach Möglichkeiten mit und ohne Preprocessing gefragt ist und nach der Ermittlung der Pfade mit "vorab" ermittelteten Daten.
Also wenn noch jemand andere Ideen hat, wäre ich dafür sehr zu haben
Viele Grüße, Lars
|
|
|
| |
|
Hallo Ihr beiden,
also spontan gesagt, wenn man nicht gerade alle Pfade aufzählen will, braucht man nicht unbedingt exponentiell viel Zeit. Der Trick dabei ist natürlich, dass man die Pfade nur indirekt notiert. Dazu kann man BFS, bzw. eine Variante von Dijkstra nehmen. Beides ist aber im Fall von Kantengewicht 1 äquivalent.
Man geht einfach folgendermaßen vor: Starte mit Knoten $x$. Sei $X$ die Menge der aktuell zu betrachtenden Kanten und damit [mm] $X=\{x\}$. [/mm] Nur wollen wir solange es ein [mm] $v\in [/mm] X$ gibt folgendes machen: Entferne $v$ aus $X$ und für jede Kante [mm] $(v,w)\in [/mm] E$ addiere $v$ zu den möglichen Nachfolgern von $w$ und füge $w$ in $X$ hinzu.
Dann hat man die Pfade im Endeffekt indirekt als Nachfolger gegeben. Gestartet in Knoten $y$ kann man sich so nach $x$ "hangeln". Allerdings bietet dies nur eine Teillösung, denn die Längenbeschränkung kann man sozusagen nicht gleichzeitig darauf werfen, dass müsste man dann in einem weiteren Schritt machen. Laufzeittechnisch sollte das per DFS kein Problem geben, da man dann amortisiert nicht mehr Zeit verbraucht als man hätte wenn man diese Einschränkung gleich miteinbindet (jedenfalls soweit wie ich das sehe).
Die eigentliche Laufzeit um die Pfade indirekt aufzubauen ist dann [mm] $O(|E|)\subset O(|V|^2)$.
[/mm]
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:12 Fr 10.03.2006 | | Autor: | mathiash |
Hallo und guten Morgen Matthias und Eisbär,
Matthias, Du baust also via Dijkstra sowas auf wie fuer jeden Knoten eine Liste von Pointern auf Knoten, und
wenn es von u nach v einen Pointer gibt, heisst das, dass es einen Pfad der Laenge hoechstens z (oder was das war)
von u zur Quelle (hieß sie s ?) gibt, der als erste Kante die von u nach v nimmt.
Das geht natuerlich, wenn man sich mit einer solchen Repräsentation begnügt.
Ich denke, damit können wir die Frage auf grün schalten, oder ?
Viele Grüße,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:32 Mo 13.03.2006 | | Autor: | kretschmer |
Hallo mathiash und Eisbär,
um mathiashs Frage zu beantworten: Ja - so dachte ich mir das. Wenn man alle aufzählen will, ist es nicht unbedingt das geschickteste, weil man dann ja direkt DFS oder sowas machen muss, was man auch gleich auf dem ursprünglichen Graphen hätte machen können.
--
Gruss
Matthias
|
|
|
| |
|
Ich denke auch, ich werde mich damit zufrieden geben und das erstmal auf mich einwirken lassen :)
Vielen Dank Euch beiden.
Gruß, Lars
|
|
|
|
