Velocity Reviews > Java > My OPE & the Euclicidean TSP

# My OPE & the Euclicidean TSP

Joshua Cranmer
Guest
Posts: n/a

 08-17-2008
JSH wrote:
> On Aug 17, 1:16 pm, Joshua Cranmer <(E-Mail Removed)> 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

JSH
Guest
Posts: n/a

 08-18-2008
On Aug 17, 4:51*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > On Aug 17, 1:16 pm, Joshua Cranmer <(E-Mail Removed)> 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.

I think Patricia Shanahan is on a far more rigorous path as she's
relying on a coding implementation, while you are clearly guessing.

I have actually ran some simple scenarios through my head to test your
own intuition about putting two close nodes at a great distance and
found your intuitive belief fails and that the algorithm behaves
perfectly. But thanks for presenting that scenario!

I believe you need to think of arcs on circles versus assuming you're
on a planar grid because you write things out like a planar grid, or
maybe just actually graph things out first versus guessing.

James Harris

Joshua Cranmer
Guest
Posts: n/a

 08-18-2008
JSH wrote:
> On Aug 17, 4:51 pm, Joshua Cranmer <(E-Mail Removed)> wrote:
>> JSH wrote:
>>> On Aug 17, 1:16 pm, Joshua Cranmer <(E-Mail Removed)> 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.

>
> I think Patricia Shanahan is on a far more rigorous path as she's
> relying on a coding implementation, while you are clearly guessing.

You're guessing just as much. Tell me where the modified table (F-B and
F-C edges at 10) is not Euclidean, or that your algorithm presents the
shortest path when starting at A.

Using the modified graph, your algorithm still selects
A->B->D->F->E->C->A (or transpose B/C and D/E to your content), while
A->B->C->D->E->F->A (or transpose B/C and D/E to your content) is still
clearly less in terms of total weight.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

JSH
Guest
Posts: n/a

 08-18-2008
On Aug 17, 5:18*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > On Aug 17, 4:51 pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> >> JSH wrote:
> >>> On Aug 17, 1:16 pm, Joshua Cranmer <(E-Mail Removed)> 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.

>
> > I think Patricia Shanahan is on a far more rigorous path as she's
> > relying on a coding implementation, while you are clearly guessing.

>
> You're guessing just as much. Tell me where the modified table (F-B and
> F-C edges at 10) is not Euclidean, or that your algorithm presents the
> shortest path when starting at A.

Euclidean TSP has distance between nodes where the nodes are actually
at that distance, so every node connection has to fit on a graph. And
it's actually supposed to be planar but I allowed that you might
consider some other surface and even higher dimensions.

So, if you're giving a Euclidean TSP example then you can get out
graph paper and actually draw out the nodes and if you use a ruler
between various nodes the distances will come out to the same as your
table.

Is is your claim that you are following those guidelines?

James Harris

Patricia Shanahan
Guest
Posts: n/a

 08-18-2008
Joshua Cranmer wrote:
> Patricia Shanahan wrote:
>> JSH wrote:
>>> A little while back I posted for a while on a creative algorithm I
>>> came up with for tracing out a path through nodes, and discussions got
>>> bogged down on the issue of whether or not it solved the TSP, where
>>> the consensus of several members was that it did not. But I have made
>>> a project for the full algorithm at Google Code for coding in java and
>>> while the welcome mat for coders has been put out, I have no
>>> responses, so I have decided to talk more about the algorithm here
>>> with the Euclidean TSP as I realized it'd be simpler to explain.

>> ...
>>
>> I don't see any need for a team project on this. Take a look at

>
>
> One feature I think many would find helpful is the ability to input the
> graph via a GUI editor.
>

Yes, but I am not going to do any more programming on this until JSH has
implemented an algorithm and shown that it works on at least my existing
test case. If he really does have an algorithm, it should not take long
to code it up in Java, or some other programming language if he does not
know enough Java.

Once that has been done, I'll consider adding more test cases as well as
features to aid in creating new ones.

Patricia

Joshua Cranmer
Guest
Posts: n/a

 08-18-2008
JSH wrote:
> Euclidean TSP has distance between nodes where the nodes are actually
> at that distance, so every node connection has to fit on a graph. And
> it's actually supposed to be planar but I allowed that you might
> consider some other surface and even higher dimensions.

The graph I gave is embeddable in 3 dimensions, but not 2. Pick an
arbitrary point A on the y-axis, with B and C in the x-axis. F would be
on the plane determined by the y and z axes, and D and E at the
intersections of the spheres. If you tweak the numbers in the right way,
you can push the graph into 2 dimensions.

So let me give you a simpler one in 2 dimensions:

A is at (0, 10)
B and C at (+/- 1, 0)
D is at (0, 9)

Your algorithm gives A->B->D->C->A, a length of 2*[sqrt(11)+sqrt(10)]
(~13), while the optimal is A->D->B->C->A, a length of
2+sqrt(11)+sqrt(10) (~8.5).

Would you like me to scan this page in and send it to you? Here's some
rough ASCII art:

A
/ \
/ D \
/_( )_\
B-------C
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

JSH
Guest
Posts: n/a

 08-18-2008
On Aug 17, 6:11*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> Joshua Cranmer wrote:
> > Patricia Shanahan wrote:
> >> JSH wrote:
> >>> A little while back I posted for a while on a creative algorithm I
> >>> came up with for tracing out a path through nodes, and discussions got
> >>> bogged down on the issue of whether or not it solved the TSP, where
> >>> the consensus of several members was that it did not. *But I have made
> >>> a project for the full algorithm at Google Code for coding in java and
> >>> while the welcome mat for coders has been put out, I have no
> >>> responses, so I have decided to talk more about the algorithm here
> >>> with the Euclidean TSP as I realized it'd be simpler to explain.
> >> ...

>
> >> I don't see any need for a team project on this. Take a look at

>
> > One feature I think many would find helpful is the ability to input the
> > graph via a GUI editor.

>
> Yes, but I am not going to do any more programming on this until JSH has
> implemented an algorithm and shown that it works on at least my existing
> test case. If he really does have an algorithm, it should not take long
> to code it up in Java, or some other programming language if he does not
> know enough Java.

I was a professional Java developer. I also have the open source
project Class Viewer for Java.

I am curious though, have you heard of it?

If not, Google Class Viewer with or without quotes. You can even us
the "Get Lucky" feature.

> Once that has been done, I'll consider adding more test cases as well as
> features to aid in creating new ones.
>
> Patricia

I have an open source project at Google Code called optimalpathengine
which brings things back full circle in an interesting round-trip path
(little TSP humor).

I haven't even started design yet.

Besides, the algorithm can be tested with the Euclidean TSP by
checking the distance between nodes from the outside in, as I
explained in other replies in this thread, and then averaging those
distances, which should be a minimum for the optimal path.

From the outside in, again means that if the path is

ABCDEFG

then you'd look at the distances between A & G, B & F, and C & D, and
ignore E as that is the 0 case anyway.

So you'd compare that with the average from ANY other path using the
same starting point, like

ACBDEGF.

James Harris

JSH
Guest
Posts: n/a

 08-18-2008
On Aug 17, 6:23*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > Euclidean TSP has distance between nodes where the nodes are actually
> > at that distance, so every node connection has to fit on a graph. *And
> > it's actually supposed to be planar but I allowed that you might
> > consider some other surface and even higher dimensions.

>
> The graph I gave is embeddable in 3 dimensions, but not 2. Pick an
> arbitrary point A on the y-axis, with B and C in the x-axis. F would be
> on the plane determined by the y and z axes, and D and E at the
> intersections of the spheres. If you tweak the numbers in the right way,
> you can push the graph into 2 dimensions.
>
> So let me give you a simpler one in 2 dimensions:
>
> A is at (0, 10)
> B and C at (+/- 1, 0)
> D is at (0, 9)
>
> Your algorithm gives A->B->D->C->A, a length of 2*[sqrt(11)+sqrt(10)]
> (~13), while the optimal is A->D->B->C->A, a length of
> 2+sqrt(11)+sqrt(10) (~8.5).

Think circles, like I said before.

It's a^2 + b^2 = c^2, so you

c = sqrt(a^2 + b^2), so...

from A to B: sqrt(100+1) = sqrt(101). So re-calculate using the
correct formulas.

James Harris

Patricia Shanahan
Guest
Posts: n/a

 08-18-2008
JSH wrote:
> On Aug 17, 6:11 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
>> Yes, but I am not going to do any more programming on this until JSH has
>> implemented an algorithm and shown that it works on at least my existing
>> test case. If he really does have an algorithm, it should not take long
>> to code it up in Java, or some other programming language if he does not
>> know enough Java.

>
> I was a professional Java developer. I also have the open source
> project Class Viewer for Java.

....

Excellent. In that case, I can safely assume you don't have a valid
algorithm until you post its Java implementation. That will save me time
trying to find counter-examples for vague descriptions and hypotheses.

Patricia

JSH
Guest
Posts: n/a

 08-18-2008
On Aug 17, 6:42*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> JSH wrote:
> > On Aug 17, 6:11 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> >> Yes, but I am not going to do any more programming on this until JSH has
> >> implemented an algorithm and shown that it works on at least my existing
> >> test case. If he really does have an algorithm, it should not take long
> >> to code it up in Java, or some other programming language if he does not
> >> know enough Java.

>
> > I was a professional Java developer. *I also have the open source
> > project Class Viewer for Java.

>
> ...
>
> Excellent. In that case, I can safely assume you don't have a valid
> algorithm until you post its Java implementation. That will save me time
> trying to find counter-examples for vague descriptions and hypotheses.
>
> Patricia

Ok. Back full circle as I have already stated that I'm looking for
coders for my OPE project where that stands for optimal path engine
which implements the full algorithm where I've simplified things for
this discussion relating to the Euclidean TSP as I think it's easier.

The full algorithm goes beyond TSP to handle nodes that do not connect
to all other nodes, so that it can even handle hubs where one node is
visited multiple times.

I'm simply talking about the TSP now as an easy frame of reference as
the full OPE goes far beyond it.

James Harris