3 ms·

This is great, thanks for sharing! I had good results with genetic algorithms as well.

• mjn 6y ago
  There are also TSP-specific heuristics that work well in practice on a lot of large instances, often finding the optimal solution pretty quickly (but with no guarantees of optimality). The first I believe was the Lin-Kernighan heuristic from 1973 (the same Kernighan as the 'K' in K&R C, incidentally). There are fast implementations of some modern improved versions, e.g.: http://akira.ruc.dk/~keld/research/LKH/ http://akira.ruc.dk/~keld/research/LKH/
  • IncRnd 6y ago
    I coded a version of SA for TSP in the early 90s. I iterated until the probability of a hardware error was greater than having a sub-optimal solution. It took just a couple of seconds, and that speed was due to visually displaying the algorithm as it executed.
  • fjfaase 6y ago
    I believe that this is about a different type of TSP problem, where the distances between cities are defined by the geometric distance from their coordinates in some plane (or on a sphere). This is a simpler problem than when the distances are specified as (whole) numbers.
    • knuthsat 6y ago
      Geometric distance implies symmetry, asymmetric TSP can be converted to symmetric by doubling the number of vertices.