Re: My OPE & the Euclicidean TSP
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
http://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43303d1fbc
One feature I think many would find helpful is the ability to input the
graph via a GUI editor.
I decided to make this feature myself. The code is here (it's a single
file): <http://www.prism.gatech.edu/~jcranmer3/TSPTest.java>.
As a quick hack session, it has very few comments. Unfortunately, Java
6.0 only comes with the Rhino scripting engine, forcing you to put your
custom engines in JavaScript for the custom algorithm editor. If I feel
up to it, and you ask nicely, I'll put together a JAR that allows you to
use bsh (i.e., actual Java code, although I don't know how much Java 5.0
bsh can do), or at least some source code that allows you to choose from
the available languages.
The brute force algorithm is Patricia's, slightly modified to be usable
in the context of my code (i.e., the nodes is passed in as a List, not
an array). I originally copied some of the code from the Scribble.java
example, but most of that has probably been ripped out over the last few
hours, as I didn't like how it did stuff.
By the way, click the Done button in the second editor frame; do not
close it by clicking the X in the window manager decoration. Another bug
I know of is don't run stuff without any nodes in the display. You'll
get an unrecoverable error somewhere.
And yes, I am having an anonymous inner class fetish today.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth