Published
Edited
Sep 17, 2021
1 star
solveTSP = function(adjacencyMatrix) {
// algo slightly modified version of its implementation here: https://observablehq.com/@oscarlvp/tsp-art
// edited here for haversine distance
const ESPILON = -0.001;
const N = adjacencyMatrix.length;
var toRad = 1;
let distances = (() => {
const dist = (a, b) => adjacencyMatrix[a][b]
let result = [];
for (let i = 0; i < N; i++) {
let row = new Float32Array(N);
for (let j = 0; j < N; j++) {
row[j] = dist(i, j);
}
result.push(row);
}
return result;
})();
function firstTwoOptImprovement(tour) {
const next = current => (current + 1) % tour.length;
const pick = d3.randomInt(tour.length - 2);
function delta(i, j) {
let ni = tour[next(i)];
let nj = tour[next(j)];
let ci = tour[i];
let cj = tour[j];
return (
distances[ci][cj] +
distances[ni][nj] -
distances[ci][ni] -
distances[cj][nj]
);
}
function move(from, to) {
let result = [...tour];
let count = to - from;
for (let i = 0; i < count; i++) {
result[from + 1 + i] = tour[to - i];
}
return result;
}
for (
let times = 0, start = pick();
times < tour.length;
times++, start = next(start)
) {
for (let end = start + 2; end < tour.length; end++) {
let variation = delta(start, end);
if (variation < ESPILON) {
return { tour: move(start, end), delta: variation };
}
}
}
return { tour: tour, delta: 0 };
}
const random = () => d3.shuffle(d3.range(N));
let current = { tour: random(), delta: Number.MIN_SAFE_INTEGER };
//yield current.tour;
console.log("delta " + current.delta);
while (current.delta < 0) {
//yield current.tour;
current = firstTwoOptImprovement(current.tour);
}
//yield current.tour;
return(current.tour);
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
