11 Traveling Salesman

Gegeben: G = (V,E) bewertet mit c : E$\to$$\mathbb {Z}$ .

Gesucht: Permutation der Knoten x₀,x₁,...,x_{n - 1} $\in$ V , so daß c(x_i,x_{(i + 1)$\mbox{ mod }$n}) minimal. (Billigster Rundweg (Hamiltonkreis))