Re:Traveling Salesman: the most misunderstood problem
by Peaker on Saturday November 10, 2012 @05:47PM
(#4768023)
Maybe you can do something like:
A) Sort edges (descending).
B) Have a total order between N-sized subsets by treating each edge as a binary digit (1 if it is in, or 0 if it is not). I believe this guarantees that the total order between the binary numbers that correspond to edge selections is the same total order as the one between the sums of those selections.
C) Start with some first guess (e.g: 111...111000000...)
D) Binary search on the number, by adjusting each next guess to be the nearest number with N digits enabled.
I am not entirely sure, I just made this up, but I think it might work?
A) Sort edges (descending).
B) Have a total order between N-sized subsets by treating each edge as a binary digit (1 if it is in, or 0 if it is not). I believe this guarantees that the total order between the binary numbers that correspond to edge selections is the same total order as the one between the sums of those selections.
C) Start with some first guess (e.g: 111...111000000...)
D) Binary search on the number, by adjusting each next guess to be the nearest number with N digits enabled.
I am not entirely sure, I just made this up, but I think it might work?