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