Archiv verlassen und diese Seite im Standarddesign anzeigen : Graphentheoretische Frage - Algorithmus gesucht
Senior Sanchez
2011-05-02, 20:10:09
Hallo miteinander,
Ich beschäftige mich gerade mit einer Anwendung der Graphentheorie und bin dabei auf ein Problem gestoßen, für das ich zwar eine Lösung habe, mit der ich aber nicht ganz zufrieden bin.
Ich habe eine Menge von Knoten, die über ungerichtete, positiv gewichtete Kanten verbunden sind. Dabei existieren zwischen Knoten auch mehrere Pfade. Dies möchte ich aber nicht, sondern stattdessen dass es jeweils nur einen Pfad gibt, der auch möglichst kurz sein soll. Das klingt erstmal nach einem minimalen Spannbaum.
Es kann aber im Graph bei einigen Kanten Zyklen geben (und die wird es auch geben, was korrekt ist), die somit die Bedingung eines einzelnen Pfades verletzen, wodurch kein Spannbaum möglich ist. Im Idealfall sollen die Knoten wie eine Art Perlenschnur miteinander verbunden werden, wobei jede Kante nur einmal besucht werden soll und der Gesamtpfad eben möglichst kurz sein soll. Das wiederum klingt in Richtung TSP, wobei ich aber teilweise das Problem habe, dass ich nicht genau einen Start- und einen Endknoten ausmachen kann. Inwiefern das für aktuelle TSP-Verfahren relevant ist, weiß ich nicht.
Meine momentane Variante ist, dass ich den Graphen mit all seinen Knoten betrachte und zuerst die Kanten absteigend nach ihrer Länge sortiere. Nun werden schrittweise die Kanten aus dem Graph entfernt, wobei jedes Mal geprüft wird, ob die Erreichbarkeit der Knoten weiterhin besteht. Wenn ja, bleibt die Kanten draußen, wenn nicht wird sie wieder eingefügt. Das führt zu einem ganz guten Ergebnis, aber da ich nicht leicht überprüfen kann, ob eine Kante für irgendeinen Pfad mehrmals besucht werden muss, bekomme ich nicht immer das gewünschte Ergebnis.
Habt ihr irgendeine Idee, was ich da machen könnte?
Baalzamon
2011-05-02, 20:24:22
Hmmm... weiss nicht ob ich dich richtig verstanden habe, aber das klingt doch stark nach dem Hamiltonkreis (http://de.wikipedia.org/wiki/Hamiltonkreisproblem) (von dem der TSP ein Spezialfall ist).
Vielleicht hilfts ja? =)
Senior Sanchez
2011-05-02, 20:28:49
Danke für den Link, aber das ist es denke ich nicht.
Erstens habe ich keinen kompletten Zyklus, dass heißt Start- und Endknoten sind nicht zwangsläufig miteinander verbunden. Zweitens habe ich zwischendrin mal Zyklen drin, sodass ein Knoten dann mehrfach besucht wird, z.B. so etwas:
A -> B -> C -> D -> C -> B
D -> E -> F
Baalzamon
2011-05-02, 20:41:04
Danke für den Link, aber das ist es denke ich nicht.
Erstens habe ich keinen kompletten Zyklus, dass heißt Start- und Endknoten sind nicht zwangsläufig miteinander verbunden. Zweitens habe ich zwischendrin mal Zyklen drin, sodass ein Knoten dann mehrfach besucht wird, z.B. so etwas:
A -> B -> C -> D -> C -> B
D -> E -> F
OK, ich habe mich durch die Perlenschnur irreleiten lassen. ;)
Wenn du genau alle Kanten einmal haben möchtest dann wäre das ja ein Eulerkreis (http://de.wikipedia.org/wiki/Eulerkreisproblem), aber ich schätze das passt hier auch noch nicht wirklich, da du ja auch die kürzesten Wege mit drin haben möchtest.... hmmm...
Sorry, da fällt mir auch erstmal auf die schnelle nix Gescheites ein. ;(
Ist dein Problem das hier: http://de.wikipedia.org/wiki/Steinerbaumproblem ?
Deine Formulierung ist da nicht ganz nachvollziebar...
Senior Sanchez
2011-05-02, 21:13:47
Ist dein Problem das hier: http://de.wikipedia.org/wiki/Steinerbaumproblem ?
Deine Formulierung ist da nicht ganz nachvollziebar...
Es geht in die Richtung, aber ich bin mir unsicher, ob ich damit auch teilweise Zyklen abbilden kann.
Du hast aber Recht, dass es schwer beschreibbar ist. Ich habe mal eine Beispielgrafik angehängt, bei der der schwarze Pfad der gewünschte Pfad ist, der eine Teilmenge der gesamten Kantenmenge ist.
du suchst einen kürzesten Hamiltonweg, da gibt es viele verschiedene Heuristiken
wenn du Interesse hast, schaue ich mal nach.
Senior Sanchez
2011-05-02, 22:14:03
du suchst einen kürzesten Hamiltonweg, da gibt es viele verschiedene Heuristiken
Kann ein Hamiltonweg auch ohne Zyklen sein? Das wäre wichtig, da zum Beispiel auch die Kanten B-I und A-I mal fehlen können. Dann gäbe es da keinen Kreis mehr. Was passiert wenn nicht alle Knoten verbunden sind und es somit im Grunde zwei Graphen gibt? Das ließe sich zwar auch gesondert herausfinden, aber vielleicht fängt der Algorithmus das schon ab?
Ohne jetzt überhaupt die Angabe genauers gelesen zu haben :frown:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Baalzamon
2011-05-02, 23:09:10
Ohne jetzt überhaupt die Angabe genauers gelesen zu haben :frown:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Dann lese es doch bitte und überdenke was du gepostet hast.
:facepalm:
Senior Sanchez
2011-05-02, 23:19:01
Ohne jetzt überhaupt die Angabe genauers gelesen zu haben :frown:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Wäre das die Lösung hätte ich sie wohl schon längst gefunden und hätte hier nicht gepostet. ;) Das schließt natürlich nicht aus, dass es trotzdem eine abgefahrene Lösung gibt, die darauf basiert. Ich habe jedenfalls keine gefunden.
Dann lese es doch bitte und überdenke was du gepostet hast.
:facepalm:
procrastinate now - panic later :biggrin:
Edit:
Nach durchlesen der Angabe, würde ich auch das sagen was pest gesagt hat.
AlecWhite
2011-05-02, 23:38:18
Ganz ehrlich, ich weiß noch nicht genau was das Problem ist...
Was ist nun genau gesucht? Wie schauen die Nebenbedingungen kurz und bündig aus?
Kann ein Hamiltonweg auch ohne Zyklen sein? Das wäre wichtig, da zum Beispiel auch die Kanten B-I und A-I mal fehlen können. Dann gäbe es da keinen Kreis mehr. Was passiert wenn nicht alle Knoten verbunden sind und es somit im Grunde zwei Graphen gibt? Das ließe sich zwar auch gesondert herausfinden, aber vielleicht fängt der Algorithmus das schon ab?
Wir müssen schon die selbe Terminologie verwenden :)
Ein Hamiltonweg ist ein Weg der alle Knoten eines Graphen enthält.
Ein Hamiltonkreis ist ein Hamiltonweg bei dem Start und Endknoten identisch sind. Jeder Kreis ist also auch ein Zyklus.
Was meinst du mit "nicht alle Knoten verbunden"?
Ein (ungerichteter) Graph ist zusammenhängend wenn "jeder Knoten von jedem anderen über einen Weg erreichbar ist".
Wenn der ungerichtete Graph nicht zusammenhängend ist ex. kein Hamiltonweg. Dann müsstest du zu erst die Zusammenhangskomponenten herausfinden (Tiefensuche).
Senior Sanchez
2011-05-03, 07:41:16
Wir müssen schon die selbe Terminologie verwenden :)
Ein Hamiltonweg ist ein Weg der alle Knoten eines Graphen enthält.
Ein Hamiltonkreis ist ein Hamiltonweg bei dem Start und Endknoten identisch sind. Jeder Kreis ist also auch ein Zyklus.
Okay, dann brauch ich den Hamiltonweg. :) Aus der Definition, wie du sie jetzt gegeben hast, schlussfolgere ich auch mal, dass auch Zyklen in einem Teilgraph enthalten sein dürfen, oder?
Was meinst du mit "nicht alle Knoten verbunden"?
Ein (ungerichteter) Graph ist zusammenhängend wenn "jeder Knoten von jedem anderen über einen Weg erreichbar ist".
Wenn der ungerichtete Graph nicht zusammenhängend ist ex. kein Hamiltonweg. Dann müsstest du zu erst die Zusammenhangskomponenten herausfinden (Tiefensuche).
Ja, genau so meinte ich das. Dann muss ich das vorher überprüfen, sollte aber relativ einfach machbar sein.
Hast du mal einen Link zu den von dir angesprochenen, guten Heuristiken?
Senior Sanchez
2011-05-03, 07:43:26
Ganz ehrlich, ich weiß noch nicht genau was das Problem ist...
Was ist nun genau gesucht? Wie schauen die Nebenbedingungen kurz und bündig aus?
- ich habe mehrere Knoten, die über ungerichtete, positiv gewichtete Knoten verbunden sind
- Alle Knoten sollen über eine Teilmenge der Kantenmenge miteinander verbunden werden
- dabei soll es zu jedem Knoten nur einen Pfad geben, wobei dieser minimal sein soll
- jeder Knoten soll nur einmal besucht werden
- Zyklen innerhalb des Graphen sind möglich
- es gibt keinen eindeutigen Start- oder Zielknoten
- ich habe mehrere Knoten, die über ungerichtete, positiv gewichtete Knoten verbunden sind
- Alle Knoten sollen über eine Teilmenge der Kantenmenge miteinander verbunden werden
- dabei soll es zu jedem Knoten nur einen Pfad geben, wobei dieser minimal sein soll
- (A) jeder Knoten soll nur einmal besucht werden
- (B) Zyklen innerhalb des Graphen sind möglich
- es gibt keinen eindeutigen Start- oder Zielknoten
Widersprechen sich die Bedingungen A + B nicht?
Edit: :frown:
Wenn du Bedingung A rausnimmst, dann wäre es glaube ich folgendes Problem:
http://de.wikipedia.org/wiki/Briefträgerproblem
Sorry, aber ich glaube, das hier könnte dir helfen:
"Falls es im praktischen Planungsproblem zulässig ist, Orte mehrfach zu besuchen, lässt sich das symmetrische TSP auf das metrische TSP reduzieren. Dazu wird das Rundreiseproblem auf dem sogenannten Distanzgraphen betrachtet. "
Quelle: http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
Senior Sanchez@Work
2011-05-03, 13:09:20
Widersprechen sich die Bedingungen A + B nicht?
Wenn du Bedingung A rausnimmst, dann wäre es glaube ich folgendes Problem:
http://de.wikipedia.org/wiki/Briefträgerproblem
Da hast du Recht und dem bin ich mir bewusst.
Sagen wir es mal so: Zyklen sind erlaubt, aber sonst wird jeder Knoten nur ein einziges Mal besucht.
AlecWhite
2011-05-04, 10:34:31
Ok, also Knoten dürfen mehrfach besucht werden, sollte aber nachmöglichkeit nur einmal besucht werden. Primäres Ziel ist der kürzeste Weg zwischen den Knoten.
Klingt für mich nach einer typischen Aufgabe für einen Ameisenalgorithmus.
DocEW
2011-05-08, 15:42:58
Ich komme mit deinen Angaben noch nicht so ganz zurecht...
- dabei soll es zu jedem Knoten nur einen Pfad geben, wobei dieser minimal sein soll
Heißt das "von jedem zu jedem anderen Knoten"?
- jeder Knoten soll nur einmal besucht werden
Was heißt denn "besucht"? Knotengrad zwei?
- Zyklen innerhalb des Graphen sind möglich
Bei jedem Knoten des Zyklus gibt es aber doch mindestens zwei Pfade zu allen anderen Knoten des Zyklus.
Das widerspricht deiner Forderung oben. Kannst du das noch präziser ausdrücken?
Vielleicht hilft es auch, wenn du mal die Anwendung beschreibst. :)
Senior Sanchez
2011-05-08, 20:02:31
Ich komme mit deinen Angaben noch nicht so ganz zurecht...
Heißt das "von jedem zu jedem anderen Knoten"?
Meinst du jetzt eine Direktverbindung zwischen allen Knoten? Das ist nicht gemeint. Ich meine einfach, dass die Erreichbarkeit, wie sie vor dem entfernen von Kanten besteht, weiterhin erhalten bleibt. Existiert also irgendeine Verbindung von Knoten D zu G (siehe Beispiel oben), dann soll nach dem Entfernen von Kanten der Knoten G immer noch von D erreichbar sein.
Was heißt denn "besucht"? Knotengrad zwei?
Ja, im Grunde heißt es das. Allerdings gibt es eben mal Zyklen und da sind auch höhere Grade möglich.
Bei jedem Knoten des Zyklus gibt es aber doch mindestens zwei Pfade zu allen anderen Knoten des Zyklus.
Das widerspricht deiner Forderung oben. Kannst du das noch präziser ausdrücken?
Du darfst den Knotengrad von 2 nicht als unumstößlich betrachten. Nach Möglichkeit soll der gewährleistet werden, aber es gibt eben Situationen wo das nicht geht. In so einem Fall sind dann auch höhere Grade möglich.
Vielleicht hilft es auch, wenn du mal die Anwendung beschreibst. :)
Darf ich leider nicht. ;)
Ein Hamiltonpfad ist's ja auch nicht, weil bei diesem jeder Knoten genau einmal besucht werden darf.
Wie wärs mit einem TSP, bei dem Start- und Endpunkt nicht gleich sein müssen (zB am Ende die längste Kante löschen..?)
Ich würd mir mal genau überlegen was ich will und versuchen das zu definieren bzw. diesen Begriff dann in Publikationen (Papers/Bücher) zu finden. Bevor du das nicht weist wirds schwierig sein einen Algorithmus dafür zu finden.
Sonst bleibt dir noch übrig, einen Algorithmus für ein generelleres Problem zu nehmen und anzupassen.
Noch eine Ergänzung:
Das mit den "manchmal erlaubten Zyklen" klingt komisch. Bist du dir sicher dass Zyklen nicht generell erlaubt sind (wie auch im TSP)? Darf der Weg zur Vermeidung eines Zyklus beliebig schlecht sein?
Tipp: Frag mal auf mathoverflow.com
- ich habe mehrere Knoten, die über ungerichtete, positiv gewichtete Knoten verbunden sind
(A) Alle Knoten sollen über eine Teilmenge der Kantenmenge miteinander verbunden werden
(B) dabei soll es zu jedem Knoten nur einen Pfad geben, wobei dieser minimal sein soll
(C) jeder Knoten soll nur einmal besucht werden
(D) Zyklen innerhalb des Graphen sind möglich
(E) es gibt keinen eindeutigen Start- oder Zielknoten
Ist das ueberhaupt wohldefiniert?
Sei G das Viereck mit Knoten 0,1,2,3 und ungerichteten Kanten {0,1}, {1,2}, {2,3}, {3,0} + alle Schlingen/Schleifen {i,i}, wobei jede Kante Gewicht 1 hat. Dann ist G die einzige Loesung, da:
Kuerzester Weg von i nach j ist die Kante {i,j}, also muessen alle Kanten verwendet werden, womit aber stets von i nach j mindestens zwei (einfache) Pfade existieren.
Wenn ich das richtig verstehe, laeuft das auf All-Pairs Shortest-Distance rauslaufen, d.h., wegen der positiven Gewichte je einmal Dijkstra pro Knoten,
wobei du dir wohl die jeweiligen Kantenrelation merken musst, wenn du eindeutige kuerzeste Pfade haben willst.
Alles aber ohne Garantie.
Senior Sanchez
2011-05-10, 23:05:49
Das diese Aufgabe einige Stolperstellen hat, dem bin ich mir überaus bewusst und ansonsten hätte ich sie auch nicht gestellt. ;) Dummerweise habe ich eben bisher keine Problemdefinition gefunden, die mit meinem Problem übereinstimmt, was die Suche nach Verfahren auch sehr erschwert.
Zyklen sind schon erlaubt. Nach heutiger Betrachtung ist ein Zyklus bei mir aber erst erlaubt, wenn er eine bestimmte Länge überschreitet. Eine Kante, die einen Knoten mit sich selbst verbindet, ist dagegen nicht erlaubt.
Vielen Dank auf jeden Fall schon mal für die rege Beteiligung. :)
DocEW
2011-05-11, 00:33:54
Also, den Trade-off zwischen Zyklenbildung und kürzesten Wegen muss man glaube ich noch näher spezifizieren:
Ein Spannbaum ist ja ansonsten eine Lösung, oder? Warum magst du den Spannbaum nicht? Weil die Wege zwischen den Knoten "zu lang" sind, also nicht den kürzesten Wegen entsprechen?
Der ursprüngliche Graph, aus dem man so lange Kanten heraus nimmt, wie sich kein kürzester Weg ändert, ist auch eine Lösung, oder? Warum magst du diese Lösung nicht? :)
Eine Kante herauszunehmen vermindert potentiell die Anzahl der Zyklen, aber verlängert kürzeste Wege zwischen Paaren von Knoten. Wie soll das gegeneinander abgewogen werden?
Außerdem ist mir noch aufgefallen, dass ich aus dem ersten Post diesen Teil
Das führt zu einem ganz guten Ergebnis, aber da ich nicht leicht überprüfen kann, ob eine Kante für irgendeinen Pfad mehrmals besucht werden muss, bekomme ich nicht immer das gewünschte Ergebnis. nicht verstehe. :)
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.