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