Re: My OPE & the Euclicidean TSP
JSH wrote:
On Aug 17, 1:16 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
Time to put my visualization skills back together with graphs instead of
merely thinking about amorphous inheritance charts...
JSH wrote:
Well the first couple has moved from the starting city to two other
different cities, choosing them such that their physical distance
apart is the LEAST possible given all possible city choices, while the
other couple has gone to different cities for some other reason, so
what do we now know?
We know that the two travelers are near each other. That's about it.
Let me show you an example of where this fails. This is the weight table:
A B C D E F
A - 10 10 5 5 1
B 10 - 1 6 6 4
C 10 1 - 6 6 4
D 5 6 6 - 2 5
E 5 6 6 2 - 5
F 1 4 4 5 5 -
That should be Euclidean.
Why? If A to B is 10 and A to C is 10, then they are on an arc
centered at A, so I see you're not on a grid. But you have A to F at
1, while F to B and F to C is 4.
Ah, I forgot to check the A-F-B triangle inequality. Popping F<->B and
F<->C up to 10 should fix that without affecting the results.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth