salesman
See: demo
Author: Ophir LOJKINE
Author: Thibaud MICHEL
salesman npm module
Modified by Wemap (thibaud@getwemap.com) to add ts
Good heuristic for the traveling salesman problem using simulated annealing.
salesman~Point
Kind: inner class of salesman
new Point(x, y)
Represents a point in two dimensions. Used as the input for solve
.
Param | Type | Description |
---|
x | number | abscissa |
y | number | ordinate |
salesman~solve(points, [temp_coeff], [callback], [callback]) ⇒ Array.<number>
Solves the following problem:
Given a list of points and the distances between each pair of points,
what is the shortest possible route that visits each point exactly
once and returns to the origin point?
Kind: inner method of salesman
Returns: Array.<number>
- An array of indexes in the original array. Indicates in which order the different points are visited.
Param | Type | Default | Description |
---|
points | Array.<Point> | | The points that the path will have to visit. |
[temp_coeff] | number | 0.999 | changes the convergence speed of the algorithm. Smaller values (0.9) work faster but give poorer solutions, whereas values closer to 1 (0.99999) work slower, but give better solutions. |
[callback] | function | | An optional callback to be called after each iteration. |
[callback] | function | euclidean | An optional argument to specify how distances are calculated. The function takes two Point objects as arguments and returns a number for distance. Defaults to simple Euclidean distance calculation. |
Example
var points = [
new salesman.Point(2,3)
];
var solution = salesman.solve(points);
var ordered_points = solution.map(i => points[i]);