Matching-Probleme

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?