Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦
Finding a short route through points without returning back with 2-opt
{
// build a distance matrix, including an additional "sentinel" point with 0 distance to all other points
const n = points.length + 1;
const distances = new Float64Array(n * n);
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n - 1; j++) {
const [x0, y0] = points[i];
const [x1, y1] = points[j];
const d = Math.hypot(x1 - x0, y1 - y0);
distances[i * n + j] = d;
distances[j * n + i] = d;
}
}
// start with an arbitrary route, including the sentinel
const path = new Uint16Array(n);
for (let i = 0; i < n; i++) path[i] = i;
// do a fixed number of max iterations to make sure we don't get stuck; usually 2-4 suffice
for (let k = 0; k < 10; k++) {
let foundImprovement = false;
for (let i = 0; i < n; i++) {
for (let j = i + 2; j < n; j++) {
const k0 = path[i];
const k1 = path[(i + 1) % n];
const k2 = path[j];
const k3 = path[(j + 1) % n];
const p01 = distances[n * k0 + k1];
const p23 = distances[n * k2 + k3];
const p02 = distances[n * k0 + k2];
const p13 = distances[n * k1 + k3];
if (p01 + p23 - p02 - p13 > 1e-20) {
path.subarray(i + 1, j + 1).reverse(); // found an improvement; do a 2-opt swap
foundImprovement = true;
await Promises.delay(8); yield draw(path); // draw intermediary results for the viz
}
}
}
if (!foundImprovement) break;
}
// you would then convert a closed TSP loop into an open one by removing the sentinel
const sentinel = path.indexOf(points.length);
const result = [];
for (let i = sentinel + 1; i < n; i++) result.push(points[path[i]]);
for (let i = 0; i < sentinel; i++) result.push(points[path[i]]);
}
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.
