solve_tsp_with_2opt#
- mrinufft.trajectories.maths.tsp_solver.solve_tsp_with_2opt(locations, improvement_threshold=1e-08)[source]#
Solve the TSP problem 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²) where chunks of an initially random route are reversed, and selected if the total distance is reduced. As a result, the route solution does not cross its own path in 2D.
- 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