3e:null 3f:["$","title",null,{"children":"Held-Karp Algorithm | Andrew's Workspace | Observable"}] 45:[] 43:{"id":"0a580727a28626f6","slug":null,"title":"Held-Karp Algorithm","thumbnail":"42d1e82c79a0e8df0b30ba89e99dcf84ba64ca4ae3c27eccde00e64237087a89","access_level":"public","create_time":"$D2023-12-02T23:18:22.034Z","update_time":"$D2023-12-03T16:50:35.925Z","view_time":null,"first_public_time":"$D2023-12-18T21:16:19.375Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","bio":"","following":false},"version":226,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","role":"editor"},{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"f4aee92b58c0361a","slug":"travelling-salesperson-problem","title":"Travelling Salesperson Problem","owner":{"id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace"}},"type":"notebook","body":{"titling":"auto","title":"Held-Karp Algorithm","cells":[{"id":0,"value":"# Held-Karp Algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"viewof n = Inputs.range([1, 20], {step: 1, label: \"Number of Cities\"}); ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"R = d3.randomLcg(1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"x = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"y = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"// Now we compute distances between them (symmetric)\ndist = Array.from(Array(n), (_, i) => Array.from(Array(n), (_, j) => \n Math.hypot(x[i]-x[j], y[i]-y[j])\n));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"// Subsets of S size s\nfunction* subsets(n, k) {\n if (k == 0) {\n yield \"\".padEnd(n,\"0\");\n } else {\n if (n > k) { // We can place a zero\n for (const x of subsets(n-1,k)) {\n yield x;\n }\n }\n for (const x of subsets(n-1,k-1)) {\n yield (1<<(n-1))|x;\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"[...subsets(5,3)]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"g = Array.from(Array(n-1), () => { return {} });","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"last = {\n for (let k = 0; k < n-1; k++) {\n g[k][1< g[m][S&~(1< g[k][(1<<(n-1))-1].dist + dist[k+1][0]) {\n smallest.dist = g[k][(1<<(n-1))-1].dist + dist[k+1][0];\n smallest.last = k+1;\n }\n }\n return smallest;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"tour = {\n const result = [0];\n let set = (1<<(n-1))-1;\n let vertex = last;\n for (;;) {\n result.splice(0,0,vertex.last);\n if (result.length >= n)\n break;\n // Walk backwards to the last vertex\n let prev = vertex.last-1;\n vertex = g[vertex.last-1][set];\n set &= ~(1<<(prev));\n }\n result.splice(0,0,0);\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":196,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (let i = 0; i+1 < tour.length; i++) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[tour[i]])\n .attr(\"y1\", y[tour[i]])\n .attr(\"x2\", x[tour[i+1]])\n .attr(\"y2\", y[tour[i+1]]);\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W45","stdlib":"1"}} 44:"$43:body"