Rudy’s OBTF Rudolf Adamkovič

Home / Computer science / Traveling salesman problem (TSP) / Computation: Python, SAT, MTZ (with NN)


Hint: Nearest neighbor heuristic

# hint (tour)
h = np.array([22, 21, 20, 24, 23, 45, 44, 43, 47, 46, 68, 67, 66, 49, 48, 51, 52, 53, 41, 42, 27, 28, 29, 30
, 18, 19, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 36, 35, 34, 33, 39, 40, 59, 58
, 57, 56, 62, 63, 61, 60, 54, 55, 50, 65, 64, 70, 71, 72, 38, 37, 31, 32, 26, 25, 3, 2, 1, 0
, 74, 75, 73, 69])

# Rotate `h` so that the city `0' is first.
h_0 = np.where(h == 0)[0][0]
h = np.roll(h, -h_0)

# edges
e = set((h[k], h[k + 1]) for k in range(len(h) - 1))
e = e.add((h[-1], h[0])) # wrap!

for i in range(n):
    for j in range(n):
        if (i, j) in e:
            model.add_hint(x[i][j], 1)
        else:
            model.add_hint(x[i][j], 0)

for k, i in enumerate(h):
    model.add_hint(t[i], k)

© 2025 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and secret alien technologies of yesteryear.