My OPE & the Euclicidean TSP

J

Joshua Cranmer

JSH said:
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.
 
J

JSH

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
 
J

Joshua Cranmer

JSH said:
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.
 
J

JSH

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
 
P

Patricia Shanahan

Joshua said:
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
 
J

Joshua Cranmer

JSH said:
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
 
J

JSH

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
 
J

JSH

JSH said:
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
 
P

Patricia Shanahan

JSH said:
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
 
J

JSH

...

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
 
P

Patricia Shanahan

JSH said:
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.

So why don't you just write up the relatively simple 2-D Euclidean TSP
algorithm in Java? That would convince people to help you with the rest
of your OPE ideas.

Given your claim of Java competence, and the relative shortness of your
English explanations of your algorithm, I'm going to go on assuming you
don't have a 2-D Euclidean TSP algorithm until I see it in Java.

Patricia
 
W

willo_thewisp

I was a professional Java developer.  I also have the open source
project Class Viewer for Java.
Just to clarify---you were a professional Java developer at Alltel,
in Atlanta. They fired you because you were very stupid. Remember?
 
J

Joshua Cranmer

JSH said:
JSH said:
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).

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

Even if I forgot to square (take the sqrts of the values), the result is
still the same.

38 versus 21 is a much worse regression than than 13 to 8.5, by the way.
 
J

Joshua Cranmer

JSH said:
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.

Start with what you have. Version 0.1 is better than nothing at all.

Besides, even if I release one of my projects open source from day 1, I
would write the basic framework and the first 0.* revisions mostly
myself simply because it's easiest that way.

So start the project with a simple algorithm solving Euclidean TSP.
Others who want to extend it to solve others can do so at their choosing.
 
J

JSH

So why don't you just write up the relatively simple 2-D Euclidean TSP
algorithm in Java? That would convince people to help you with the rest
of your OPE ideas.

I'm about to head off as I think I've achieved all my objectives but I
think that's an excellent question that's worth answering fully.

I have the perspective of quite a few major discoveries under my belt
where I'm waiting for the world to catch up (and it's a remarkably
slow world considering how brilliant so many people seem to think it
is). But still it has been a rather HUGE shock to have the optimal
path algorithm pop up, prove that P=NP, and solve TSP through the use
of an additional degree of freedom that is, so rather, well, simple,
and I'm trying to absorb the emotional impact as much as anything
else.

So I have a perspective that people who don't know what I already have
accomplished lack, so to you I'm just some guy mouthing off what you
see as unproven claims, but for me, I'm looking at one more discovery
kind of going, what the f***.
Given your claim of Java competence, and the relative shortness of your
English explanations of your algorithm, I'm going to go on assuming you
don't have a 2-D Euclidean TSP algorithm until I see it in Java.

Patricia

Claims of competence? Here you're off in Never-Never Land as reality
is I have the Class Viewer for Java project, and you can Google or
Yahoo! Class Viewer with or without quotes to see a dose of reality.

I must admit here is where I really find your behavior kind of
bizarre, as if the very notion that I might actually have a place in
the world of Java is distasteful to you.

One of the funnier stories to me is that Microsoft has their own
"Class Viewer" and World of Warcraft--the game if you don't know what
that is either--has their own as well, and I look at times to see if
they've taken over my #1 position in the search engine results and for
years they have not.

But at least I think (can't be sure) Microsoft has grown as for a
while I couldn't find my project listed at #1 on MSN (who knows why
really but I have my assumptions), but last time I checked, I was
there.

So my Class Viewer for Java comes up higher in search engines than
Microsoft's Class Viewer for I guess whatever it is, oh, I think
it's .NET or something and I may be silly but, pardon me, I think that
might actually signify something! Though you can of course disagree.

So as an administrator for an open source project hosted on
SourceForge which is called Class Viewer for Java, used around the
globe, and #1 for its name in the major search engines, I think I can
safely say that I more than just claim Java competence.

Whether they know me as the developer or not, people from Australia to
China to Brazil to the United States use my open source code, and what
better definitive real world test of knowing Java is there?


James Harris
 
J

JSH

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 will not give the full detailed algorithm here as I wish to simply
explain, but the gist of it is that you have TWO travelers who start
from the same node, every node is connected to every other node, and
the weight is the distance between nodes as it's the Euclidean
Traveling Salesman Problem being considered, and the two travelers
choose nodes such that they stay as physically close together as
possible where they can't choose the same node.

Oh, that's wrong.


James Harris
 
P

Patricia Shanahan

JSH said:
I'm about to head off as I think I've achieved all my objectives but I
think that's an excellent question that's worth answering fully.

I have the perspective of quite a few major discoveries under my belt
where I'm waiting for the world to catch up (and it's a remarkably
slow world considering how brilliant so many people seem to think it
is). But still it has been a rather HUGE shock to have the optimal
path algorithm pop up, prove that P=NP, and solve TSP through the use
of an additional degree of freedom that is, so rather, well, simple,
and I'm trying to absorb the emotional impact as much as anything
else.
.....

I suggest absorbing the technical impact first, and getting on with
implementing your algorithm. Don't assume your algorithm is correct
before it has been precisely specified, preferably through a runnable
implementation, and proved correct for all cases.

Patricia
 
J

JSH

JSH said:
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).
from A to B: sqrt(100+1) = sqrt(101).  So re-calculate using the
correct formulas.

Even if I forgot to square (take the sqrts of the values), the result is
still the same.

38 versus 21 is a much worse regression than than 13 to 8.5, by the way.

Oh, yeah. You're right! I gave the wrong algorithm.


James Harris
 
J

JSH

....

I suggest absorbing the technical impact first, and getting on with
implementing your algorithm. Don't assume your algorithm is correct
before it has been precisely specified, preferably through a runnable
implementation, and proved correct for all cases.

Patricia

Simpler to me if it's all incorrect. Kind of preferable.

Have you ever been on a product development team from the beginning
all the way to the end? Any idea the effort involved to get an app
out there from first steps to a full blown product?

My take on reading posts in this thread is that none of you have ever
been on major Java coding project from inception to product release as
you seem to think it's easier than it is.

I like mentioning Class Viewer because it's great for perspective
where that's a simple app, that primarily is just a middle-ware app
between Java Reflections and the coder, which just makes the raw
output from Java Reflections easier to read, and also will take you to
javadocs directly (I know suddenly sounding like a commercial but I
have a point here).

That project is not a lot of lines of code, and is a very simple
concept and it took YEARS for Class Viewer to reach its current form
though that was with me doing all the programming.

The energy investment and the time investment that you all seem to
take for granted is almost unimaginable which is what's necessary to
get to world class where your app comes up higher in search engines
than one Microsoft has of the same name or one that World of Warcraft
has of the same name.

World class.

When you people have your own major apps on the world stage that
dominate at the top of the heap then you come back to me and explain
how I should step out a major project, as then you'll have some real
world experience versus some vague notion where I think you take for
granted all these wonderful apps out there, without understanding the
pain, energy and time that all of the world class applications and
applications packages and operating systems took, from Windows to
Google to Linux, to Open Office, to Microsoft Word, all the way to my
little Class Viewer.

So don't think you can tell me how to do a major app until you tell me
what you put out the door that I can Google and see you know because
you've done SOMETHING yourself.


James Harris
 
J

Joshua Cranmer

JSH said:
My take on reading posts in this thread is that none of you have ever
been on major Java coding project from inception to product release as
you seem to think it's easier than it is.

I've never done a 1.0 release on any project, mostly because I've never
planned out any of my personal projects before starting them and I
change my mind so many times the code's unbearable. I do have several
0.* releases: a Java decompiler that I'm about to start a bottom-to-top
rewrite (with planning this time!), a TB extension that integrates
mailing lists as a new account type, as well as a python TextTwist clone.

I have also produced a full read-only database library where I had to
completely reverse engineer the database specification based on existing
code and, at one point, decompile my own code because I discovered an
undocumented "feature" of hg. How long did that take me? Not even half a
year, most of which is because I have a limited amount of time to work
on stuff and cycle all my projects. If you want to see that code, it's
here: <https://bugzilla.mozilla.org/show_bug.cgi?id=424446> (don't let
the diff part throw you off. I wrote it by starting new files and then
replacing the old ones).
That project is not a lot of lines of code, and is a very simple
concept and it took YEARS for Class Viewer to reach its current form
though that was with me doing all the programming.

1,453 lines for my database reader, 1,072 for my WIP listarchive
extension, and 6,082 for my WIP decompiler, all of which I have been
working on in the past year alone (disclaimer: this is total file size,
although much of my code is on the sparser side of comments).

A 5K LOC project should be able to make a 1.0 release within a year if
it is well laid-out beforehand, even if only one person is working on it.
The energy investment and the time investment that you all seem to
take for granted is almost unimaginable which is what's necessary to
get to world class where your app comes up higher in search engines
than one Microsoft has of the same name or one that World of Warcraft
has of the same name.

If you search for "mork reader", you will find a posting I have on the
subject as the second entry. Not bad for a project which currently only
exists as a patch to existing code.

"listarchive" brings my page up as the first result and my blog post on
the subject as the second result. Total age of project? Three months.

But something else to note is that Google results are somewhat biased.
I'm sure that hosting a project on sourceforge will put it on higher
results that hosting it on xxxfreehosting.com.

If I have an extremely WIP project and an internal library show up at
the top of the results, does that mean they're "world class"? No. It
just means that they are more visible than other projects of the same name.
So don't think you can tell me how to do a major app until you tell me
what you put out the door that I can Google and see you know because
you've done SOMETHING yourself.

Does gutting entire modules of major programs and replacing them with
working code count? 'Cause I have that covered fairly well.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top