Traveling salesman problem
Travelling Salesman problemet (TSP) er et kendt problem i kombinatorisk optimering. Der forskes i problemet i operationsanalyse og datalogi.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Sa_poland_tsp.gif/220px-Sa_poland_tsp.gif)
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
redigérSpire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |