tsp
-
ich weiß es gibt unzähliges über das travelling salesman problem im Internet aber ganz kapieren tu ich es dann leider doch nicht deswegn hab ich mir gedacht vll kann mir das mal jemand erklären.
Soweit ich das Verstanden habe ist eine Methode zum optimieren jene, wo man das große Problem in Teilprobleme aufteilt und wenn diese gut sind müssen sie nicht mehr beachtet werden (branch and bound?) um den exponentiellen Rechenaufwand für eine vernünftige Anzahl von Orte klein zu halten.
leider hab ich aber keine Idee wie ich meine Orte (Orte und die Gewichtung der Kanten ist die Entfernung auf der Erdoberfläche) in Teilprobleme aufteile.
Was ich bis jetzt habe ist eine Rundreise zu erzeugen mit vollständiger Permutation (ist bis 12 Orte noch schnell aber 20-30 sollte ich schaffen) sowie einen Minimum Spanning Tree nach dem Algorithmus von Kruskal zu erzeugen.
Meine Frage ist also kann mir jemand vll erklären wie man das in Teilprobleme aufteilt bzw. wie man nach Erzeugung des Minimum Spanning Trees fortfährt.
Vielen Dank im voraus
Tom