2d:null 2e:["$","title",null,{"children":"Finding a short route through points without returning back with 2-opt | Volodymyr Agafonkin | Observable"}] 33:T6d8,{ // 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]]); }34:[] 31:{"id":"3f90cd52fa5a5b1d","slug":"tsp-no-return-two-opt","title":"Finding a short route through points without returning back with 2-opt","thumbnail":"daad58cc9a35f5de2fdd9afc5ccf2f77d029c341caea4a104758227dfff14623","access_level":"public","create_time":"$D2024-03-13T11:28:33.264Z","update_time":"$D2024-03-14T12:32:12.821Z","view_time":null,"first_public_time":"$D2024-03-13T15:04:14.134Z","has_unpublished_edits":null,"fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"78f29d059906819a","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":"starter_2024","bio":"Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦"},"version":393,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"3954cddf6608132f","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":null,"bio":"Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦"}],"members":[{"type":"individual","id":"3954cddf6608132f","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":null,"role":"editor"},{"type":"team","id":"78f29d059906819a","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"6aaf02cd1aea775c","slug":"algorithms","title":"Algorithms & Math","owner":{"id":"78f29d059906819a","login":"mourner","name":"Volodymyr Agafonkin"}},"type":"notebook","body":{"titling":"auto","title":"Finding a short route through points without returning back with 2-opt","cells":[{"id":0,"value":"# Finding a short route through points without returning back with 2-opt\n\nA proof of concept for using a simple [2-opt algorithm](https://en.wikipedia.org/wiki/2-opt) to find a reasonably short route through a set of points _without returning to the starting point_ (unlike the [Traveling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem)).\n\nFound a [nice suggestion](https://stackoverflow.com/a/7158721/244789) of accomplishing this by introducing a sentinel point which has zero distance to all other points, solving the resulting TSP as usual, and then removing that sentinel from the final route. Made this notebook to test it out in practice and it works pretty well!\n\nNote that 2-opt is an approximation algorithm which doesn't guarantee an optimal route, it just gives a reasonably short one on average. It's also relatively expensive, and only reasonably fast for a modest number of points.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":82,"value":"viewof reset = Inputs.button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"points = {\n reset;\n const points = [];\n for (let i = 0; i < numPoints; i++) {\n points.push([\n Math.round(w * Math.random()),\n Math.round(h * Math.random())\n ]);\n }\n return points;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"function draw(path) {\n ctx.fillStyle = 'white';\n ctx.fillRect(0, 0, w + 2 * padding, h + 2 * padding);\n ctx.lineWidth = 1;\n ctx.beginPath();\n for (let i = 0; i < path.length; i++) {\n const k0 = path[i];\n const k1 = path[(i + 1) % path.length];\n if (k0 === points.length || k1 === points.length) continue;\n const [x0, y0] = points[k0];\n const [x1, y1] = points[k1];\n ctx.moveTo(padding + x0, padding + y0);\n ctx.lineTo(padding + x1, padding + y1);\n }\n ctx.stroke();\n ctx.fillStyle = 'red';\n const r = 4;\n for (const point of points) {\n ctx.fillRect(padding + point[0] - r, padding + point[1] - r, 2 * r, 2 * r);\n }\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"ctx = DOM.context2d(w + 2 * padding, h + 2 * padding)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":305,"value":"padding = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"numPoints = 30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"w = Math.min(width, 800)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"h = Math.ceil(w / 2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 32:"$31:body"