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) ?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.