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
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.
Wenn Du den Algorithmus hast, dann reiche das am besten gleich beim Nobelpreisakommitee ein.
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.
Achim schrieb: > Habt ihr Tipps für mich Besuche ein Studium der Informatik, das erklärt dir die Grundzüge.
Also hier wird es auch schon mal grundlegend erklärt: https://www.youtube.com/watch?v=_J4FlTOHEDU 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
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.
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.
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
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 :-)
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.
Das Stichwort dass du suchst heiß Dijkstra Algorithmus https://www.wikiwand.com/de/Dijkstra-Algorithmus
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.
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.
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.
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
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---
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
Nicht schlecht. Endlich mal etwas, was besser funktioniert, als Geschichten ohne Enten.
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?
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?
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
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.
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.
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.
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.
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.
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
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! https://www.youtube.com/watch?v=7J2oijo9958
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.