Traveling Salesman Problem

DSA · Graphs

Theory

The Traveling Salesman Problem (TSP) asks for the shortest route that visits every city exactly once and returns to the start. It is the classic NP-hard problem: the number of possible tours grows factorially, so 20 cities already have about 6 x 10^16 routes. Exact methods include brute force over permutations (O(n!)) and the Held-Karp dynamic programming algorithm, which stores the best cost for each subset of visited cities ending at each city, giving O(n^2 * 2^n). For real logistics with hundreds of stops, heuristics are used instead: nearest neighbour (always go to the closest unvisited city), 2-opt improvements that remove crossing edges, or metaheuristics such as simulated annealing. These find routes close to optimal quickly.

Why we use it

TSP models delivery routes, drilling paths on circuit boards and sequencing tasks. It is also the standard example for explaining NP-hardness and the trade-off between exact and approximate algorithms.

When to use it

Use exact DP for up to about 15-20 points. Use heuristics for larger instances where a near-optimal route is good enough.

How it works

  1. Cities with pairwise distances
  2. Few cities (<= 15)? Yes: Exact: Held-Karp DP over subsets. No: Heuristic: nearest neighbour + 2-opt.
  3. Compute the tour cost
  4. Return best tour found

Syntax

Brute force          O(n!)
Held-Karp DP         O(n^2 * 2^n)
Nearest neighbour    O(n^2)  (approximate)

Example

from itertools import permutations
from functools import lru_cache

d = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
n = len(d)

# 1. Brute force
best = min(permutations(range(1, n)), key=lambda p: sum(d[a][b] for a, b in zip((0,) + p, p + (0,))))
cost = sum(d[a][b] for a, b in zip((0,) + best, best + (0,)))
print("Brute force:", (0,) + best + (0,), cost)

# 2. Held-Karp dynamic programming
@lru_cache(maxsize=None)
def hk(mask, last):
    if mask == (1 << n) - 1:
        return d[last][0]
    return min(d[last][j] + hk(mask | 1 << j, j) for j in range(n) if not mask & 1 << j)
print("Held-Karp:", hk(1, 0))

# 3. Nearest neighbour heuristic
tour, seen = [0], {0}
while len(tour) < n:
    nxt = min((j for j in range(n) if j not in seen), key=lambda j: d[tour[-1]][j])
    tour.append(nxt); seen.add(nxt)
print("Nearest neighbour:", tour + [0], sum(d[a][b] for a, b in zip(tour, tour[1:] + [0])))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic