Strassennetz mit minimaler Streckenlänge abfahren

Question

In einem gegebenen Netz aus zusammenhängenden Strassen soll von einem identischen Start/Ziel Punkt aus das gesamte Netz bei minimaler Streckenlänge abgefahren werden. Jede Strecke zwischen zwei Kreuzungspunkten soll möglichst nur einmal befahren werden (ist wohl nicht immer möglich). Wie kann man diese Aufgabe möglichst einfach lösen? Ich glaube, es handelt sich dabei um das sogenannte "Briefträgerproblem".

Answer 1

Das ist das Problem eines Handlungsreisenden

Das Thema ist sehr komplex. Bitte schau dir zunächst mal Wikipedia und die Weiterführende Literatur dazu an.

https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Solltest du noch weitere Fragen haben, oder etwas nicht verstehen, dann melde dich gerne wieder.

Comments

Nein, dabei handelt es sich nicht um das Problem des Handlungsreisenden!

Das Problem des Handlungsreisenden besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist.

Bei meiner Frage geht es darum, ein gesamtes Strassennetz abzufahren (jede der vorhandenen Strassen mindestens einmal befahren). Die gesamte gefahrene Strecke soll möglichst klein sein. Der Startpunkt und der Zielpunkt der Reise sind ein und derselbe.

---

Oh. Ja ich verstehe jetzt den Unterschied. Bei Wikipedia gibt es sogar auch einen Eintrag zum Briefträgerproblem

https://de.wikipedia.org/wiki/Briefträgerproblem

Dort ist auch geschildert wie man so ein Problem lösen kann.