Traveling Salesman — the poster problem

The most famous NP-complete problem in the world. Real solvers are mature; build them yourself only if you have a reason.

1. 01
   Held-Karp dynamic programming for up to about twenty cities — bitmask the visited set, memoize on (last-city, set). The work is n² · 2ⁿ, fast for n ≤ 20 and infeasible beyond. Past that, switch to LKH via FFI or hand the problem to Vroom.

   fn tsp_held_karp(dist: &[Vec<u32>]) -> u32 {
       let n = dist.len();
       assert!(n <= 20, "use LKH or a SaaS for n > 20");
       let mut dp = vec![vec![u32::MAX; n]; 1 << n];
       dp[1][0] = 0;
       for mask in 1u32..(1 << n) {
           for last in 0..n {
               if (mask >> last) & 1 == 0 || dp[mask as usize][last] == u32::MAX { continue; }
               for next in 0..n {
                   if (mask >> next) & 1 == 1 { continue; }
                   let m = (mask | (1 << next)) as usize;
                   let cand = dp[mask as usize][last].saturating_add(dist[last][next]);
                   if cand < dp[m][next] { dp[m][next] = cand; }
               }
           }
       }
       let full = (1 << n) - 1;
       (1..n).map(|i| dp[full][i].saturating_add(dist[i][0])).min().unwrap()
   }

2. 02
   vec![vec![u32::MAX; n]; 1 << n] allocates a two-dimensional table in one line. The vec! macro has two forms: vec![1, 2, 3] is the literal version (explicit list of elements), and vec![value; count] is the repeat form — produces a Vec of count copies of value. Nesting the repeat form gives a rectangular table: the inner vec![u32::MAX; n] is a row of n "infinity" entries; the outer vec![row; 1 << n] makes 1 << n copies of that row, one per possible subset of cities. u32::MAX is the largest u32 value (about 4.3 billion) and serves as the "unreached / infinity" sentinel — any real distance will be smaller, so reading MAX from the table reliably means "no path lands in this state yet." 1 << n is the bit-shift expression for 2 to the power n — for the Held-Karp DP it is the count of all possible subsets of n cities.

   // vec! macro — two forms:
   let xs = vec![1, 2, 3];               // literal: explicit elements
   let ys = vec![0u32; 5];               // repeat:  five copies of 0u32
   //      ──────────  ─
   //                  ↑    ↑
   //                value  count
   
   // Nesting the repeat form makes a rectangular table:
   let dp: Vec<Vec<u32>> = vec![vec![u32::MAX; n]; 1 << n];
   //                           ──────────────  ────────
   //                           inner row:       outer:
   //                           n × u32::MAX     (1 << n) copies of the row
   //
   // Shape: (1 << n) rows  ×  n columns,  every entry u32::MAX.
   
   
   // u32::MAX as the sentinel "unreached / infinity":
   //
   //   u32::MAX  =  4_294_967_295        the largest u32 value
   //
   // Any real distance fits inside u32, so MAX safely means "no path yet."
   // .saturating_add() (used elsewhere in the function) keeps the sum
   // pinned at MAX instead of wrapping around.
   
   
   // 1 << n is left bit-shift — equivalent to 2.pow(n):
   //
   //   1 << 0  =  1                       0b00000001  =  2⁰
   //   1 << 1  =  2                       0b00000010  =  2¹
   //   1 << 2  =  4                       0b00000100  =  2²
   //   1 << 3  =  8                       0b00001000  =  2³
   //   1 << 4  = 16                       0b00010000  =  2⁴
   //   1 << n  = 2ⁿ
   //
   // Why 2ⁿ?  Each of n cities is either visited or not — exactly 2ⁿ
   // possible subsets.  The DP indexes one row per subset.
   
   
   // Memory footprint blows up:
   //   n = 10  →    1 024 × 10 × 4 bytes  =    40 KB
   //   n = 15  →   32 768 × 15 × 4 bytes  =   1.9 MB
   //   n = 20  →    1 M  × 20 × 4 bytes   =    80 MB
   //   n = 25  →    32 M × 25 × 4 bytes   =   3.2 GB
   //
   // The exponential explosion is why Held-Karp tops out around n = 20.
   // Past that, even storing the table runs out of memory.

3. 03
   The mask variable is a single u32 whose bits encode a subset of cities. Bit i is set if city i has been visited. This is the standard trick for representing subsets when there are at most about 64 elements — one machine word holds the whole subset, and bitwise operations let you test, add, and remove elements in a single CPU instruction. Four operations carry the entire encoding. 1 << k is a mask with only bit k set. mask | (1 << k) adds city k to the subset. (mask >> k) & 1 reads the value of bit k — right-shift slides bit k down to position 0, then & 1 masks every other position away, leaving 0 or 1. (1 << n) - 1 is the "all cities" mask: bit n set, then minus one, gives bits 0..n-1 all set. Subsets-as-bitmasks is the canonical encoding in performance-sensitive code whenever the universe is small (≤ 64 elements). Past that, switch to BTreeSet or HashSet.

   // Encoding a subset as bits in a u32.  Bit i = "city i has been visited."
   //
   //   Cities {0, 2, 3}     →    00001101    (bits 0, 2, 3 set)
   //                              = 13 in decimal
   
   
   // Read bit k:  (mask >> k) & 1
   let mask: u32 = 0b00001101;            // {0, 2, 3}
   (mask >> 0) & 1;                        // 1   ← city 0 IS in the subset
   (mask >> 1) & 1;                        // 0   ← city 1 is NOT
   (mask >> 2) & 1;                        // 1   ← city 2 IS in
   (mask >> 3) & 1;                        // 1   ← city 3 IS in
   //
   // Visual for (mask >> 2) & 1:
   //
   //   mask           00001101
   //   >> 2           00000011    shift right by 2 — bit we want is now at position 0
   //   & 1            00000001    mask everything else away
   //   result         1
   
   
   // Set bit k:  mask | (1 << k)
   let mask: u32 = 0b00001101;            // {0, 2, 3}
   let with_5    = mask | (1 << 5);        // {0, 2, 3, 5}
   //
   //   mask           00001101
   //   1 << 5         00100000    a mask with only bit 5 set
   //   | (or)         00101101    bit 5 added; everything else unchanged
   
   
   // Clear bit k:  mask & !(1 << k)       (not used on page 25 — still worth knowing)
   let mask: u32 = 0b00001101;            // {0, 2, 3}
   let without_2 = mask & !(1 << 2);       // {0, 3}
   
   
   // The "all of them" mask:  (1 << n) - 1
   //
   //   1 << 4           00010000     bit 4 set
   //   (1 << 4) - 1     00001111     bits 0, 1, 2, 3 all set  →  full subset {0,1,2,3}
   
   
   // Page 25 uses these four operations in the inner DP loop:
   //
   //   (mask >> last) & 1 == 0       "if last is NOT in mask, skip this state"
   //   (mask >> next) & 1 == 1       "if next IS in mask, skip — can't revisit"
   //   mask | (1 << next)            "extended subset including next"
   //   (1 << n) - 1                  "full subset — all n cities visited"
   //
   // Reach for bitmasks whenever the universe has at most about 64 elements.
   // Past that (a single u64 can't hold the subset), use BTreeSet or HashSet.