Frage von MechiMac, 11

Idee für MathLab-Routenplanung oder Buchempfehlungen?

Unser Uni MathLab-Projekt besteht zurzeit aus der Fragestellung, wie eine Müllabfuhr die die beste Route bestimmt. Es gibt Sackgassen und Einbahnstraßen. Jede Straße muss einmal befahren werden und der Anfang und Endpunkt sind identisch. Hat jemand eine Idee für ein Math-Lab Script oder eine Buchempfehlung, wie man am besten diese Routen bestimmt?

Vielen Dank im Vorraus Mfg MechiMac

(Genauere Details)

Es wird eine Matrize an dieses Script übergeben welche Straßenknotenpunkte mit einander durch eine Straße verbunden sind. Erweitert wäre es auch möglich die Entfernung mitzugeben durch diese Matrize und dadurch nochmal bessere Routen zu planen.

Antwort
von Maimaier, 5

Eine optimale Rundreise wäre dann gefunden, wenn jede Straße genau 1 mal befahren wird, das wäre dann ein Eulerkreis. Das geht aber nur, wenn in jedem Knoten die Anzahl Kanten gerade ist. Ungerade Anzahl Kanten bedeuten Extrawege.  (Hier ohne Einbahnstraßen)

Teilgraphen, in denen solch ein Eulerkreis gefunden werden kann, sind schon optimal. Das macht den Suchraum schon beträchtlich kleiner.

Jetzt vielleicht noch eine Heuristik, welche Straßen mehrfach befahren werden müssen: um so kürzer umso besser. Durch die mehrfach befahrenen Straßen gibt es wieder gerade Anzahl von Kanten, Eulerkreis wieder möglich, siehe oben.

Hab ich mir gerade selber ausgedacht. Vielleicht gibt es bessere Algorithmen.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten