Traveling salesman problem

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.

Traveling salesman problem 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.