Advertisement
Guest User

Untitled

a guest
May 21st, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. %
  2. % A Golomb ruler is a set of integers (marks) a(1) < ... < a(n) such
  3. % that all the differences a(i)-a(j) (i > j) are distinct. Clearly we
  4. % may assume a(1)=0. Then a(n) is the length of the Golomb ruler. For
  5. % a given number of marks, n, we are interested in finding the shortest
  6. % Golomb rulers. Such rulers are called optimal.
  7. %
  8. % Currently (1999), optimal rulers are known up to n=21.
  9. % See http://www.research.ibm.com/people/s/shearer/grule.html
  10. %
  11. % ECLiPSe solution by Joachim Schimpf, IC-Parc. The code is inspired
  12. % by Jean-Francois Puget and Michel Leconte's ILOG solver solution.
  13. %
  14. % N Opt Backtr Backtr Time(s)
  15. % to opt total total
  16. % 5 11 0 0 0.0
  17. % 6 17 0 3 0.0
  18. % 7 25 7 24 0.4
  19. % 8 34 45 186 3.8
  20. % 9 44 309 1013 33.4
  21. % 10 55 2797 6008 287
  22. % 11 72 15597 88764 6500
  23. % 12 85 487865 763328 75300
  24. %
  25.  
  26. :- lib(ic).
  27. :- lib(ic_global).
  28. :- lib(branch_and_bound).
  29. :- import alldifferent/1 from ic_global.
  30.  
  31. golomb(N, Xs) :-
  32. length(Xs, N), % model
  33. NN is 2^(N-1)-1,
  34. Xs :: [0..NN],
  35. once append([0|_], [Xn], Xs),
  36.  
  37. ordered(<, Xs),
  38. distances(Xs, Diffs),
  39. Diffs::[1..NN],
  40. alldifferent(Diffs),
  41. once append([D1|_], [Dn], Diffs),
  42. D1 #< Dn,
  43.  
  44. bb_min(labeling(Xs), Xn, _default). % search
  45.  
  46.  
  47. distances([], []).
  48. distances([X|Ys], D0) :-
  49. distances(X, Ys, D0, D1),
  50. distances(Ys, D1).
  51.  
  52. distances(_, [], D, D).
  53. distances(X, [Y|Ys], [Diff|D1], D0) :-
  54. Diff #= Y-X,
  55. distances(X, Ys, D1, D0).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement