0

I'm trying to calculate fastest route through 8 points with different travel times between them. You can start at any point, and you have to travel through all of the points once. You do not have to finish at the same point where you started.

I'm trying to do it with lists in a list (sort of a matrix including all the possible travel times), and figure out a proper recursive function to loop through all the possibilities and check if the current solution is faster than the fastest one and if, then save it as a new fastest route. But I can't quite manage to find out the proper way to loop through all the possibilities.

jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
Moonlooper
  • 1
  • 1
    Please review [ask] and the [tour] and put a [mcve] in the question. – jonrsharpe Jan 13 '17 at 23:12
  • Dynamic programming? Something like `optimal_time = (time to current node) + min(time to neighbor_edges)` – OneCricketeer Jan 13 '17 at 23:14
  • Must you use recurision to loop through all possibilities? Python's maximum recursion depth might make this impractical. Why not use `itertools.permutations(points,len(points))` – juanpa.arrivillaga Jan 13 '17 at 23:15
  • https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm or perhaps https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm – OneCricketeer Jan 13 '17 at 23:17
  • This is a (variant of) the traveling salesman problem. 8! isn't too big so you can brute-force it, with `itertools` being the natural tool. On the other hand, if you are satisified with a near-optimal you could just use a nearest neighbor heuristic followed by a 2-opt refinement. For problems that small, this will usually produce an optimal solution. – John Coleman Jan 13 '17 at 23:25
  • I can see closing the question as off-topic, but calling it a duplicate of that particular question isn't very plausible. The two questions don't seem to have a lot in common. – John Coleman Jan 14 '17 at 00:00

0 Answers0