solve_tsp_with_2opt

solve_tsp_with_2opt#

mrinufft.trajectories.maths.tsp_solver.solve_tsp_with_2opt(locations, improvement_threshold=1e-08)[source]#

Solve approximately the TSP using a 2-opt approach.

A sub-optimal solution to the Travelling Salesman Problem (TSP) is provided using the 2-opt approach in O(n²) time and memory, where chunks of an arbitrary initial route are reversed, and selected if the total distance is reduced. A notable result in 2D is that the path is guaranteed to never cross itself.

This implementation solves the TSP for a one-way path, not a looping cycle.

Parameters:
  • locations (NDArray) – An array of N points with shape (N, D) where D is the space dimension.

  • improvement_threshold (float, optional) – Threshold used as progress criterion to stop the optimization process. The default is 1e-8.

Returns:

The new positions order of shape (N,).

Return type:

NDArray