In << Data Structure and Algorithm Analysis >>, turnpike reconstruction problem is given for demo of backtracking.

Suppose we are given n points, p1 , p2 , . . . , pn , located on the X -axis. Xi is the x coordinate of pi . Let us further assume that X1 = 0 and the points are given from left to right. These n points determine n ( n - 1)/2 (not necessarily unique) distances between every pair of points. It is clear that if we are given the set of points, it is easy to construct the set of distances in O ( n^2 ) time. The turnpike reconstruction problem is to reconstruct a point set from the distances. This finds applications in physics and molecular biology (see the references for pointers to more specific information). Nobody has been able to give an algorithm that is guaranteed to work in polynomial time.

I feel there is space for optimization.

Given D = [1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10]

len(D) = n(n-1)/2 = 15, so n = 6.

Let X1 = 0, X5 = 8, X6 = 10 , delete 10, 8, 2 from D. (same as book described)

Instead guess X4 = 7 or X2 = 3, separate D = A + B,

B = [(3,7),(4,6),(5,5)], ((x,y): x+y = max(D))

A = [1,2,2,3,3,5], (x,y: x+y != max(D))

If len(B) < n-3, then no solution for this problem.Luckily,it not happen here.

else if len(B) == n-3, then X2 = X(n-1) - max(A) = 3 is necessary. It happens here!

else try to fix X2 by backtracking.

After fix X2 (it means D has been separated properly), separate A = E+F

E = [(2,3),(2,3),(5)], ((x,y): x+y = max(A))

F = [1], (x,y: x+y != max(A))

If len(E) < n-3, then no solution for this problem.Luckily,it not happen here.

else try to fix X3...

If problem has no solution, then this algorithm will know it in advance most probably, no need to check every corner.

If it has solution, when search, only search in special sub-list, and has more conditions to be a sieve to stop early in a wrong direction.

I guess it should work much faster when n is big.

Could it be optimized further ?

  • $\begingroup$ Please explain or at least link to a definition of the problem. $\endgroup$ – j_random_hacker Dec 7 '17 at 18:36
  • $\begingroup$ Thanks for your kind suggestion. Hope you can optimized it further. $\endgroup$ – shen lixing Dec 8 '17 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.