längster weg in einem Graph.

Moin,
Ich möchte gerne den längsten Weg in einem Graphen finden, ohne das ein Knotenpunkt mehrfach besucht wird. Alle Knoten haben den gleichen Abstand von einander.
Google & Co. liefert (bei meinen Stichwörtern) zwar sehr viel aber nichts hilft mir wirklich weiter, da ich jetzt auch nicht die große Ahnung von dem Thema hab.
Ich hab einfach gehofft, dass das ein bekanntes Problem ist und das es dafür schon ein Algo. gibt. Nun meine frage ist, ob es solch ein Algo. gibt und wenn ja wie er heißt und wo eine Beschreibung von diesem steht oder es ohne BruteForce es nicht zu lösen ist.

MFG Bernard

CStoll

Wenn alle Knoten den gleichen Abstand haben, ist der längste Weg der Hamilton-Pfad (soweit vorhanden). (und den zu finden, ist afaik NP-vollständig - d.h. es gibt keine wesentlich schnellere Lösung als Brute-Force)

D-U-D-E

Ja, an Brute-Force führ kein Weg vorbei. Du mußt bei jeder Lösung, die du findest, davon ausgehen, daß es einen längeren Weg geben könnte.

crashterpiece

was meinst du mit "alle knoten haben gleichen abstand voneinander"?

liegen die knoten auf einem gitter? oder ist der graph vollständig, d.h. jeder knoten hat eine kante mit jedem anderen knoten?
in so einem fall könnte man vielleicht einfachere lösungsideen finden

oder heisst es schlichtweg, dass die kantenkosten 1 betragen?

Moin,

was meinst du mit "alle knoten haben gleichen Abstand voneinander"?

Soweit ich alles verstanden hab und eine Kante quasi nur eine Verbindung zwischen zwei Knoten darstellt und diese evtl. gewichtet sein kann z.b. durch Länge eines Weges oder Kosten die entstehen, dann meine ich das einfach eine Kante existiert also Kosten keine Rolle spielen.

Meine Idee war mit dem längsten Weg durch meinen Graphen, die Maximale Anzahl an Paaren zu finden die man bilden kann, wenn jeder Knoten mit einem seinem Nachbar Knoten ein Paar bilden kann.

Ich glaube jedenfalls das ich dazu einen Algo. gefunden hab den Blossom-Algorithmus. Soweit ich die ganzen Englischen Scripte verstanden hab sollte dieser für diese Aufgabe geschaffen sein. Die brauchbarste Beschreibung, die jedenfalls für mich so aussieht, steht auf Seite 12 dieses PDF Dokumentes(http://a.baude.net/studium/dokumente/Algorithmen.pdf)

Ich würde mich freuen wenn mir jemand diesen Algo. , wenn dieser überhaupt der Richtige ist für dieses Problem , mir ein bisschen näher bringen könnte, oder wenigsten evtl. eine gute Beschreibung (verständlich für nicht Informatiker) empfehlen könnte ( möglichst online)

MFG

ein längster weg ist nicht unbedingt ein perfektes matching.
z.B hier:

a1  a2
*---*
     \ c
      * -- d 
     /
*---*
b1  b2

ein perfektes matching existiert in dem graph gar nicht ...

du wirst nicht umhin kommen nach brute-force vorzugehen, eventuell kann man sich noch ein paar gute heuristiken ausdenken um schnell lange wege zu erhalten.

Jester

Du willst also eigentlich ein Matching bestimmen? Dann tue auch das und such nicht lange Pfade. Größte Matchings zu finden ist in P, längste Wege ist NP-vollständig. Der Blossom-Algorithmus ist dazu geeignet. Allerdings nicht so richtig einfach zu implementieren.

Ich versuche die Grundidee rüberzubringen. Wir haben nen Graphen G, ein Matching M (also ne Menge von Kanten, die paarweise nicht adjazent sind -> keine zwei kanten aus M hängen am selben knoten). Ein Knoten heißt frei (bezüglich M), wenn er nicht gematcht ist, also zu keiner Kante in M inzident ist. Ein alternierender Pfad (bezüglich M) ist ein Pfad, der abwechselnd Kanten benutzt, die in M sind und welche die's nicht sind. Ein augmentierender Pfad (bezüglich M) ist ein alternierender Pfad, der bei einem freien Knoten beginnt und bei einem anderen freien Knoten endet. Hat man einen bezüglich M augmentierenden Pfad gefunden, kann man mit dem das Matching vergrößern, indem man die Kanten auf dem Pfad, die in M sind rauslöscht und dafür die Kanten vom Pfad, die noch nicht drin waren reintut. Da wir mit nem freien Knoten anfangen und enden wird das Matching dadurch um eins größer.

Was hilft das jetzt für größte Matchings? -- Berge hat bewiesen, dass ein Matching genau dann ein größtes Matching ist, wenn es keinen augmentierenden Pfad gibt. Solange es also noch kein größtes Matching ist kann man einen augmentierenden Pfad finden.

Grober Algorithmus:

Finde augmentierenden Pfad
Wenn gefunden, dann vergrößere mit dem das Matching und gehe zu 1)
keiner gefunden, dann gib das Matching zurück

Allerdings ist das Finden der augmentierenden Pfade ziemlich haarig. Für bipartite Graphen isses einach, für allgemeine Graphen kniffliger, geht aber in O(m) Zeit (m Anzahl der Kanten).

Wenn Du ne Implementierung benötigst würde ich Dir empfehlen auf was vorhandenes zurückzugreifen... boost::graph bietet zum beispiel was.

Ein paar Infos dazu findest Du auch hier: http://i11www.iti.uni-karlsruhe.de/teaching/theses/files/da-irutter-07.pdf -- Kapitel 2 gibt einen Mini-Überblick.

Fischi

@Jester

nein, jetzt hast du dir die ganze arbeit umsonst gemacht.
er will den längsten pfad im graphen haben und er war der meinung, dass ein perfektes matching dasselbe ist.

Jester

Bernard schrieb:

Meine Idee war mit dem längsten Weg durch meinen Graphen, die Maximale Anzahl an Paaren zu finden die man bilden kann, wenn jeder Knoten mit einem seinem Nachbar Knoten ein Paar bilden kann.

Das hier liest sich für mich anders... klingt als wäre der lange Pfad nur ein Hilfsmittel gewesen. Und von perfekten Matchings steht da auch nichts, sondern nur von maximaler Anzahl, also einem größten Matching. Insofern bin ich zuversichtlich, dass es nicht umsonst ist.

Moin, danke schonmal für die Hilfe,
ja ich möchte gerne ein größt mögliches matching finden.
Das Dokument hat mich weiter gebracht dennoch hab ich eine frage zum alternierender Pfad bzw. augmentierenden Pfad. Kann/darf der Pfad Abzweigungen enthalten? Wenn nicht wie findet man dann einen Pfad im Graph den der graphtheoretiker als Beispiel verwendet hat?

MFG

Jester

Bernard schrieb:

Kann/darf der Pfad Abzweigungen enthalten? Wenn nicht wie findet man dann einen Pfad im Graph den der graphtheoretiker als Beispiel verwendet hat?

Nein, ein Pfad hat keine Abzweigungen. Beim Suchen darfst Du natürlich schon verzweigen. Nur der gefundene Pfad ist tatsächlich ein Pfad. Der Trick ist, dass man von allen freien Knoten aus sogenannte alternierende Bäume wachsen lässt (also abwechselnd matching- und nicht-matching-kante). Sobald ein solcher alternierender Baum einen freien Knoten erreicht ist der Pfad von dem Knoten zur Wurzel des Baums ein augmentierender Pfad.

Für bipartite Graphen tut's das schon. Wenn der Graph aber nicht bipartit ist, dann wird's schwieriger... denn dann kann ein Baum sich selber treffen bzw. einen anderen Baum treffen, ohne dass ein augmentierender Pfad gefunden ist. Das passiert bei Kreisen mit ungerader Länge. Das sind dann genau diese Blossoms. Die kann man nun zusammenziehen zu einem Knoten und sich überlegen, dass man einen augmentierenden Pfad im kontrahierten Graphen findet genau dann wenn es im original-Graphen einen gibt. Und dieser Pfad im kontrahierten Graphen lässt sich auch wieder zu einem im Original-Graphen umbauen.

Wenn Du nicht unbedingt ein größtmögliches Matching brauchst ist eine einfache Strategie einfach greedy noch erlaubte Kanten zum Matching hinzuzufügen. Das geht ziemlich flott und man kann sich leicht überlegen, dass das gefundene Matching mindestens halb so groß ist, wie das größte Matching.

Im Fall von graphtheoretiker (dessen graph sehr wohl ein perfektes Matching besitzt) handelt es sich um einen Baum. Da gibt es einen sehr einfachen und schnellen Algorithmus zum Finden von größten Matchings -- schau mal in Kapitel 3 von dem Link von oben.