Traveling salesman problem (search)

programming

Statement

Traveling salesman problem (search)

Given a list of $n$ cities $C$, a symmetric distance function $d: C \times C \rightarrow \mathbb{R}$ and a goal $g$. Is there an ordering on $C$, $c_i \in C$ with $1 \leq i \leq n$, that visits every city and has length $d(c_n, c_1) + \sum_{i=1}^{n-1} d(c_i, c_{i+1}) \leq g$ if it exists?

Solutions

Theory

Related problems