TSP & Hamiltonian — Held–Karp DP and 2-opt

Speed

Ready.

Distance matrix

How to read it

Held–Karp mode: the table is the DP. Rows are subsets mask (each must contain city 0); columns are the current end city i. A cell holds dp[mask][i] = the shortest path that starts at 0, visits exactly the cities in mask, and ends at i. Stepping fills cells from small masks to the full set, then closes the cycle with + d[i][0] to read off the optimal tour length 80 for this instance.

2-opt mode: points sit in the plane. We start from a deliberately scrambled tour and repeatedly remove two edges and reconnect them (reversing the middle segment) whenever that shortens the tour — visually, uncrossing crossings — until no improving move remains.

Keyboard

Space / → step · Enter run/pause · R reset