Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:25 Mo 09.01.2006 | | Autor: | kuminitu |
Hallo,
habe habe eine kurze frage:
Wenn ich einen Graphen habe und soll einfach alle
Wege von einem Knoten zu einem anderen Knoten
aufschreiben, wie kann man begründen dass man
alle gefunden hat?
Bin über jede hilfe erfreut.
MFG
kuminitu
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:19 Di 10.01.2006 | | Autor: | Frank05 |
> > Wenn ich einen Graphen habe und soll einfach alle
> > Wege von einem Knoten zu einem anderen Knoten
> > aufschreiben, wie kann man begründen dass man
> > alle gefunden hat?
>
>
> Also ein Patentrezept habe ich zwar nicht, aber ich denke,
> daß hier eine
> ![[]](/images/popup.gif) vollständige Backtracking-Suche
> helfen müßte. Die Begründung dafür, daß man alle Wege
> gefunden hat, bestünde dann wohl darin die Korrektheit
> deines Backtracking-Verfahrens nachzuweisen.
Vorsicht mit der Bezeichnung: Vollständig ist Backtracking (bzw. Depth-First-Search) eben gerade nicht. Die Eigenschaft der Vollständigkeit bekommst du hingegen bei der Breitensuche (bzw. Breadth-First-Search).
Warum das unterschieden wird kann man sich ganz einfach vorstellen, wenn man sich überlegt, dass obige Frage den 'Graph' unzureichend charakterisiert:
Was ist wenn der Graph Zyklen hat? Eine DFS könnte dann den gleichen Zyklus immer wieder durchlaufen (nicht zu vergessen, dass dadurch auch die Anzahl der Wege von u nach v unendlich groß werden kann). Dieses Problem existiert natürlich auch bei der BFS.
Was ist wenn der Graph nicht endlich ist? Eine DFS könnte dann in einen unendlich tiefen Teilgraphen laufen, obwohl der Zielknoten darin gar nicht enthalten ist. Mit einer BFS wird der Zielknoten hingegen garantiert gefunden, daher auch die Vollständigkeit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:32 Di 10.01.2006 | | Autor: | mathiash |
Hallo,
diese Mitteilung kommt jetzt zwar mehr oder minder aus dem Bauch heraus,
aber was verstehst Du denn unter DFS, wenn diese Knoten
mehrfach durchlaufen wuerde ? ''Eine anstaendige DFS tut sowas nicht''.
Es geht ja um Wege, bei denen per def. jede Kante hoechstens einmal durchlaufen wird.
Meiner Meinung nach sollte man bei dieser Aufgabe nicht unendliche Graphen
zur Sprache bringen.
Gruss,
Mathias
PS Natuerlich muesst man die Art der Kantenmarkierung bei DFS modifizieren,
um es zu
verwenden, aber das wuerde nichts daran aendern, dass es sich um eine DFS-Strategie handelt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:58 Mi 11.01.2006 | | Autor: | Frank05 |
> diese Mitteilung kommt jetzt zwar mehr oder minder aus dem
> Bauch heraus,
> aber was verstehst Du denn unter DFS, wenn diese Knoten
> mehrfach durchlaufen wuerde ? ''Eine anstaendige DFS tut
> sowas nicht''.
Hängt wohl davon ab, was das Teil berechnen soll. Ich weiß auch nicht, ob es die DFS gibt. Die gängige rekursions-basierte Implementierung würde z.B. nicht terminieren bei Zyklen. Aber meistens verwendet man ja doch noch irgendwelche Zusatzbedingungen.
> Meiner Meinung nach sollte man bei dieser Aufgabe nicht
> unendliche Graphen
> zur Sprache bringen.
Warum nicht? Kann doch nicht schaden etwas weiter zu gehen (und zudem war das ja nicht als Antwort gedacht).
Außerdem kann ich mir solch eine Aufgabe auch bei einem unendlichen Graphen vorstellen, wobei dann die Schwierigkeit darin liegt eine kompakte Notation für die evtl. unendlich vielen Wege zu finden.
|
|
|
| |
|
Hallo und nochmal guten Morgen,
Karls Vorschlag funktioniert. Ein anderer ist, es ueber ein Branch & Bound -Verfahren
zu machen. ZB triffst Du fuer jede Kante die Entscheidung, ob sie im Pfad sein soll oder nicht, und so bekommst Du einen binaeen Baum der Tiefe = Anzahl der Kanten.
Dabei besteht Hoffnung, viele Teilb"aume schon fruehzeitig abzuschneiden, zB weil
aus der momentanen Entscheidung, gewisse Kanten nicht zu nehmen, resultiert, dass der
eine Knoten nicht mehr vom anderen aus erreichbar ist.
Denkbar waere auch, Kuerzeste-Wege-Algorithmen so zu modifizieren, dass sie
die kuerzesten Wege der laenge mindestens L ausgeben.
Weiterhin kann man alternativ direkt einen Ansatz ueber dynamische Programmierung versuchen - wenn man das Problem fuer alle Knotenpaare loesen moechte, zB.
Gruss,
Mathias
|
|
|
|
![[willkommenir]](/images/smileys/willkommenir.png "[willkommenir]")
