PYME.Analysis.points.traveling_salesperson.queue_opt module¶
- class PYME.Analysis.points.traveling_salesperson.queue_opt.TSPQueue(positions, start=0, epsilon=0.01, t_step=1)¶
Bases:
object
Object which masquerades as an n x 2 positions array for use in position queuing. Delays are added in the __getitem__ call according to the t_step attribute which allows positions to be sorted in the background while positions near the beginning of the route are already accessible.
- queue_two_opt(initial_route, epsilon, t_step, distances, og_distance)¶
Solves the traveling salesperson problem (TSP) using two-opt swaps to untangle a route. Does so in a way which is convenient for quickly accessing the beginning of the sorted list, as t_step is used to periodically advance the first index which can be moved by the sort
- Parameters
- initial_route: ndarray
[optional] route to initialize search with. Note that the first position in the route is fixed, but all others may vary. If no route is provided, the initial route is the same order the distances array was constructed with.
- epsilon: float
exit tolerence on relative improvement. 0.01 corresponds to 1%
- t_step: float
average time after which to advance an index. A single step can easily be longer if the nested for loop takes a considerable amount of time, after which multiple indices will be moved to the ‘sorted’ route to catch up.
- distances: ndarray
distance array, which distances[i, j] is the distance from the ith to the jth point
- og_distance: float
path-length of initial_route
- property start_ind¶