Matching-Probleme

haus-sonne schrieb:

tut mir leid, wenn es etwas unverständlich ist!
also ich habe das Straßennetz als Graphen dargestellt und suche jetzt die kürzeste route für die müllabfuhr, also einen eulerkreis (und nicht etwa einen hamilton-pfad wie beim kaufmann).
Doch das geht ja nur, wenn alle knotengrade gerade sind und um das zu erreichen brauche ich angeblcih den blossom-algorithmus.
doch dessen bin ich mir nicht sicher und verstehen tu ich ihn erst recht nicht

Wenn du dein eigenes Problem nicht verstehst, hilft es manchmal, zu versuchen, es genau zu erklären. Also erkläre mal: Was ist dein "reale-Welt-Problem" (Müllabfuhr, Strassen, Mülltonnen, welchen Weg willst du finden etc). Und dann erkläre mal, wie du deine reale Welt mit einem Graphen beschreibst und welches Problem du für deinen Graphen lösen willst.

Wenn du soweit bist, können wir mal schauen, ob google und wikipedia und eine Lösung für dein Problem ausspucken

Jester

Hallo,

das ist an sich schon das richtige Vorgehen. Damit ein Eulerkreis existiert müssen alle Knoten geraden Grad haben. Ist das nicht der Fall, kann man diese Eigenschaft herstellen, indem man sozusagen zwischendrin von einem ungeraden Knoten zu einem anderen fährt. Man fügt also einfach eine Kante zwischen diesen beiden ein. Damit der Weg nun insgesamt so kurz wie möglich wird, sucht man also eine möglichst kurze Menge von Kanten, nach deren Hinzunahme zum Graphen alle Knoten geraden Grad haben. Unter einigen vernünftigen Annahmen (alle Kantengewichte sind positiv und die Dreiecksungleichung gilt) kann man zeigen, dass die beste Hinzunahme ein Matching mit minimalem Gewicht ist. Das Matching-Problem ist also schonmal die richtige Adresse.

Der ursprüngliche Blossom-Algorithmus arbeitet aber eigentlich für das ungewichtete Matching-Problem. Um den auf gewichtete Matchings zu verallgemeiner braucht man noch das sogenannte primal-duale Schema, was auf die Theorie der linearen Optimierung zurückgeht. Dazu gibt es einiges an schönen Büchern. Etwa Kombinatorische Optimierung | ISBN: 9783540769187.

Allerdings geht beides meiner Meinung nach weit über Schulniveau hinaus. Daher nochmal die konkrete Frage, was willst Du machen? Eine Implementierung? Dann benutze eine fertige Implementierung, etwa die von LEDA oder die von Lemon http://lemon.cs.elte.hu/trac/lemon.

Oder sollst/willst Du vielleicht eher konzeptionell erklären, warum man ein Matching braucht und wieso genau das das entsprechende Problem löst? Dann schau Dir an was ein Matching ist und versuche zu beweisen, dass es das richtige tut und verwende dass es eine gute Lösung dafür gibt nur als Blackbox.

Ansonsten kann ich Dir nur davon abraten Dich für eine schulische Arbeit mit den Innereien dieses Algorithmus zu beschäftigen. Vermutlich kommt da ein ziemlicher Bockmist raus, außerdem hat der Lehrer davon vermutlich auch keine Ahnung.

Damit ein Eulerkreis existiert müssen alle Knoten geraden Grad haben. Ist das nicht der Fall, kann man diese Eigenschaft herstellen, indem man sozusagen zwischendrin von einem ungeraden Knoten zu einem anderen fährt. Man fügt also einfach eine Kante zwischen diesen beiden ein. Damit der Weg nun insgesamt so kurz wie möglich wird, sucht man also eine möglichst kurze Menge von Kanten, nach deren Hinzunahme zum Graphen alle Knoten geraden Grad haben.

Genau das will ich machen!

Der ursprüngliche Blossom-Algorithmus arbeitet aber eigentlich für das ungewichtete Matching-Problem.

Kann ich den also gar nicht verwenden? Das ist der Blossom-Algorithmus, den ich gefunden habe http://a.baude.net/studium/dokumente/Algorithmen.pdf (Seite 14)

Allerdings geht beides meiner Meinung nach weit über Schulniveau hinaus.

Tja, das erschient mir leider auch so.....

Oder sollst/willst Du vielleicht eher konzeptionell erklären, warum man ein Matching braucht und wieso genau das das entsprechende Problem löst? Dann schau Dir an was ein Matching ist und versuche zu beweisen, dass es das richtige tut und verwende dass es eine gute Lösung dafür gibt nur als Blackbox.

So wie ich unseren lehrer kenne, erwartet er von uns, dass wir jeden schritt erklären und beweise anführen, weshlab ich eigentlich zumindest die grobe funktionsweise gerne kennen würde, aber wenn es so kompliziert ist, muss ich es dann wohl doch lassen

Ansonsten kann ich Dir nur davon abraten Dich für eine schulische Arbeit mit den Innereien dieses Algorithmus zu beschäftigen. Vermutlich kommt da ein ziemlicher Bockmist raus, außerdem hat der Lehrer davon vermutlich auch keine Ahnung.

Ganz genau! den habe ich nämlich auch schon gefragt und er meinte, er wisse es nicht und das sei mein Problem!

Ben04

Beschreibe mal deine Problemstellung besser. Mir ist noch nicht ganz klar, was du überhaupt erreichen willst. Um einen Eulerkreis zu berechnen braucht man jedenfalls so weit ich sehe keinen allgemeinen Matchingalgorithmus.

also ich habe ein Stadtgebiet genommen, das in isch relativ geschlossen ist, und habe mich informiert, welche Straßen die müllabfuhr entlang fährt, allerdings nicht in welcher Reihenfolge und Richtung, das möchte ich zunächst selbst ausrechnen und mit deren Tour vergleichen.
Die Straßen habe ich als Graphen dargestellt.
Und nun möchte ich die beste route für die Müllabfuhr ausrechnen, also suche ich ja einen Eulerkreis.
Aber ein Eulerkreis existiert ja nur, wenn alle Knoten geraden Grades sind.
Um das wiederum zu erreichen, muss ich je 2 Knoten ungeraden Grades miteinander "verbinden". Dadurch entstehen für die müllabfuhr eigentlich unnötige Fahrten und um die ideale Route zu finden, muss ich diese Fahrten so minimal wie möglich halten.
Somit habe ich ein Matching-Problem!

Aber kann mir jemand sagen, ob der Blossom-Algorithmus, den ich gefunden habe, dafür geeignet ist oder nicht? Sonst habe ich ein noch größeres Problem...

Ach ja und vielen Dank für den Buch-Tip! Ich habe mir das Buch mal über Fernleihe bestellt und hoffe, es bringt mich weiter und wenn nicht ein Kumpel von mir braucht's sicher, also acuh Danke von ihm!!!

Jester

haus-sonne schrieb:

Aber kann mir jemand sagen, ob der Blossom-Algorithmus, den ich gefunden habe, dafür geeignet ist oder nicht? Sonst habe ich ein noch größeres Problem...

Ja, der tut's. Dein Problem hört übrigens auch auf den schönen Namen Postbotenproblem. Folgendes Buch scheint das als Beispiel zu bringen: http://www.springerlink.com/content/nx07216564t6m737/

Das sieht zumindest auf den ersten Blick ganz gut aus. Schick mir am besten mal ne Mail.

volkard

Mups schrieb:

Ich verstehe dein Problem noch nicht ganz: Du hast einen (ungerichteten) Graphen, und suchst eine kürzeste Route, um alle Knoten zu besuchen?

Das hört sich für mich nach dem reisenden Kaufmann an: http://de.wikipedia.org/wiki/Traveling_Salesman_Problem

Nee, alle Straßen müssen besucht werden.
Mir scheint, man muß nur in die Mitte jeder Straße einen zusätzlichen Knoten machen, und hat das Problem des Müllautos reduziert auf das Problem des Handlungsreisenden. Also kann man gute Handlungsreisende auch als Müllfahrer einstellen.
Geht das auch andersrum?

Jester

volkard schrieb:

Mups schrieb:

Ich verstehe dein Problem noch nicht ganz: Du hast einen (ungerichteten) Graphen, und suchst eine kürzeste Route, um alle Knoten zu besuchen?

Das hört sich für mich nach dem reisenden Kaufmann an: http://de.wikipedia.org/wiki/Traveling_Salesman_Problem

Nee, alle Straßen müssen besucht werden.
Mir scheint, man muß nur in die Mitte jeder Straße einen zusätzlichen Knoten machen, und hat das Problem des Müllautos reduziert auf das Problem des Handlungsreisenden. Also kann man gute Handlungsreisende auch als Müllfahrer einstellen.
Geht das auch andersrum?

Nicht wenn P!=NP. Schließlich ist das Problem alle Kanten abzulaufen eben polynomiell lösbar, das Handlungsreisenden-Problem aber NP-schwer. Insofern ist es auch nicht verwunderlich, dass sich das Euler-Problem darauf reduzieren lässt. Es lässt sich nämlich jedes Problem in NP in polynomieller Zeit darauf reduzieren.

Auch danke für den nächsten Buchtipp! Das klingt wirklich ziemlich passend!

Und da ich jetzt zumindest den richtigen Algorithmus kenne, kann ich mir den mal programmieren lassen oder so (halt so, dass er für mich das Ergebnis ausspuckt, sry, ich kenn mich da net so aus ) und dann wenigstens erstmal die Lösung angeben. Erklärung und Beweise kommen dann halt erst später, wenn ich es selbst jemals verstehen sollte....hab ja noch Zeit bis zu den Sommerferien

Hmm. Für einen Eulerkreis müssen nicht alle Knoten eine gerade Anzahl von Kanten haben sondern entweder alle gerade oder genau 2 Knoten mit ungeraden Kanten. Hast Du schonmal die Hilbert-Kurve oder den Ameisenhaufenoptimierungs Algorithmus ausprobiert? Der ist eventuell etwas leichter zu verstehen als der Eulerkreis, den ich leider auch nicht ganz verstanden habe!

Ich glaube für einen Eulerkreis reicht es wenn die Gesamtanzahl der Knoten gerade ist und die Anzahl der Knoten mit geradem Grad, gerade ist.

Da fällt mir was ein:

Wenn du eine Graphen hast mit einer geraden Anzahl an Knoten aber eine ungerade Anzahl von Knoten mit geradem Grad, dann mußt du nur die Kanten der Knoten mit ungeraden Grad verdoppeln (also aus einer Kante eines Knotens mit ungerader Anzahl an kanten zwei Kanten machen die den selben Start- und Zielknoten haben). Diese Straßen können dann einmal hin und einmal zurück befahren werden, dargestellt durch 2 parallele Straßen. Damit wird die Anzahl der Knoten mit geradem Grad gerade und ein Eulerkreis existiert.

Witz:
Verstanden? So gerade ^^

Michael E.

MisterX: Die Anzahl der Knoten ungeraden Grades ist immer gerade, weil zu jeder Kante genau zwei Knoten gehören.

Für einen Eulerkreis (Kreis: Anfangs- und Endknoten des Kantenzuges sind gleich) müssen alle Knoten geraden Grad haben. Für einen Eulerweg dürfen auch genau zwei Knoten ungeraden Grad haben.

MisterX schrieb:

Da fällt mir was ein:

Wenn du eine Graphen hast mit einer geraden Anzahl an Knoten aber eine ungerade Anzahl von Knoten mit geradem Grad, dann mußt du nur die Kanten der Knoten mit ungeraden Grad verdoppeln (also aus einer Kante eines Knotens mit ungerader Anzahl an kanten zwei Kanten machen die den selben Start- und Zielknoten haben). Diese Straßen können dann einmal hin und einmal zurück befahren werden, dargestellt durch 2 parallele Straßen. Damit wird die Anzahl der Knoten mit geradem Grad gerade und ein Eulerkreis existiert.

Witz:
Verstanden? So gerade ^^

Der Thread ist ja eh schon sehr alt u. ich habe nicht damit gerechnet das jmd. antwortet trotzdem Vielen Dank für die vielen u. netten Antworten aber ein Verdoppeln aller Knoten macht man doch bei der TSP-Meta-Heuristk des MST? Ich habe den Witz nicht verstanden! Außderdem muß man eigentlich nicht noch nach dem Finden eines Eulerkreis nach den Hamiltonischen Pfad suchen? D.h. alle doppelten Knoten löschen um einen gültigen Pfad zu bekommen? Kann man eigentlich mit dem selben Algorithmus mehrere Eulerkreise in einem Graphen finden? Und ist der selbe Algorithmus auch zum Finden von Eulerwegen geeignet? Ich glaube ja. Ich habe den Fleury-Algorithmus mal in php nachprogrammiert aber ich bekomme unterschiedliche Ergebnisse. Jmd. Interesse das nachzuprüfen? Hat jmd. vielleicht php installiert?