Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > My OPE & the Euclicidean TSP

Reply
Thread Tools

My OPE & the Euclicidean TSP

 
 
Patricia Shanahan
Guest
Posts: n/a
 
      08-17-2008
JSH wrote:
> On Aug 17, 12:32 pm, Patricia Shanahan <(E-Mail Removed)> 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 athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...
>>
>> In it, I posted code for a simple test environment for the
>> java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem
>> that I thought would result in a suboptimal path in the algorithm as you
>> had posted it, and a brute force solver. I wrote the program during a
>> coffee break from my research, no multi-programmer, multi-day project
>> needed.

>
> Ok, I checked the link and it seems simple enough.

....
> I suggest you output the distance between two travelers with one going
> backwards along the path as I've explained previously, at each
> decision point for each of your brute force attempts.

....
> I believe I have a solution from considering phase space so am not
> interested in playing with your code, while I think it might be a
> useful exercise for you to add the second traveler to it and see what
> happens when you look over the distance between travelers as
> explained.



I don't have any travelers at all in my implementation, just a search
through the set of permutations of the nodes starting with a given node.
That makes it hard to add a "second traveler".

In any case, my implementation of solve() is interesting only for
verifying that a claimed solution to a non-trivial problem is actually
optimal.

Also, note that there are 11!, 39,916,800, Hamiltonian cycles
considering a single start node in my twelve node case. I do prune the
search space whenever the current permutation prefix has a higher cost
than the best Hamiltonian cycle so far, but I would not expect that to
help enough to make decision-by-decision output useful.

The important thing is your Java implementation of your algorithm. All
you need to do is replace my solve() with a method representing it. The
rest of the code is useful for enabling identical problem specifications
for your algorithm and the brute force method.

Patricia
 
Reply With Quote
 
 
 
 
willo_thewisp@hotmail.com
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 5:19*pm, JSH <(E-Mail Removed)> wrote:
>
> 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. *
>
>

James, your stupidity truly is a natural wonder.
 
Reply With Quote
 
 
 
 
JSH
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 3:24*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> JSH wrote:
> > On Aug 17, 12:32 pm, Patricia Shanahan <(E-Mail Removed)> 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 athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...

>
> >> In it, I posted code for a simple test environment for the
> >> java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem
> >> that I thought would result in a suboptimal path in the algorithm as you
> >> had posted it, and a brute force solver. I wrote the program during a
> >> coffee break from my research, no multi-programmer, multi-day project
> >> needed.

>
> > Ok, I checked the link and it seems simple enough.

> ...
> > I suggest you output the distance between two travelers with one going
> > backwards along the path as I've explained previously, at each
> > decision point for each of your brute force attempts.

> ...
> > I believe I have a solution from considering phase space so am not
> > interested in playing with your code, while I think it might be a
> > useful exercise for you to add the second traveler to it and see what
> > happens when you look over the distance between travelers as
> > explained.

>
> I don't have any travelers at all in my implementation, just a search
> through the set of permutations of the nodes starting with a given node.
> That makes it hard to add a "second traveler".


You just take an outputted path and output the distance between nodes
going from the outside in, for example if the path is

ABCDEF

then you'd output distances between A & F, B & E, and C & D.

If you had

ABCDEFG

you'd output distances between A & G, B & F, and C & E, as with the
algorithm, either traveler can move to E, so the algorithm exits after
C & E.

> In any case, my implementation of solve() is interesting only for
> verifying that a claimed solution to a non-trivial problem is actually
> optimal.
>
> Also, note that there are 11!, 39,916,800, Hamiltonian cycles
> considering a single start node in my twelve node case. I do prune the
> search space whenever the current permutation prefix has a higher cost
> than the best Hamiltonian cycle so far, but I would not expect that to
> help enough to make decision-by-decision output useful.


That's the intuitive feel, but no other algorithm uses a global
variable because none exists without additional degrees of freedom.

My algorithm unlike others uses local decisions with a GLOBAL
variable.

> The important thing is your Java implementation of your algorithm. All
> you need to do is replace my solve() with a method representing it. The
> rest of the code is useful for enabling identical problem specifications
> for your algorithm and the brute force method.
>
> Patricia


You were arguing against the need for a multi-team effort to code my
full optimal path algorithm based on code you stated you wrote on your
coffee break.

I merely noted how you could advance that code a little further to
directly test this approach, and explained why I don't see a need to
do so myself because of a phase space argument.

I've further explained how you can simply do the addition after you
noted you didn't have travelers in your code, where I gave you a
specific example for how you output the desired information, giving
the phase space results.

To me it's about a solution that I can see which is counter-intuitive
to people who have a serious intellectual investment in different
beliefs, like your learned response that local decisions can't matter
globally with the TSP.

I'd gain little by using your code to prove something I feel I already
know by other means, but you'd gain much more by making the addition
to your code to quickly and easily see how your intuition is wrong.

It shouldn't take as long as you took to do the original code, which
you said you did on a coffee break.


James Harris
 
Reply With Quote
 
kenny.riodan@gmail.com
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 10:40*pm, JSH <(E-Mail Removed)> wrote:
>
> On Aug 17, 3:24*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> > ...

>
> I'd gain little by using your code to prove
> something I feel I already know...


What Patricia is trying to say, in her very modest and polite way,
is that it's obvious to all of us that your algorithm doesn't work.
By using her framework, you can at least input a test case and see
that
your algorithm produces a lousy solution, and you can then
compare and see the error of your way.

> I'd gain little by using your code to prove
> something I feel I already know...


On the contrary, you have a lot to gain.
Having a scientific test bench allows you to (potentially) prove that
your algorithm truly works on all the test cases people throw at you.
You will then have great credibility and people will have no choice
but to take you very seriously.

You're either delusional (and truly believe that you alone knows how
to solve NP problem in P time), or you subconsciously are trying to
avoid
facing your own stupidity and thus you push away all the people trying
to help you.
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 3:49*pm, "(E-Mail Removed)" <(E-Mail Removed)>
wrote:
> On Aug 17, 10:40*pm, JSH <(E-Mail Removed)> wrote:
>
>
>
> > On Aug 17, 3:24*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> > > ...

>
> > I'd gain little by using your code to prove
> > something I feel I already know...

>
> What Patricia is trying to say, in her very modest and polite way,
> is that it's obvious to all of us that your algorithm doesn't work.
> By using her framework, you can at least input a test case and see
> that
> your algorithm produces a lousy solution, and you can then
> compare and see the error of your way.


All of us? So you speak for every member of the entire group
worldwide?

That is a sign of delusional thinking on your part.

And I disagree with you. Disproof by counter to your assertion.

> > I'd gain little by using your code to prove
> > something I feel I already know...

>
> On the contrary, you have a lot to gain.
> Having a scientific test bench allows you to (potentially) prove that
> your algorithm truly works on all the test cases people throw at you.
> You will then have great credibility and people will have no choice
> but to take you very seriously.


Nope. In my experience people simply ignore such data to hold on to
their own view, or look around to see if someone else will do
something, which I know from my prime counting function.

It's better to get people to do things themselves or they tend to walk
away from painful results, like information that forces them to
discount knowledge they previously worked hard to attain.

> You're either delusional (and truly believe that you alone knows how
> to solve NP problem in P time), or you subconsciously are trying to
> avoid
> facing your own stupidity and thus you push away all the people trying
> to help you.


I'm not pushing anyone away. I'm simply not taking non-optimal paths,
which I know from past experience do not work.

You on the other hand have been rather insulting as well as delusional
in your global statement of agreement from all readers worldwide of
this newsgroup as if you were an uber-mind with access to all.

Are you claiming to be God?


James Harris
 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      08-17-2008
JSH wrote:
> On Aug 17, 3:24 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
>> JSH wrote:
>>> On Aug 17, 12:32 pm, Patricia Shanahan <(E-Mail Removed)> 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 athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...
>>>> In it, I posted code for a simple test environment for the
>>>> java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem
>>>> that I thought would result in a suboptimal path in the algorithm as you
>>>> had posted it, and a brute force solver. I wrote the program during a
>>>> coffee break from my research, no multi-programmer, multi-day project
>>>> needed.
>>> Ok, I checked the link and it seems simple enough.

>> ...
>>> I suggest you output the distance between two travelers with one going
>>> backwards along the path as I've explained previously, at each
>>> decision point for each of your brute force attempts.

>> ...
>>> I believe I have a solution from considering phase space so am not
>>> interested in playing with your code, while I think it might be a
>>> useful exercise for you to add the second traveler to it and see what
>>> happens when you look over the distance between travelers as
>>> explained.

>> I don't have any travelers at all in my implementation, just a search
>> through the set of permutations of the nodes starting with a given node.
>> That makes it hard to add a "second traveler".

>
> You just take an outputted path and output the distance between nodes
> going from the outside in, for example if the path is
>
> ABCDEF
>
> then you'd output distances between A & F, B & E, and C & D.
>
> If you had
>
> ABCDEFG
>
> you'd output distances between A & G, B & F, and C & E, as with the
> algorithm, either traveler can move to E, so the algorithm exits after
> C & E.


OK, that is doable:

Best Score 32.0000
Best Cycle: A W H G Z F E Y D C X B A
Elapsed time: 3.66239 seconds
Distance A to B = 2.00000
Distance W to X = 2.00000
Distance H to C = 8.00000
Distance G to D = 8.00000
Distance Z to Y = 2.00000
Distance F to E = 2.00000

It seems to be rather sensitive to which node I start at. Here are the
results starting at G, without changing the coordinates of any point:

Best Score 32.0000
Best Cycle: G H W A B X C D Y E F Z G
Elapsed time: 3.87479 seconds
Distance G to Z = 3.00000
Distance H to F = 5.83095
Distance W to E = 5.38516
Distance A to Y = 5.38516
Distance B to D = 5.83095
Distance X to C = 3.00000

What is this supposed to tell me? Looking only at one optimal path makes
it hard to pick out features that are related to being optimal.

Patricia
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 4:00*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> JSH wrote:
> > On Aug 17, 3:24 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> >> JSH wrote:
> >>> On Aug 17, 12:32 pm, Patricia Shanahan <(E-Mail Removed)> 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 athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...
> >>>> In it, I posted code for a simple test environment for the
> >>>> java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem
> >>>> that I thought would result in a suboptimal path in the algorithm as you
> >>>> had posted it, and a brute force solver. I wrote the program during a
> >>>> coffee break from my research, no multi-programmer, multi-day project
> >>>> needed.
> >>> Ok, I checked the link and it seems simple enough.
> >> ...
> >>> I suggest you output the distance between two travelers with one going
> >>> backwards along the path as I've explained previously, at each
> >>> decision point for each of your brute force attempts.
> >> ...
> >>> I believe I have a solution from considering phase space so am not
> >>> interested in playing with your code, while I think it might be a
> >>> useful exercise for you to add the second traveler to it and see what
> >>> happens when you look over the distance between travelers as
> >>> explained.
> >> I don't have any travelers at all in my implementation, just a search
> >> through the set of permutations of the nodes starting with a given node.
> >> That makes it hard to add a "second traveler".

>
> > You just take an outputted path and output the distance between nodes
> > going from the outside in, for example if the path is

>
> > ABCDEF

>
> > then you'd output distances between A & F, B & E, and C & D.

>
> > If you had

>
> > ABCDEFG

>
> > you'd output distances between A & G, B & F, and C & E, as with the
> > algorithm, either traveler can move to E, so the algorithm exits after
> > C & E.

>
> OK, that is doable:
>
> Best Score 32.0000
> Best Cycle: A W H G Z F E Y D C X B A
> Elapsed time: 3.66239 seconds
> Distance A to B = 2.00000
> Distance W to X = 2.00000
> Distance H to C = 8.00000
> Distance G to D = 8.00000
> Distance Z to Y = 2.00000
> Distance F to E = 2.00000
>
> It seems to be rather sensitive to which node I start at. Here are the
> results starting at G, without changing the coordinates of any point:


Hmmm...my hypothesis was that with the Euclidean TSP it wouldn't
matter which node was the start...

> Best Score 32.0000
> Best Cycle: G H W A B X C D Y E F Z G
> Elapsed time: 3.87479 seconds
> Distance G to Z = 3.00000
> Distance H to F = 5.83095
> Distance W to E = 5.38516
> Distance A to Y = 5.38516
> Distance B to D = 5.83095
> Distance X to C = 3.00000
>
> What is this supposed to tell me? Looking only at one optimal path makes
> it hard to pick out features that are related to being optimal.
>
> Patricia


Oh, you just compare with any other non-optimal paths. The distances
along an optimal path should be less at each decision point from the
outside in, so like with

ABCDEFG

versus

BCDEFGA

you'd compare A & G from the first to B & A from the second and so
forth, and if the first is the optimal path, then at each such
comparison you'd find the distance is shorter.

That's it. It's that simple. If I'm wrong that is not true.


James Harris
 
Reply With Quote
 
Kenny Riodan
Guest
Posts: n/a
 
      08-17-2008
JSH wrote:
> > What Patricia is trying to say, in her very modest and polite way,
> > is that it's obvious to all of us that your algorithm doesn't work.

>
> All of us? So you speak for every member of the entire group
> worldwide?


I certainly did not (and do not) speak for every member of this
newsgroup.
It's this kind of logical fallacy that you're exhibiting time and time
again
in your flawed reasoning.

I meant me and several people who have pointed out
that it has been proven that local optimal prefixes are not
guaranteed to be part of the global optimal solution.

> > On the contrary, you have a lot to gain...

>
> Nope. In my experience people simply ignore such data...


That is not the case here. Each time, you revise your algorithm,
and several people almost immediately produce a counterexample
showing that your algorithm is not optimal.

Several people here produce data.
You're the ony who "simply ignore such data".
You're the one standing against progress.
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-17-2008
On Aug 17, 4:06*pm, JSH <(E-Mail Removed)> wrote:
> On Aug 17, 4:00*pm, Patricia Shanahan <(E-Mail Removed)> wrote:
>
>
>
> > JSH wrote:
> > > On Aug 17, 3:24 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> > >> JSH wrote:
> > >>> On Aug 17, 12:32 pm, Patricia Shanahan <(E-Mail Removed)> 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 athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...
> > >>>> In it, I posted code for a simple test environment for the
> > >>>> java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem
> > >>>> that I thought would result in a suboptimal path in the algorithm as you
> > >>>> had posted it, and a brute force solver. I wrote the program during a
> > >>>> coffee break from my research, no multi-programmer, multi-day project
> > >>>> needed.
> > >>> Ok, I checked the link and it seems simple enough.
> > >> ...
> > >>> I suggest you output the distance between two travelers with one going
> > >>> backwards along the path as I've explained previously, at each
> > >>> decision point for each of your brute force attempts.
> > >> ...
> > >>> I believe I have a solution from considering phase space so am not
> > >>> interested in playing with your code, while I think it might be a
> > >>> useful exercise for you to add the second traveler to it and see what
> > >>> happens when you look over the distance between travelers as
> > >>> explained.
> > >> I don't have any travelers at all in my implementation, just a search
> > >> through the set of permutations of the nodes starting with a given node.
> > >> That makes it hard to add a "second traveler".

>
> > > You just take an outputted path and output the distance between nodes
> > > going from the outside in, for example if the path is

>
> > > ABCDEF

>
> > > then you'd output distances between A & F, B & E, and C & D.

>
> > > If you had

>
> > > ABCDEFG

>
> > > you'd output distances between A & G, B & F, and C & E, as with the
> > > algorithm, either traveler can move to E, so the algorithm exits after
> > > C & E.

>
> > OK, that is doable:

>
> > Best Score 32.0000
> > Best Cycle: A W H G Z F E Y D C X B A
> > Elapsed time: 3.66239 seconds
> > Distance A to B = 2.00000
> > Distance W to X = 2.00000
> > Distance H to C = 8.00000
> > Distance G to D = 8.00000
> > Distance Z to Y = 2.00000
> > Distance F to E = 2.00000

>
> > It seems to be rather sensitive to which node I start at. Here are the
> > results starting at G, without changing the coordinates of any point:

>
> Hmmm...my hypothesis was that with the Euclidean TSP it wouldn't
> matter which node was the start...
>
> > Best Score 32.0000
> > Best Cycle: G H W A B X C D Y E F Z G
> > Elapsed time: 3.87479 seconds
> > Distance G to Z = 3.00000
> > Distance H to F = 5.83095
> > Distance W to E = 5.38516
> > Distance A to Y = 5.38516
> > Distance B to D = 5.83095
> > Distance X to C = 3.00000

>
> > What is this supposed to tell me? Looking only at one optimal path makes
> > it hard to pick out features that are related to being optimal.

>
> > Patricia

>
> Oh, you just compare with any other non-optimal paths. *The distances
> along an optimal path should be less at each decision point from the
> outside in, so like with
>
> ABCDEFG
>
> versus
>
> BCDEFGA


Sorry. That's wrong.

You have to have the same starting node, so a better example would be:

ABCDEFG

versus

ACBDEGF

> you'd compare A & G from the first to B & A from the second and so
> forth, and if the first is the optimal path, then at each such
> comparison you'd find the distance is shorter.


And that's wrong as well. You'd add all the distances together and
get the average, and compare averages between different paths.

Sorry but I made a quick reply before, without thinking it all through
carefully and realized later I was wrong.

> That's it. *It's that simple. *If I'm wrong that is not true.


Um, sorry about changing criteria midstream but this research is all
new.

I'm figuring things out as I go along.

Main change is to compare apples to apples versus apples to oranges as
with the original criteria you could have the same optimal path with
different starting points along it and get a contradiction.


James Harris

 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      08-17-2008
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....1bbb43303d1fbc


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

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

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
how can i get particular datafrom #<Net::HTTP google.co ope Priyank Shah Ruby 2 09-14-2010 04:51 AM
My TSP idea, google code and google group, thanks! JSH Java 0 08-03-2008 05:43 PM
Distance normalized TSP algorithm JSH Java 18 07-27-2008 03:31 AM
Richard Heathfield's TSP permutation algorithm whitehatmiracle@gmail.com C Programming 12 09-22-2006 10:12 AM
How to get CiscoIOSTSP3.1.zip (TSP Light TAPI driver)? Cisco 0 06-18-2005 08:19 AM



Advertisments