Published by Dimitris Kougioumtzis · Updated
Explore tours from vertex 0. Bound every partial route by its cost plus minimum outgoing costs for the remaining vertices; prune a bound that cannot improve the incumbent.
Enumerate routes from vertex zero while maintaining the cheapest complete tour found. Add the cheapest outgoing edge for the current end and every unvisited vertex to obtain a lower bound; discard a branch when this bound cannot beat the incumbent.
When to use Branch-and-bound traveling salesperson
Teaching exact branch-and-bound search and admissible pruning on a small directed traveling-salesperson instance.
Choosing an alternative
Held-Karp stores optimal subset states. This view searches route prefixes and prunes with an outgoing-edge lower bound; it remains factorial in the worst case.
Worked example: input and state changes
Example input
0,10,15,20;10,0,35,25;15,35,0,30;20,25,30,0
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Start at vertex 0; bounds use one minimum outgoing edge per remaining vertex.
State at this checkpoint
{ "values": [ 1, 0, 0, 0 ], "active": [ 0 ], "kind": "graph", "directed": true, "chosen": [], "visited": [ 0 ], "result": -1, "output": [ -1, -1, -1, -1, -1, 1, 0 ], "expanded": 1, "pruned": 0, "lowerBound": 0 }Step 7: Extend the partial route; lower bound 70.
State at this checkpoint
{ "values": [ 1, 2, 0, 3 ], "active": [ 3 ], "kind": "graph", "directed": true, "chosen": [ 0, 5 ], "visited": [ 0, 1, 3 ], "result": -1, "output": [ 0, 1, 2, 3, 0, 5, 0 ], "expanded": 5, "pruned": 0, "lowerBound": 70 }Step 14: Prune candidate 1: lower bound 80 cannot beat 80.
State at this checkpoint
{ "values": [ 1, 0, 2, 0 ], "active": [ 2 ], "kind": "graph", "directed": true, "chosen": [ 1 ], "visited": [ 0, 2 ], "result": -1, "output": [ 0, 1, 3, 2, 0, 7, 1 ], "expanded": 7, "pruned": 1, "lowerBound": 80 }Step 20: Extend the partial route; lower bound 70.
State at this checkpoint
{ "values": [ 1, 3, 0, 2 ], "active": [ 1 ], "kind": "graph", "directed": true, "chosen": [ 2, 10 ], "visited": [ 0, 3, 1 ], "result": -1, "output": [ 0, 1, 3, 2, 0, 10, 2 ], "expanded": 10, "pruned": 2, "lowerBound": 70 }Step 27: Optimal tour cost 80; expanded 11, pruned 4.
State at this checkpoint
{ "values": [ 1, 2, 4, 3 ], "active": [ 0 ], "kind": "graph", "directed": true, "chosen": [ 0, 5, 11, 6 ], "visited": [ 0 ], "result": 80, "output": [ 0, 1, 3, 2, 0, 11, 4 ], "expanded": 11, "pruned": 4, "lowerBound": 95 }
Expected final state
Optimal tour cost 80; expanded 11, pruned 4.
Complexity and input bounds
Family: Optimization. Time complexity: O(n! * n) worst case; n <= 7.
Implementation detail: Directed matrices have one through seven vertices, diagonal zero, -1 absent edges and costs 0..99. Downloads return the optimal cost and first lexicographic optimal cycle, plus expanded/pruned counters. Exhaustive permutation fixtures verify routes; a hand-checked case verifies that pruning actually occurs.
Space complexity: O(n) route, minimum-edge and traversal state excluding the n by n input matrix and saved frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Square 1..7 directed cost matrix, diagonal 0, -1 absent, other costs 0..99. Returns a cycle from vertex 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A lower bound may underestimate the completion but must never overestimate it. Include the return edge to zero. Missing edges and no-tour outcomes must not be confused with zero-cost edges.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Directed TSP cycle from vertex 0, square n 1..7, diagonal 0, -1 absent, off-diagonal costs 0..99. Returns optimal cost, or -1 if no Hamiltonian cycle. Output capacity n+3: first n+1 entries are the lexicographically first optimal tour including final 0 (all -1 on failure), then expanded partial routes and bound-pruned extensions. Lower bound is spent cost plus the cheapest outgoing cost for the current end and each unvisited vertex. Nonnegative costs; complete bounded search, no heuristic-only success claim. n=1 returns 0 and tour [0,0]. O(n!*n) worst-case time, O(n^2+n) input/traversal storage. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(costs, n, output) { if (n < 1 || n > 7) { return -1; } for (let i = 0; i <= n; i++) { output[i] = -1; } output[n+1] = 1; output[n+2] = 0; if (n == 1) { output[0] = 0; output[1] = 0; return 0; } let minOut = Array(256).fill(0); let path = Array(256).fill(0); let used = Array(256).fill(0); let next = Array(256).fill(0); let spent = Array(256).fill(0); let best = 1000000; let depth = 0; let candidate = 0; let edge = 0; let bound = 0; let newCost = 0; let total = 0; for (let i = 0; i < n; i++) { minOut[i] = 1000000; for (let j = 0; j < n; j++) { if (i != j && costs[i*n+j] >= 0 && costs[i*n+j] < minOut[i]) { minOut[i] = costs[i*n+j]; } } if (minOut[i] == 1000000) { return -1; } } used[0] = 1; next[0] = 1; while (depth >= 0) { if (depth == n-1) { edge = costs[path[depth]*n]; if (edge >= 0) { total = spent[depth]+edge; if (total < best) { best = total; for (let i = 0; i < n; i++) { output[i] = path[i]; } output[n] = 0; } } used[path[depth]] = 0; depth--; } else { candidate = next[depth]; next[depth]++; if (candidate == n) { used[path[depth]] = 0; depth--; } else { edge = costs[path[depth]*n+candidate]; if (used[candidate] == 0 && edge >= 0) { newCost = spent[depth]+edge; bound = newCost+minOut[candidate]; for (let i = 0; i < n; i++) { if (used[i] == 0 && i != candidate) { bound += minOut[i]; } } if (bound >= best) { output[n+2]++; } else { used[candidate] = 1; depth++; path[depth] = candidate; spent[depth] = newCost; next[depth] = 1; output[n+1]++; } } } } } if (best == 1000000) { return -1; } return best; } |
Source
Foundational branch-and-bound TSP research. The playground uses a simpler admissible minimum-outgoing-edge bound, rather than reproducing the paper reduced-cost-matrix procedure.
- An Algorithm for the Traveling Salesman Problem
J. D. C. Little; K. G. Murty; D. W. Sweeney; C. Karel (1963). Foundational branch-and-bound TSP research.