Hallo zusammen

Etwas für die Denker und Mathematiker hier (und fürs Wochenende).

Ich suche nach einem Algorithmus, der sich einfach folgendermassen beschreiben lässt:

Ein Bauer möchte sein Land bewässern indem er entlang eines vorgegebenen Weges mit seinem Pflug einen Graben zieht (siehe Bild). Wie muss der Bauer nun mit seinem Traktor fahren, damit er die Arbeit in möglichst kurzer Zeit erledigen kann? Am Ende jedes Weges darf er auch seinen Pflug hoch heben und zum nächsten Weg fahren, den er noch nicht gepflügt hat.

Als Vorgabe erhält er eine Liste mit Wegen (L1, L2, L3, ... Ln). Jeder Weg hat einen Startpunkt P1(x1,y1) und einen Endpunkt P2(x2,y2). Zurück geben sollte der Algorithmus eine Liste nach welcher reihenfolge der Bauer fahren sollte und wann er den Pflug heben oder senken muss.

Über Eure Tipps, wie ihr das Problem lösen würdet, bin ich sehr gespannt.

Beste Grüsse
Geri
PS. Ach ja, der Traktor fährt immer gleich schnell, die Zeit für das hoch heben und Senken des Pfluges kann vernachlässigt werden:)

Cool, TSP^^ (siehe Wiki) Den Unterschied zwischen klasischen TSP und deinem Problem is, das Bestimmte Routen abgefahren werden müssen und nicht bestimmte Städte. Das kann man aber ganz schnell ändern^^


Wird zu

wobei die Os Städte darstellen und die Linien die möglichen Routen. Die Strecke zwischen dem 1. Knoten, der Stadt und dem 2. Knoten muss nur gleich der Entfernung zwischen Erstem und 2. Knoten sein.- Schon kannst du die verschiedenen Lösungsstrategien darauf ansetzen, dies da gibt. Ein paar Schlagworte:
- Ameisen-Algorythmus (A*)
- Kohonen-Netze
- usw.
- Bruteforcen (Alles durchprobieren, Müsste bei den paar möglichen Wegen noch möglich sein)

Tjioar.... Progen musste selbst^^

Hallo

Tjioar, vielen Dank für Deine Rückmeldung.

Das Traveling Salesman-problem, den Ameinsenalgorithmus imd Kohonen-Netze habe ich mir auch schon angeschaut, nutzen mir für dieses Problem leider auch nichts.

Ich habe vielleicht auch vergessen zu sagen, dass es sehr viele Wege gibt (ca. 100.000)

Beste Grüsse
Geri

Für mich schaut das mehr nach dem Eulerkreisproblem aus (mehr dazu bei Wiki). Dies sollte sich auch für viele Elemente gut lösen lassen.

Falls du es dennoch als allgemeines TSP modellieren willst, dann hast du es mit deiner großen Anzahl sehr schwer (für das allgemeine TSP gibt es auch keine Approximationsalgorithmen).
So wie ich das sehe würde es sich aber um die metrische (oder sogar euklidische) Version des TSP handeln. Dafür gibt es verschiedene Approximationsalgorithmen (z.B.: Christofides Heuristik)

Hallo Reddevil

Eulerkreis ist es glaube ich auch nicht, da es sich ja meines Wissens um ein Eulerproblem handelt (Eulerkreis oder ein offener Eulerzug) wenn es einen Weg gibt, bei dem jede Kante nur einmal durchlaufen wird. In dem beschriebenen gibt es ja auch mehrere Eulerzüge.

Beste Grüsse
Geri

Du willst doch das jede Kante einmal durchlaufen wird oder hab ich das falsch verstanden?

Für die Knoten mit ungeradem Grad musst du zuerst ein gewichtsminimales maximum Matching finden, wobei du als Gewichte die "Länge" eines kürzesten Weges zwischen den entsprechenden Knoten verwendest. Die Kanten aus dem Matching fügst du in deinen Graphen ein und suchst darin einen Eulerkreis/Eulerzug und bist fertig.

Wie du einen Eulerkreis/Eulerzug findest steht bei Wiki. Auch für das finden der kürzesten Wege findest du dort was.
Für das Matching hab ich leider nichts bei Wiki gefunden und ich weiss auch nicht wie das genau geht. Ich glaube gehört zu haben dass es in O(n³) geht (also für die Größe deines Problems durchaus machbar)

Hallo reddevil

Ich glaube, ich verstehe Lösungsansatz teilweise.

"
Für die Knoten mit ungeradem Grad musst du zuerst ein gewichtsminimales maximum Matching finden, wobei du als Gewichte die "Länge" eines kürzesten Weges zwischen den entsprechenden Knoten verwendest. Die Kanten aus dem Matching fügst du in deinen Graphen ein und suchst darin einen Eulerkreis/Eulerzug und bist fertig. "

.. welche entsprechenden Knoten meinst du hier aber bitte. Ich kann mir aber vorstellen, das Gewichtsminimal herauszufinden ist sehr zeitaufändig, wenn ich den shortest-path-Algorithmus für alle Knoten berechnen muss.

Irgendwie habe ich auch den Verdacht, es könnte sich um das Hamiltonkreisproblem handeln. Die Lösung könnte dann vielleicht so aussehen:

Was meinst du/ihr aber dazu
1.) Suche alle zusammenhängende Pfade
2.) suche alle Hamilton-Kreise
3.) suche die übrigen Wege (Euler-Wege)
4.) lege einen Startpunkt fest
5.) wenge TSP-an

Die Lösung führt zwar nicht zum Supremum Optimum, dürfte davon aber nicht so weit entfernt liegen.

Irgendwie lässt mich aber immer noch nicht das Gefühl nicht los, dass ich hier zu kompliziert denke.

Jedenfalls nochmals vielen Dank fürs Mitdenken und freundliche Grüss!

Geri

Hallo

Beim Hamilton-Kreis geht es darum einen Kreis zu finden bei dem jeder Knoten genau einmal besucht wird. Du willst doch aber das jede Kante in deinem Graphen mindestens einmal besucht wird? Das Hamilton-Kreis Problem ist, wie das TSP auch, NP-vollständig (also für große Instanzen praktisch nicht lösbar).

Jetzt nochmal meine Lösungsidee zu deinem Problem in ausführlicherer Form.

Du hast einen Graphen G, welcher als Knoten die "Ecken der Felder" enthält und als Kanten die Wege die bewässert werden sollen. Die Wege die bewässert werden sollen müssen abgefahren werden, daran kannst du nichts minimieren. Minimieren kannst du die Wege welche doppelt gefahren werden müssen bzw die "diagonalen Wege ohne Pflug".

Wenn dein Graph einen Eulerkreis enthalten würde, so wäre dieser eine Lösung des Problems. Ein Graph hat genau dann einen Eulerkreis wenn der Grad (die Valenz) aller Knoten gerade ist.
Falls dein Graph nun aber keinen Eulerkreis enthält so fügst du noch zusätzliche Kanten ein bis er einen Eulerkreis hat. Das Ziel ist es jetzt genau die Kanten rauszufinden damit G einen Eulerkreis hat und deren Gewicht (Gewicht ist in diesem Fall z.B. die Länge des Weges oder die benötigte Fahrzeit für die Kante oder weiss der Geier) minimal ist. Um das zu erreichen baust du einen zweiten Graphen G' auf. Die Knoten von G' sind gerade die Knoten aus G die ungeraden Grad haben. Der Graph G' sei vollständig, also zwischen je zwei Knoten existiert eine Kante. Du ordnest jeder Kante ein Gewicht wie folgt zu: die Kante {x,y} aus G' erhält als Gewicht die Länge eines kürzesten Weges von x nach y in G.
In dem Graphen G' suchst du jetzt ein gewichtsminimales perfektes Matching (das geht in O(n³) aber ich weiss nicht wie). Die Kanten die dir das Matching liefert fügst du in G ein. Dadurch haben nun alle Knoten in G geraden Grad und es gibt einen Eulerkreis der die Lösung des Problems ist.

Wie ist denn dein Vorwissen zu der ganzen Sache? Schüler? Student? Graphentheorie? Informatik?

Hallo Reddevil

Vielen Dank für Deine Mühe und die detaillierte Beschreibung! Du hast recht, beim Hamiltonproblem geht es um etwas anderes. Ich habe da zu ungenau recherchiert.

Ich glaube, deinen Lösungsansatz verstehe ich nun. Die Überlegung finde ich wirklich sehr gut! Vielleicht finde ich auch noch eine Lösung für das Matching.

Ja, jedenfalls ist das Problem nicht trivial. Erschwerend kommt später schliesslich noch hinzu, dass der Bauer das Ganze in mehreren Ortschaften tun soll.

Hätte mir nur gedacht, dass es für dieses Problem eine für den semi-professionellen Bereich (also finanzierbare) kommerzielle Komponente gibt.

Beste Grüsse und nochmals vielen Dank für Deinen nachhaltige Hilfe!

Geri

Vor einigenn Jahren habe ich eine Wi-Ing-Studium abgeschlossen. Mit der Graphentheorie bin ich aber nur aus Eigeninteresse ein wenig in Kontakt gekommen:)