Idee für MathLab-Routenplanung oder Buchempfehlungen?

...komplette Frage anzeigen

1 Antwort

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.

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?