Prev: Galois group of a quintic polynomial over Q
Next: Help with a (hopefully famous) quote
From: JSH on 29 Nov 2009 10:22
On Nov 28, 5:00 pm, Rotwang <sg...(a)hotmail.co.uk> wrote:
> Sorry if this appears twice, my internet connection keeps cutting out.
>
> On 28 Nov, 22:58, JSH <jst...(a)gmail.com> wrote:
>
>
>
>
>
> > On Nov 28, 10:55 am, Rotwang <sg...(a)hotmail.co.uk> wrote:
>
> > [...]
>
> > > It isn't, but that wasn't a mistake on my part: as I said, I coded
> > > what you called the "distance normalized" version of the algorithm, in
> > > which the distance between any two distinct nodes is simply set to
> > > one. Quoting from your blog:
>
> > Ok.  That makes sense now.
>
> > >   After pondering the problem I have a distance normalized TSP
> > >   algorithm, which simply assumes that the distance between every
> > >   node is a unit of 1, so with this algorithm, with m nodes, the
> > >   nodes are assumed to be in an m-1 dimensional space with a
> > >   distance of 1 from each other in that space.
>
> > > As an experiment, I also tried setting the distances equal to the
> > > costs instead, but to my surprise that worked much less often than the
> > > distance normalized version. Though in retrospect it's fairly obvious
> > > why; much of the time, having the two travellers seek to stay close to
> > > one another is actually a bad idea. Consider nodes arranged in a
> > > circle with pairs of points close to one another, but in which the
> > > pairs themselves are far apart, for example.
>
> > > > Oh, but it is amazing to me how
> > > > compact what you did present is!
>
> > > > And you say it actually got the right answer at times?
>
> > > Of course, but then an algorithm that simply returned the nodes in a
> > > random order would also get the right answer at times. In fact, your
>
> > Well yeah, that's not a surprise.
>
> > > algorithm gave the correct answer for most inputs, though the
> > > proportion it got right decreased with the number of nodes (e.g. only
> > > about 30 failures per 1000 attempts with 5 nodes, about 170 failures
>
> > Yuck.  That doesn't sound bad.  With 5 nodes, 5! = 120 possible brute
> > force paths, with 5*5 chances to match the algorithm as it is O(m^2),
> > and you have 25/120 or 20.8% success rate for random.
>
> > Which would give about 800 failures per 1000 attempts.
>
> This calculation doesn't make much sense, as far as I can tell.
> Firstly, assuming that a graph has no unusual symmetries, the
> probability of a random guess giving the optimal path is (where m is
> the number of nodes) 2/(m - 1)!. This is because the length of a path

Oh, yeah, you're right. Read over the rest and I find it convincing
to the position that my idea is no better than the greedy algorithm.

So I didn't solve the TSP problem and did not prove P=NP. Oh well.
Not a big deal.


James Harris
From: Mark Murray on 29 Nov 2009 12:53
JSH wrote:
> So I didn't solve the TSP problem and did not prove P=NP. Oh well.
> Not a big deal.

Apologies for the insults left along the way?

M
From: Peter on 29 Nov 2009 15:45
On Nov 29, 12:53 pm, Mark Murray <w.h.o...(a)example.com> wrote:
> JSH wrote:
> > So I didn't solve the TSP problem and did not prove P=NP.  Oh well.
> > Not a big deal.
>
> Apologies for the insults left along the way?
>
> M

Isn't the comedy itself sufficient?

Peter
From: Mark Murray on 29 Nov 2009 16:54
Peter wrote:
> Isn't the comedy itself sufficient?

Naah. Like James, I like dreaming.

M
From: JSH on 29 Nov 2009 18:58
On Nov 29, 12:43 pm, Peter <pwoly...(a)yahoo.com> wrote:
> On Nov 29, 10:22 am, JSH <jst...(a)gmail.com> wrote:
>
> > So I didn't solve the TSP problem and did not prove P=NP.  Oh well.
> > Not a big deal.
>
> > James Harris
>
> Such a nonchalant attiutude for a person who holds the fate of the
> entire world in his hands (giggle), although maybe, just maybe, after

Well, pity me for daring to acknowledge error!

And people wonder why it's so hard to do it?

Because nasty people will insult you for doing it, that's why.

These people simply hate. Making yourself vulnerable by acknowledging
error is an invitation to them to kick you while you are down. They
are dismal humans.

> this your 50th (or is it the 500th) unsuccessful attempt, one might be
> tempted to side with dear Uncle Al, who so poetically put it to you in

You mean the robot? What makes you think his behavior is not
predictable?

> his classic "An Ode to James Harris"

<deleted>

I've read it before.


James Harris
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Galois group of a quintic polynomial over Q
Next: Help with a (hopefully famous) quote