Traveling salesman problem

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Travelling Salesman problemet (TSP) er et kendt problem i kombinatorisk optimering. Der forskes i problemet i operationsanalyse og datalogi.

Problemet formuleres som følgende: Givet en liste af byer og deres parvise afstande, er problemet at finde den korteste mulige tur der besøger alle byer præcist én gang.

Problemet er NP-komplet.

TSP minder om Hamiltonkreds-problemet.

Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.