Beispiel-Problem: Traveling Salesman Problem (TSP)
Gegeben: n Städte, Entfernungsmatrix M = (mij),
mit mij Entfernung von Stadt i nach Stadt j.
Gesucht: Rundreise über alle Städte mit minimaler Länge, also Permutation p: {1,...,n} -> {1,...,n} so daß
NP-vollständig (Rechenzeit mit großer Sicherheit exponentiell)
Naiver Algorithmus: alle (n-1)! viele Reihenfolgen betrachten, wenigstens exponentielles Wachstum.
c(p) = S mp(i),p(i+1) + mp(n),p(1) minimal.