Traveling salesman problem

Travelling salesman problemet (TSP) eller den handelsrejsendes problem er et kendt problem i kombinatorisk optimering. Der forskes i problemet i operationsanalyse og datalogi.

En salgsmands besøg i polske byer

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.