Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you're trying to solve the Traveling Sales Person problem by going over all possible paths. To do so, you have a number of computers. Each gets $(n-1)!/p$ paths to scan, where $p$ is the number of computers available. In order for each computer to know which paths it's responsible for, you have to send him an encoding of a path prefix, from which it's supposed to exhaustively scan $(n-1)!/p$ paths. The problem is, how would you calculate the size of that prefix and how would you encode it without calculating $(n-1)!$ (since it might be too large) ?

share|improve this question
1  
Incidentally, if this isn't a hypothetical question, there are faster ways to solve the Traveling Salesman problem using dynamic programming. –  Lopsy Jan 5 '13 at 16:24
    
If calculating $(n-1)!$ is hard, you don't want to try the problem this way at all. Even if $p=10^{12}$, it only takes $n=25$ to get $(n-1)!/p \approx 6\cdot 10^{11}$. I can do $24!$ on my calculator, but I can't do that many loops in any reasonable time. –  Ross Millikan Jan 5 '13 at 17:02
add comment

1 Answer

How about this: Select a starting node $a_0$ and $r>0$ such that $(n-1)\cdots(n-r)\ge p$. Then create the $(n-1)\cdots(n-r)$ sub-tasks corresponding to all choices of first $r$ steps and distribute them? In fact, if $r>2$ some pre-optimization can be recommended by checking for an optimal tour from first to last node within the selected $r+1$ nodes.

share|improve this answer
    
How would you pick $r$ such that each computer gets roughly the same number of paths to search? –  Shmoopy Jan 5 '13 at 15:53
    
It depends. You can assign each CPU either $\lfloor\frac{(n-1)\cdots(n-r)}{p} \rfloor$ subtasks or one more (ignoring the preoptimization for the moment). If this looks too wasteful (e.g. if $(n-1)\cdots(n-r)=kp+s$ with $k$ small and $s$ small nonzero) you can of course divide $s$ tasks into $(n-r-1)$ subtasks each. –  Hagen von Eitzen Jan 5 '13 at 16:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.