Traveling salesman problem

En salgsmands besøg i polske byer

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.

Eksterne henvisninger

• Wikimedia Commons har flere filer relateret til Traveling salesman problem

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.