mikrocontroller.net

Forum: PC-Programmierung Problem des Handlungsreisenden


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Achim (Gast)


Bewertung
-5 lesenswert
nicht lesenswert
Hallo zusammen,

Wie programmiere ich am effizientesten das Problem des 
Handlungsreisenden?

Als einfaches Beispiel mit 5 Orten und einer Startposition.

Wenn ich jede mögliche Strecke ausrechnen lasse ist es bei der geringen 
Anzahl sicher noch möglich aber wenn ich das Problem auf 100 Orte 
erweitern würde wäre die die Zeit zum rechnen viel zu groß.

Finde da keinen Ansatz um dies effektiv zu lösen.

Habt ihr Tipps für mich ?

Gruß
Achim

: Verschoben durch Moderator
von Programmierer (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Achim schrieb:
> Finde da keinen Ansatz um dies effektiv zu lösen.

Ach. Da beißen sich geniale Wissenschaftler seit Jahrzehnten die Zähne 
dran aus. Wenn du eine Lösung findest ist das so etwa der Stein der 
Weisen. Dann wirst du über Nacht König der Welt.

Ansonsten musst du dich mit einer Approximation zufrieden stellen, z.B.:
https://de.wikipedia.org/wiki/MST-Heuristik
Diese ist bei Grafen mit Erfüllung der Dreiecksungleichung höchstens 
doppelt so schlecht wie die optimale Lösung.

von Andreas B. (bitverdreher)


Bewertung
-2 lesenswert
nicht lesenswert
Wenn Du den Algorithmus hast, dann reiche das am besten gleich beim 
Nobelpreisakommitee ein.

von ElKo (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Das ist ein so verbreitetes Problem, dass es da sicher viele Hinweise 
bis hin zu Youtube-Videos als Erklärungen gibt.
Als Einstieg zum Beispiel der Wikipedia-Artikel: 
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#L%C3%B6sungsverfahren

Ich denke, da musst du konkreter werden in der Frage.

von MaWin (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Achim schrieb:
> Habt ihr Tipps für mich

Besuche ein Studium der Informatik, das erklärt dir die Grundzüge.

von Simon S. (simon81)


Bewertung
0 lesenswert
nicht lesenswert
Also hier wird es auch schon mal grundlegend erklärt:

Youtube-Video "Optimale Routen (Graphentheorie)"


Das ist dann davon abhängig, wie Deine 100 Orten untereinander zu 
erreichen sind. Wenn Du die Freiheit hast, dass alle deine Knotengrade 
gerade sind (Eulerkreis)....jupi...Du musst dann keinen Weg doppelt 
fahren und kommst am Startpunkt wieder an.

Das wird aber leider nicht der Fall sein.

Des Weiterem solltest Du die Kantenlänge berücksichtigen. Zum Beispiel 
solltest du die längsten Kanten so selten wie möglich durchgehengehen 
müssen.
Ich würde erstmal die einzelnen Kanten auswerten (Länge und die beiden 
Knotengrade, die an dieser Kante anliegen.

Das wäre so der Anfang.

Gruß
Simon

von Cyblord -. (cyblord)


Bewertung
1 lesenswert
nicht lesenswert
MaWin schrieb:
> Achim schrieb:
>> Habt ihr Tipps für mich
>
> Besuche ein Studium der Informatik, das erklärt dir die Grundzüge.

Das ist nicht nötig um das Problem anzugehen. Dazu haben studierte 
Informatiker genügend Alogrithmen und Libraries erstellt. Um etwas 
Anzuwenden muss man nicht Experte in diesem Gebiet sein. Man muss eben 
wissen dass es keine "gute" Lösung gibt, sondern nur Kompromisse.

von TSP (Gast)


Bewertung
0 lesenswert
nicht lesenswert
TSP im Allgemeinen ist NP-vollständig, schneller als O(2^n) wird's fürs 
Optimum erstmal nicht.

Beitrag #6191658 wurde von einem Moderator gelöscht.
von Cyblord -. (cyblord)


Bewertung
2 lesenswert
nicht lesenswert
Reiseleiter schrieb im Beitrag #6191658:

> Steht denn nicht jeder Routenplaner und jeder Autorouter in einem
> Layoutprogramm vpor dem gleichen Problem?

Nein ein Routenplaner sucht eine Route von A nach B. Das ist im Prinzip 
einfache Graphentheorie, Breitensuche mit gewichteten Kanten usw. 
Natürlich alles im Details verfeinert.

Hat mit dem Handlungsreisenden nichts zu tun.
Dort hat man X Ziele und will die Reihenfolge ermitteln in denen man 
diese Ziele anfährt. z.B. mit dem Ziel des kürzesten Gesamtweges.
Bei 10 Zielen gibt es schon >3 Mio. Möglichkeiten.

: Bearbeitet durch User
von Programmierer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Cyblord -. schrieb:
> Bei 10 Zielen gibt es schon >3 Mio. Möglichkeiten.

Aber nur wenn der Graph vollvermascht ist und man die Auswahl des 
Startpunkts als Freiheitsgrad betrachtet... Prinzipiell ist der 
Ausgangspunkt egal, es kommt ja immer die gleiche Tour raus, den 
Startknoten kann man sich darin beliebig wählen.
Stell dir einen Graphen mit 10 Knoten vor der einfach nur ein Kreis ist 
- da hast du nur 1 oder 10 Möglichkeiten, je nach Betrachtungsweise :-)

von Cyblord -. (cyblord)


Bewertung
0 lesenswert
nicht lesenswert
Programmierer schrieb:
> Cyblord -. schrieb:
>> Bei 10 Zielen gibt es schon >3 Mio. Möglichkeiten.
>
> Aber nur wenn der Graph vollvermascht ist
Selbstverständlich geht das Allgemeine TSP davon aus.

> und man die Auswahl des
> Startpunkts als Freiheitsgrad betrachtet... Prinzipiell ist der
> Ausgangspunkt egal, es kommt ja immer die gleiche Tour raus, den
> Startknoten kann man sich darin beliebig wählen.
> Stell dir einen Graphen mit 10 Knoten vor der einfach nur ein Kreis ist
> - da hast du nur 1 oder 10 Möglichkeiten, je nach Betrachtungsweise :-)

In der Praxis gibt es immer Möglichkeiten durch real vorhandene 
Einschränkungen besser als der Worst-Case zu sein. Darauf basieren ja 
auch viele Ansätze zu diesem Thema.

von MikeH (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Das Stichwort dass du suchst heiß Dijkstra Algorithmus
https://www.wikiwand.com/de/Dijkstra-Algorithmus

von Wolfgang (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Cyblord -. schrieb:
> Man muss eben wissen dass es keine "gute" Lösung gibt, sondern
> nur Kompromisse.

Du bist auf dem Holzweg.

Natürlich gibt es gute Lösungen, die dann ein Kompromiss aus Güte und 
Rechenaufwand darstellen.
Bisher ungelöst ist das Finden des optimalen Weges.

von Cyblord -. (cyblord)


Bewertung
1 lesenswert
nicht lesenswert
Wolfgang schrieb:
> Cyblord -. schrieb:
>> Man muss eben wissen dass es keine "gute" Lösung gibt, sondern
>> nur Kompromisse.
>
> Du bist auf dem Holzweg.
Aha
>
> Natürlich gibt es gute Lösungen, die dann ein Kompromiss aus Güte und
> Rechenaufwand darstellen.
> Bisher ungelöst ist das Finden des optimalen Weges.

Ist ja Unsinn. Den optimalen Weg zu finden ist einfach. Ungelöst ist, 
das in P zu machen.

von Programmierer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Cyblord -. schrieb:
> Selbstverständlich geht das Allgemeine TSP davon aus.

So selbstverständlich ist das nicht. Wikipedia sagt auch nur "meist". 
Allerdings kann man im Zweifelsfall sehr teure Dummy-Kanten einfügen.

MikeH schrieb:
> Das Stichwort dass du suchst heiß Dijkstra Algorithmus
> https://www.wikiwand.com/de/Dijkstra-Algorithmus

Das ist völlig verkehrt und hat nichts mit der Frage zu tun.

von Cyblord -. (cyblord)


Bewertung
0 lesenswert
nicht lesenswert
Programmierer schrieb:

> MikeH schrieb:
>> Das Stichwort dass du suchst heiß Dijkstra Algorithmus
>> https://www.wikiwand.com/de/Dijkstra-Algorithmus
>
> Das ist völlig verkehrt und hat nichts mit der Frage zu tun.

Es hat nichts mit TSP zu tun. Wenn ich allerdings das Eingangspost lese, 
bin ich mir nicht sicher was der TE genau will. Wenn er von einem 
Startpunkt aus, 5 Ziele hat und jeweils die Strecke zu diesen Zielen 
wissen will, ist das normale Routenplanung (mal 5) und geht mit 
Dijkstra. Ist nur dann kein TSP bzw. eben stark beschränkt.
Die Frage ist ja nur, kann er den trivialen Weg gehen für sein konkretes 
Problem oder muss er sich tatsächlich mit Effizienz beschäftigen.

: Bearbeitet durch User
von Programmierer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Cyblord -. schrieb:
> bin ich mir nicht sicher was der TE genau will

Das ist eh immer eine philosophische Frage.

Reiseleiter schrieb im Beitrag #6191658:
> Wenn es eine komplette Ausgangssperre gibt, hat der
> Handlungsreisende zu
> Hause genug Zeit und Ruhe, die optimalen Routen für das nächste halbe
> Jahr auszurechnen....

Tja, wie praktisch wäre auch eine App mit der man sich den optimalen Weg 
durch einen Supermarkt planen könnte, um alle benötigten Artikel so 
schnell wie möglich einzusammeln sodass man sich so kurz wie möglich den 
Mitmenschen aussetzen muss - leider NP-hart, und leider würden die 
Supermarkt-Betreiber so etwas niemals zulassen weil die Kunden weniger 
kaufen würden wenn sie schneller durch sind. Da wird auch eine globale 
Pandemie nichts dran ändern---

von georg (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Programmierer schrieb:
> Tja, wie praktisch wäre auch eine App mit der man sich den optimalen Weg
> durch einen Supermarkt planen könnte

Wird auf absehbare Zeit nicht gebraucht - den Weg zum Klopapier finden 
die meisten auf Anhieb.

Georg

von Walter T. (nicolas)


Bewertung
0 lesenswert
nicht lesenswert
Nicht schlecht. Endlich mal etwas, was besser funktioniert, als 
Geschichten ohne Enten.

von ReiSender (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Wenn es eine komplette Ausgangssperre gibt, hat der Handlungsreisende zu 
Hause genug Zeit und Ruhe, die optimalen Routen für das nächste halbe 
Jahr auszurechnen....

Steht denn nicht jeder Routenplaner und jeder Autorouter in einem 
Layoutprogramm vpor dem gleichen Problem?

von c-hater (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Wolfgang schrieb:

> Cyblord -. schrieb:
>> Man muss eben wissen dass es keine "gute" Lösung gibt, sondern
>> nur Kompromisse.
>
> Du bist auf dem Holzweg.
>
> Natürlich gibt es gute Lösungen, die dann ein Kompromiss aus Güte und
> Rechenaufwand darstellen.

Genau das schrieb er doch, oder nicht? Sprich: du opponierst, wo es 
eigentlich gar keine Opposition gibt, gegen die zu opponieren wäre. 
Warum machst du das, nur, um auch mal was gesülzt zu haben?

von georg (Gast)


Bewertung
0 lesenswert
nicht lesenswert
ReiSender schrieb:
> Steht denn nicht jeder Routenplaner und jeder Autorouter in einem
> Layoutprogramm vpor dem gleichen Problem?

Nein. Der Handlungsreisende sucht den kürzesten Weg, der VIELE Ziele 
miteinander verbindet. Der Routenplaner sucht den kürzesten Weg zu EINEM 
Ziel. Der Autorouter sucht VIELE Wege von vielen Zielen zu vielen 
anderen Zielen. Das sind ganz verschiedene Aufgaben.

Georg

von ReiSender (Gast)


Bewertung
0 lesenswert
nicht lesenswert
georg schrieb:
> ReiSender schrieb:
>> Steht denn nicht jeder Routenplaner und jeder Autorouter in einem
>> Layoutprogramm vpor dem gleichen Problem?
>
> Nein. Der Handlungsreisende sucht den kürzesten Weg, der VIELE Ziele
> miteinander verbindet. Der Routenplaner sucht den kürzesten Weg zu EINEM
> Ziel.

Ich habe einen Verwandten, der bei einer Baustoffspedition die Touren 
plant.
Da geht es auch darum, mehrere Ziele in der besten Reihenfolge 
anzufahren und nebenbei auch noch irgendwo abgestellte 
Anhänger/Auflieger einzusammeln. Der hat ein Programm dafür auf dem 
Rechner, was diese Arbeit offenbar gut erledigt.

Leider fällt mir nicht mehr ein, wie es heißt.

von M. F. (fuchs1991)


Bewertung
0 lesenswert
nicht lesenswert
ReiSender schrieb:
> Ich habe einen Verwandten, der bei einer Baustoffspedition die Touren
> plant.
> Da geht es auch darum, mehrere Ziele in der besten Reihenfolge
> anzufahren und nebenbei auch noch irgendwo abgestellte
> Anhänger/Auflieger einzusammeln. Der hat ein Programm dafür auf dem
> Rechner, was diese Arbeit offenbar gut erledigt.
>
> Leider fällt mir nicht mehr ein, wie es heißt.

Wahrscheinlich wird das Programm alle Möglichkeiten durchprobieren.
Was aber ab einer gewissen Anzahl an Zielen viel zu langen dauern würde.
Aber ich denke das die Spedition maximal 10 Ziele auf einer Route 
anfährt.

von Ben B. (Firma: Funkenflug Industries) (stromkraft)


Bewertung
0 lesenswert
nicht lesenswert
Es gibt für solche Probleme keinen besseren Lösungsweg als die 
Möglichkeiten durchzuprobieren und zu bewerten, evtl. kann man hier und 
da was zusammenfassen oder optimieren, aber es gibt keine Formel, die 
sofort den kürzesten Weg ausspuckt.

Die Komplexität steigt exponentiell an, daher können Computer solche 
Aufgaben  mit einer "normalen" Anzahl Punkten quasi sofort lösen. 
Allerdings kann eine Verdopplung der Punkte dazu führen, daß die Aufgabe 
nicht mehr in praktischer Zeit lösbar wird.

von PittyJ (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hat sich das Problem nicht eh erledigt?
Handlungsreisende gibt es nicht mehr. Es gilt ja Sozialkontakte zu 
vermeiden.

Ein jeder "Ex-Handlungsreisender" macht heute Home-Office und eine 
Video-Konferenz mit seinen Kunden. Und da ist die Reihenfolge vollkommen 
egal.

So hat Corona wenigstens das Problem der Handlungsreisenden gelöst.

von Cyblord -. (cyblord)


Bewertung
0 lesenswert
nicht lesenswert
Ben B. schrieb:
> Es gibt für solche Probleme keinen besseren Lösungsweg als die
> Möglichkeiten durchzuprobieren und zu bewerten, evtl. kann man hier und
> da was zusammenfassen oder optimieren, aber es gibt keine Formel, die
> sofort den kürzesten Weg ausspuckt.

Aber sicher gibt es Heuristiken die besser als der Worst-Case sind. Und 
die werden in solchen Programmen auch eingesetzt.

Vergleiche mal mit Primzahltests. z.B. Miller-Rabin.

In der Realität kann man nämlich Einschränkungen annehmen die der 
generelle theoretische Fall nicht hat.

von Christoph db1uq K. (christoph_kessler)


Bewertung
0 lesenswert
nicht lesenswert
Der Schwarzmarkthändler von den Muppets heißt auch schlicht salesman.

"Hey Du, willst du ein M kaufen? EIN M KAUFEN?? Pschht nicht so lauuut"

In der deutschen Version heißt er Schlemihl, der hat seine Seele dem 
Teufel verkauft.
https://de.wikipedia.org/wiki/Peter_Schlemihls_wundersame_Geschichte

In einer EULA von 2010 musste die Seele in einer mindestens 6 Fuß hohen 
Flammenschrift eingefordert werden:
https://www.geek.com/games/gamestation-eula-collects-7500-souls-from-unsuspecting-customers-1194091/

: Bearbeitet durch User
von ReiSender (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christoph db1uq K. schrieb:
> Der Schwarzmarkthändler von den Muppets heißt auch schlicht salesman.
>
> "Hey Du, willst du ein M kaufen? EIN M KAUFEN?? Pschht nicht so lauuut"
>
> In der deutschen Version heißt er Schlemihl, der hat seine Seele dem
> Teufel verkauft.
> https://de.wikipedia.org/wiki/Peter_Schlemihls_wundersame_Geschichte


Da issa ja! Psst -nicht so LAUT!

Youtube-Video "Ernie und Schlemihl - unsichtbares Eis (Sesamstrasse)"

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.