All Questions
Tagged with pr.probability traveling-salesman-problem
2 questions
11
votes
1
answer
836
views
Generalized Euclidean TSP
Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that ...
1
vote
1
answer
173
views
Could you provide some TSP examples from real world to test a new algorithm?
It's well known that to find a hamilton cycle is NPC, while TSP is NPH.
But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...