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);
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.