Re: JSH: My optimal path idea, solution to TSP?
Joshua Cranmer
> But I would add also as an aside that it is fascinating that the
> poster is noting a case of failure as an outlier if you read the post
> to which he is linking, as usually his implementation he claims was
> actually succeeding. Wild if true.
>
> Way wild as he went up to 10 nodes. So 10! possible paths.
10 nodes is typically not terribly interesting in graph theory problems,
as the problems in greedy algorithms only manifest themselves in
pathological cases in such small graphs. Indeed, 10! possible paths is
so small as to make brute forcing a simple, logical solution (probably
why he chose to look at such small graphs: the brute force is a viable
metric to measure TSP against).
The real-world uses of this problem have graph sizes in the 000's of
nodes. Reading Wikipedia, it seems there exists, for TSP in metric
spaces, a polynomial-time approximation algorithm which gets you a path
at most 2x the optimal.
This is the pseudo-code for said algorithm (courtesy of Wikipedia):
* Construct the minimum spanning tree.
* Duplicate all its edges. That is, wherever there is an edge from u to
v, add a second edge from u to v. This gives us an Eulerian graph.
* Find a Eulerian cycle in it. Clearly, its length is twice the length
of the tree.
* Convert the Eulerian cycle into the Hamiltonian one in the following
way: walk along the Eulerian cycle, and each time you are about to come
into an already visited vertex, skip it and try to go to the next one
(along the Eulerian cycle).
In runtime, assuming complete graphs (E = V^2), that's:
1. O(V^2) (Prim's algorithm for MST, adjacency matrix)
2. O(V) to duplicate edges (MST has V - 1 edges)
3. O(V) to find a Eulerian cycle (O(E) algorithm on the MST, it's quite
simple).
4. O(V) to convert to Hamiltonian tour.
In all, that's an O(V^2) algorithm to find a Hamiltonian tour that is at
most twice as expensive as the optimal. Heck, the limiting factor is
finding a minimum spanning tree, everything else is O(V), so I don't
even need to assume a complete graph.
If your algorithm can find a guaranteed significantly more accurate
result in a reasonable runtime, then it might be interesting.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
sanboz
"JSH" <jst...@gmail.com> wrote in message
news:8cf6ecb2-5f97-4b26...@u8g2000prd.googlegroups.com...
>A while back I came up with an approach to the Traveling Salesman
> Problem which was resoundingly panned on this newsgroup, from one
> poster who proudly and repeatedly claimed it just did not work, to
> others who challenged the assertion that I'd even really given an
> approach!
it dosent work, you have never proved it work. End of story.
>
<snip crap>
> I am challenging their authority and intimating that they lead "their
> group" down the wrong path, so they are "bad people" who are also
> inferior as to their real knowledge and dangerous to people who trust
> them. That assertion should lead to a response.
you cannot challange their authority, you state you are not a mathematician,
so f*ck off.
>
>
> James Harris
JSH
> On 29 Nov, 02:54, JSH <jst...@gmail.com> wrote:
>
> > On Nov 28, 5:00 am, Rotwang <sg...@hotmail.co.uk> wrote:
>
> > [...]
>
> > >http://groups.google.co.uk/group/sci.physics/msg/ee792022c2a95bd5
>
> > Google Groups is slow in displaying new posts so I'm stuck with
> > replying again to this one, and actually wouldn't mind if "Rotwang"
> > would post his Python code on this newsgroup, as it might be better
> > appreciated here than on sci.physics and sci.math as this newsgroup
> > has more expertise in that direction.
>
> Sure. The code is reproduced below. For the results of tests, and some
> explanation of the implementation for those unfamiliar with Python,
> see the above GG link, as well as the following:
>
> http://groups.google.co.uk/group/sci.math/msg/93eaffa45999556ehttp://groups.google.co.uk/group/sci.math/msg/93a8ce4532c48df9
>
> The function takes as input a list G of lists, in which each element
> of G is assumed to have the same length as G itself; G[i][j] is the
> cost of travelling from node i to node j, where nodes are labelled by
> integers from 0 to len(G) - 1. It outputs a tuple with two elements,
> the first being a list which is the path found by the algorithm, and
> the second being the total cost of said path. Here it is:
>
> def tsj(G):
> n = range(len(G))
> T = []
> for i in n:
> T1 = [i]
> T2 = [i]
> m = [j for j in n if j != i]
> while len(m) > 1:
> c1 = []
> for j in m:
> c2 = []
> for k in m:
> if j != k:
> c2.append([k,G[T1[-1]][j]*G[T2[0]][k]])
> r = 0
> for q in xrange(1,len(c2)):
> if c2[q][1] < c2[r][1]:
> r = q
> c1.append([j,c2[r][0],c2[r][1]])
> r = 0
> for q in xrange(1,len(c1)):
> if c1[q][2] < c1[r][2]:
> r = q
> T1 = T1 + [c1[r][0]]
> T2 = [c1[r][1]] + T2
> m.remove(T1[-1])
> m.remove(T2[0])
> S = T1 + m + T2
> T.append([S,sum([G[S[j]][S[(j+1)]] for j in n])])
> r = 0
> for q in xrange(1,len(G)):
> if T[q][1] < T[r][1]:
> r = q
> return [T[r][0][i] for i in n],T[r][1]
The poster's claim, including posts he's made on sci.physics and
sci.math, is that he has programmed my algorithm in what I call its
distance normalized form, which means all nodes are a unit length from
each other, so only cost decides the optimal path. Further he says
that it performs only slightly better than the greedy algorithm.
If true then my position is thoroughly debunked that I've solved the
TSP. I don't see any reason to think he's wrong at this point, so I'd
lean towards accepting the debunking. Which would mean as well that
Joshua Cranmer was right in criticizing this approach.
James Harris
Rotwang
> On Nov 28, 7:35 pm, Rotwang <sg...@hotmail.co.uk> wrote:
>
>
> The poster's claim, including posts he's made on sci.physics and
> sci.math, is that he has programmed my algorithm in what I call its
> distance normalized form, which means all nodes are a unit length from
> each other, so only cost decides the optimal path. Further he says
> that it performs only slightly better than the greedy algorithm.
That's not quite true - as I mentioned in the other thread, the
difference in performance between your algorithm and the greedy
algorithm was bigger when I tested them on graphs with fewer than 10
nodes. I have no idea how they fare against graphs with more than 10
nodes, since the only means I have of checking the answers is to solve
the problem by brute force, which is already pretty slow with 10
nodes. Even if your algorithm is significantly better than the greedy
one, though, it's still a long way from being a reliable solution to
the problem.
Anyway, since you're apparently willing to give my claims the time of
day at the moment, perhaps you'd like to have a look at the proof I
posted a while back, concerning your prime counting formula:
http://groups.google.co.uk/group/sci.math/msg/75c9764c71dfdee8
JSH
> On 29 Nov, 15:31, JSH <jst...@gmail.com> wrote:
>
> > On Nov 28, 7:35 pm, Rotwang <sg...@hotmail.co.uk> wrote:
>
> > [...]
>
> > The poster's claim, including posts he's made on sci.physics and
> > sci.math, is that he has programmed my algorithm in what I call its
> > distance normalized form, which means all nodes are a unit length from
> > each other, so only cost decides the optimal path. Further he says
> > that it performs only slightly better than the greedy algorithm.
>
> That's not quite true - as I mentioned in the other thread, the
> difference in performance between your algorithm and the greedy
> algorithm was bigger when I tested them on graphs with fewer than 10
> nodes. I have no idea how they fare against graphs with more than 10
<deleted>
Irrelevant. The idea is trashed. Consider the approach gone.
>
> Anyway, since you're apparently willing to give my claims the time of
Your claims here appear to be valid.
> day at the moment, perhaps you'd like to have a look at the proof I
> posted a while back, concerning your prime counting formula:
Irrelevant. Don't be greedy. Take your victory here.
My claims on TSP are ended. I've trashed the algorithm I had, so it's
gone.
End of story.
James Harris
Mark Murray
James don't be a coward.
M
Jym
> My claims on TSP are ended. I've trashed the algorithm I had, so it's
> gone.
The very disturbing things about it is that it still comes as #2 on a
google search for optimal path algorithm (just after some guy named
Dijkstra). Or #1 if you add quotes around the serach. I'm pretty worried
of what that means concerning your claims on other searches where you come
#1 or #2 (such as define mathematical proof, solvind binary quadratic
diophantine equations and such).
--
Hypocoristiquement,
Jym.
Mark Murray
I'm confused about that too.
It's not like it suddenly became rubbish (JSH's TSP algorithm, I mean);
either it was always rubbish or it was always OK. As JSH has now declared
it rubbish (my words), it must have always been so, so its high ranking
on Google (must be Google) is remarkable.
No, no - not remarkable; a mystery!
Google (must be Google) must really sort out their rankings. Before
they get called into a congressional hearing.
M
JSH
> On Sun, 29 Nov 2009 17:22:20 +0100, JSH <jst...@gmail.com> wrote:
> > My claims on TSP are ended. I've trashed the algorithm I had, so it's
> > gone.
>
> The very disturbing things about it is that it still comes as #2 on a
> google search for optimal path algorithm (just after some guy named
> Dijkstra). Or #1 if you add quotes around the serach. I'm pretty worried
Don't worry, I removed the page. It WILL drop off of search results.
> of what that means concerning your claims on other searches where you come
> #1 or #2 (such as define mathematical proof, solvind binary quadratic
> diophantine equations and such).
Well one might argue that Google is actually a charade!
Possibly the world media has convinced everyone that a sham company
actually does a service!
The horror, billions of dollars raked in by such a company!
James Harris
Mark Murray
> Well one might argue that Google is actually a charade!
>
> Possibly the world media has convinced everyone that a sham company
> actually does a service!
>
> The horror, billions of dollars raked in by such a company!
This is called "assassinating your own thesis".
One blind bull in as many days. The mind boggles.
M
JSH
> On Nov 29, 12:53 pm, Jym <Jean-Yves.Moyen+n...@ens-lyon.org> wrote:
>
> > On Sun, 29 Nov 2009 17:22:20 +0100, JSH <jst...@gmail.com> wrote:
> > > My claims on TSP are ended. I've trashed the algorithm I had, so it's
> > > gone.
>
> > The very disturbing things about it is that it still comes as #2 on a
> > google search for optimal path algorithm (just after some guy named
> > Dijkstra). Or #1 if you add quotes around the serach. I'm pretty worried
>
> Don't worry, I removed the page. It WILL drop off of search results.
>
> > of what that means concerning your claims on other searches where you come
> > #1 or #2 (such as define mathematical proof, solvind binary quadratic
> > diophantine equations and such).
>
> Well one might argue that Google is actually a charade!
Not Google's fault though. I meant to be sarcastic but I don't do
sarcasm well.
Not in a good mood today.
James Harris
Mark Murray
> Not Google's fault though. I meant to be sarcastic but I don't do
> sarcasm well.
To do sarcasm /at all/ you have to be saying the opposite of what you mean, and obviously so.
Blurting out what people have been saying all along does'nt really do it.
> Not in a good mood today.
Why? You said /a priori/ that this is good news; everyone is safe and it it what you wanted anyway.
M
jonnie
"Mark Murray" <w.h....@example.com> wrote in message
news:4b10e7c8$0$2534$da0f...@news.zen.co.uk...
> JSH wrote:
>> Sounds nutty.
>
<snip crap>
>> The UK is on its own. But that is as it should be and I'm sure Brits
>> would be insulted anyway for me to dare claim that they need my help.
>
> PLEASE HELP!!!!
>
>> They do not need it, of course. And they will not get it.
>
> Oh. I thought we needed it?
>
> M
come on!
JSH telling Brittan what to do ?????
Please, flush first - then turn on the fan.
JSH
Problem which was resoundingly panned on this newsgroup, from one
poster who proudly and repeatedly claimed it just did not work, to
others who challenged the assertion that I'd even really given an
approach!
I like that "wisdom of crowds" thing to test assertions versus endless
arguing with one or two people, so I'm noting now that the algorithm
is probably available to you anywhere in the world by a Google search
(has to be Google):
optimal path algorithm
I just did that search and a page on my math blog comes up #2 behind
some guy named Dijkstra, whoever he is. I guess he did something with
a least times path, while I'm doing something that is supposed to
solve the TSP.
Now I've noted my high search rankings before in newsgroups and run
into some predictable rationalizations:
1. Posters claim only I'm getting the particular search, and say
Google has stuff on my computer to tell them what I want. Well that
one's easily proven or disproven by YOU when you do the search
yourself!!!
2. Posters claim I post a lot of links all over the place to drive up
search results for myself. Well, that one is harder to refute though
I actually rarely if ever post links to MY research, partly because
I've driven up search results for years and puzzle over why myself.
Oh, the other thing of course is, so what?
Well, one or two or even a dozen of you might proudly and loudly
proclaim the idea is crap, but for Google search results to be so
driven presumably a LOT more people around the world disagree, except
then, why isn't this idea part of the status quo?
Turns out that new ideas routinely face an uphill climb so the Google
search results I hypothesize could be a leading indicator.
Even the idea for sliced bread took years to catch on. See:
http://en.wikipedia.org/wiki/Sliced_bread
The idea for escalators was from the late 1800's but didn't get widely
implemented until the mid-twentieth century.
Lasers were to a large extent an early idea of Einstein's.
So why post here now?
Group effects interest me.
The posters who were loud and proud in decrying the idea join a long
line of people who are hostile to new ideas and do so I think for
status reasons. It is of interest to see their reaction to this post.
Presumably it will be defensive.
They are fighting for what they believe is their status in the
hierarchy of this group. Their responses also reveal what role they
*think* they play in that hierarchy. It is a dominance test.
I am challenging their authority and intimating that they lead "their
group" down the wrong path, so they are "bad people" who are also
inferior as to their real knowledge and dangerous to people who trust
them. That assertion should lead to a response.
James Harris
Mark Murray
> So why post here now?
Because you were laughed out of sci.crypt for claiming to have solved
Goldbach's conjecture on the most amusingly flimsy effort?
> Group effects interest me.
Pond slime interests me. Really. Full of interesting bugs.
> The posters who were loud and proud in decrying the idea join a long
> line of people who are hostile to new ideas and do so I think for
> status reasons. It is of interest to see their reaction to this post.
"He's baaaack!!"
> Presumably it will be defensive.
Mine will be offensive.
> They are fighting for what they believe is their status in the
> hierarchy of this group. Their responses also reveal what role they
> *think* they play in that hierarchy. It is a dominance test.
I have no status in the hierarchy of the group. I'm with the pond slime.
> I am challenging their authority and intimating that they lead "their
> group" down the wrong path, so they are "bad people" who are also
> inferior as to their real knowledge and dangerous to people who trust
> them. That assertion should lead to a response.
I have no authority. I have evidence. Maths doesn't lie.
M
Mark Murray
> I just did that search and a page on my math blog comes up #2 behind
> some guy named Dijkstra, whoever he is. I guess he did something with
> a least times path, while I'm doing something that is supposed to
> solve the TSP.
"Some guy named Dijksra" happens to be one of the most respected
computer scientists around. Pity you didn't bother to learn that.
If you'd bothered to pay attention the last N times you were told
this, you would know that the shortest-path algorithm and the TSP
are in the same problem space, so working on one is working on the
other (in crude terms).
> Now I've noted my high search rankings before in newsgroups and run
> into some predictable rationalizations:
Still on proof-by-Google? And you want folks to think you are smart?
(Famous-by-rejection idiocy removed.)
M
Joshua Cranmer
> I like that "wisdom of crowds" thing to test assertions versus endless
> arguing with one or two people, so I'm noting now that the algorithm
> is probably available to you anywhere in the world by a Google search
> (has to be Google):
>
> optimal path algorithm
That is... a very vague term. What makes a path `optimal'? Assuming a
cycle with no negative-weight edges, I can find a path with minimum
total length by simply sorting the edges by weight and picking the
lowest one. I'm not sure why that would be considered interesting though...
> Now I've noted my high search rankings before in newsgroups and run
> into some predictable rationalizations:
3. You're searching for terms that are not the natural search terms.
4. Google would theoretically tend to prefer the technologies it
provides, which you are using.
> Turns out that new ideas routinely face an uphill climb so the Google
> search results I hypothesize could be a leading indicator.
Or it could be a meaningless indicator. There is no reasonable basis for
this statistical correlation, I believe.
> Presumably it will be defensive.
Defending against what? You've got logical reasoning gaps that would
make even English teachers complain.
> I am challenging their authority and intimating that they lead "their
> group" down the wrong path, so they are "bad people" who are also
> inferior as to their real knowledge and dangerous to people who trust
> them. That assertion should lead to a response.
Ah, classism. Perchance we could discuss the effects of industrialism
and social Darwinism on socioeconomic stratification over a cup of tea?
Joshua Cranmer
> JSH wrote:
>> I just did that search and a page on my math blog comes up #2 behind
>> some guy named Dijkstra, whoever he is. I guess he did something with
>> a least times path, while I'm doing something that is supposed to
>> solve the TSP.
>
> "Some guy named Dijksra" happens to be one of the most respected
> computer scientists around. Pity you didn't bother to learn that.
Dijkstra. By about the fifth or so time I've been taught that algorithm
(it's invariably retaught every time graph theory is mentioned. Yes, I
know Dijkstra's algorithm. We learned it in the prerequisite to this
class. And the prerequisite to that class. And the prerequisite to
*that* class, as well as a few other classes that you can expect us to
have taken by now (basic programming classes, essentially)), I can not
only spell his name correctly, but code the entire thing from memory.
Both the O(EV) method and the O(E lg V) ("heap Dijkstra") versions.
> Still on proof-by-Google? And you want folks to think you are smart?
Ah, the appeal to authority fallacy:
Source A says that p.
Source A is authoritative.
Therefore, p is true.
For example:
Theodore Roosevelt believed in eugenics. He is also one of the U.S.'s
greatest presidents. Therefore, we should practice eugenics.
In your course:
Google says that my algorithm is true. Google is the best search engine
out there. Therefore, my algorithm is true.
Wow, that fails logic. FOREVER.
JSH
> On 11/26/2009 2:42 PM, JSH wrote:
>
> > I like that "wisdom of crowds" thing to test assertions versus endless
> > arguing with one or two people, so I'm noting now that the algorithm
> > is probably available to you anywhere in the world by a Google search
> > (has to be Google):
>
> > optimal path algorithm
>
> That is... a very vague term. What makes a path `optimal'? Assuming a
I considered that possibility, so I did a search on: "optimal path
algorithm"
The quote had an interesting effect--they put me at #1. Throwing off
that Djikstra guy.
And that was with 140k search results.
<quote>Results 1 - 10 of about 140,000 for "optimal path algorithm".
(0.44 seconds) </quote>
> cycle with no negative-weight edges, I can find a path with minimum
> total length by simply sorting the edges by weight and picking the
> lowest one. I'm not sure why that would be considered interesting though...
Google can give you a LOT of ways that the term is used.
But apparently in the world at this point in time, my usage is the
dominant form, at least with Google.
> > Now I've noted my high search rankings before in newsgroups and run
> > into some predictable rationalizations:
>
> 3. You're searching for terms that are not the natural search terms.
Any expert field has terms that could be described as not "natural
search terms".
Think, say, many laypeople search on neurasthenia gravis?
> 4. Google would theoretically tend to prefer the technologies it
> provides, which you are using.
Huh?
What if, the world is expressing an early opinion and YOU are wrong?
For those who don't note "Joshua Cranmer" is the one and only person
who was the proud and loud person I mention in my original post that
declared the algorithm to be wrong.
Now I disagree, but hey, if he's right then it just doesn't work. The
Google search position is not proof that it does work, nor is it
presented as such.
It is, for now, a mystery. Or do you disagree?
James Harris
Alfred Johnson
> I just did that search and a page on my math blog comes up #2 behind
> some guy named Dijkstra, whoever he is.
Yeah, who is this random jerk "Djikstra," who has the audacity to
displace JSH on Google? Who the hell does he think he is?
And hey, this one time, I searched for "theoretical computer science
machine" on Google...and some jackass named "Turing" came up before
JSH. Sounds like a couple of losers named Larry and Sergey are going
to need to learn some manners, or risk experiencing "the hammer"....
By the way, in case you haven't noticed...this is Musatov's 'hood now,
so you'd best step off, before he diverts his $1 million CMI prize
donation from the cause of curing childhood cancer to curing childhood
mathematical delusions of grandeur. You might end up with nothing to
do.
Best regards,
Dr. Alfred Johnson, British person
Mark Murray
> It is, for now, a mystery. Or do you disagree?
This is only a mystery to you.
M
Mark Murray
> It is, for now, a mystery. Or do you disagree?
For those watching, when JSH gets really wacky in the NGs, his
twittering gets wacky in a way that compliments this.
(@jstevh, by the way)
Example (he's got this mind-meme control-the-world thing):
# i think i have finally picked a new country. transition team
should start.
about 4 hours ago from txt
Gotta be quick - he deletes them fast when busted, but the excuses
can be good too.
M
JSH
wrote:
> > I just did that search and a page on my math blog comes up #2 behind
> > some guy named Dijkstra, whoever he is.
>
> Yeah, who is this random jerk "Djikstra," who has the audacity to
> displace JSH on Google? Who the hell does he think he is?
>
> And hey, this one time, I searched for "theoretical computer science
> machine" on Google...and some jackass named "Turing" came up before
> JSH. Sounds like a couple of losers named Larry and Sergey are going
> to need to learn some manners, or risk experiencing "the hammer"....
Oh, so my attempt at irony fell flat, or was it an attempt at sarcasm?
My point is that my idea now comes in--at least with a specific Google
search--just behind Dijkstra.
And interesting that you should mention the Google guys as presumably
they know something of what they're doing when it comes to search
results!
So I have #2 with: optimal path algorithm
That is behind Dijskstra. And #1 with "optimal path algorithm".
The quotes make a difference.
> By the way, in case you haven't noticed...this is Musatov's 'hood now,
> so you'd best step off, before he diverts his $1 million CMI prize
> donation from the cause of curing childhood cancer to curing childhood
> mathematical delusions of grandeur. You might end up with nothing to
> do.
Wow you sound angry. Maybe you take Usenet too seriously.
> Best regards,
> Dr. Alfred Johnson, British person
Oh, a Brit. I seem to rile you guys a lot. It's like you take a lot
of what I say personally or something, like it's an individual insult
to YOU in particular.
I find that odd.
James Harris
Mark Murray
> Oh, so my attempt at irony fell flat, or was it an attempt at sarcasm?
Oh, IRONY, riiight! I get it now!
> My point is that my idea now comes in--at least with a specific Google
> search--just behind Dijkstra.
Irony again, right?
> And interesting that you should mention the Google guys as presumably
> they know something of what they're doing when it comes to search
> results!
>
> So I have #2 with: optimal path algorithm
> That is behind Dijskstra. And #1 with "optimal path algorithm".
>
> The quotes make a difference.
Most Ironic. I just don't get it.
>> By the way, in case you haven't noticed...this is Musatov's 'hood now,
>> so you'd best step off, before he diverts his $1 million CMI prize
>> donation from the cause of curing childhood cancer to curing childhood
>> mathematical delusions of grandeur. You might end up with nothing to
>> do.
>
> Wow you sound angry. Maybe you take Usenet too seriously.
Hmm. Wait. I get it - you are using irony again! Or was that sarcasm?
>> Best regards,
>> Dr. Alfred Johnson, British person
>
> Oh, a Brit. I seem to rile you guys a lot. It's like you take a lot
> of what I say personally or something, like it's an individual insult
> to YOU in particular.
Definitely irony! Keep it up!
> I find that odd.
Isn't that ironic?
M
Alfred Johnson
Mr. JSH,
Perhaps you do not remember me, or what you have done to my great
nation of England. Perhaps this will refresh your memory:
Once, many months ago, I asked you--no, I *besought* you--to hear my
nation's pleas for you to save us, to save us with your genius. I
pleaded with you to help save our great nation from the turmoil that
we have been sucked into. I knew, with my many ties to various
clandestine intelligence agencies around the world, that something
awful was going to happen. We could have really used your TSP
algorithm to save us from the terrible fate that has befallen us.
If you cannot read between the lines, I will spell it out for you:
you, JSH, through your negligence, are directly responsible for the
global economic crisis.
Perhaps my anger is rooted in my understanding that millions of
starving families might be better off today, if only you had helped us
with your algorithm; perhaps it is rooted in my knowledge that USENET
*is* a serious place, for serious, intellectual, rigorous discourse
only; or perhaps it is just rooted in nothing--I am, after all, a
deeply angry person who has no ability to grasp such ingeniously
subtle concepts as irony.
But regardless of what I am, let's take a look at what you are: a
brilliant, yet egotistical and insensitive monster, who failed all of
England when we needed you the most, through hubris and negligence as
much as pride and apathy.
Ah, but it is too late now!...all I have left now are you and my other
esteemed USENET colleagues to vent to, and my memories of economic
prosperity.
So, on to other subjects.
I would like to start a poll, if I may. Please respond, everyone; I
will tally the votes and then attempt to factor the totals using JSH's
algorithm.
The poll is:
In a mathematics showdown between JSH and Musatov, who would win?
Your options:
a) JSH
b) Musatov
c) other - please specify
I will cast my vote first:
b) Musatov.
Joshua Cranmer
> In a mathematics showdown between JSH and Musatov, who would win?
>
> Your options:
> a) JSH
> b) Musatov
> c) other - please specify
c. Richard Feynman. He's that good.
Tim Little
> In a mathematics showdown between JSH and Musatov, who would win?
>
> Your options:
> a) JSH
> b) Musatov
> c) other - please specify
c) Nobody wins - and those witnessing the event become somewhat more
stupid for having paid attention to it.
- Tim
JSH
>
> Once, many months ago, I asked you--no, I *besought* you--to hear my
> nation's pleas for you to save us, to save us with your genius. I
Sounds nutty.
Besides, the UK isn't having the problems it could have yet, and
hopefully will manage to avoid further significant financial calamity.
For instance Brits have gone further than the US in reining in big
banks, shrinking them down to size.
And one would hope that despite Britain's debt load, it can manage to
pull out of a financial hole.
I know you're being sarcastic, but regardless, my role is not to save
any country from itself.
> pleaded with you to help save our great nation from the turmoil that
> we have been sucked into. I knew, with my many ties to various
> clandestine intelligence agencies around the world, that something
> awful was going to happen. We could have really used your TSP
> algorithm to save us from the terrible fate that has befallen us.
<deleted>
My optimal path algorithm has been available on the web for over a
year. Insults on Usenet aside, there is the real possibility that
somewhere in SOME country, it is being used.
History has turned on smaller things as scientific advances often make
the difference in who wins or loses.
Brits may be arrogant for the moment, but each moment in history, is
just a moment in time.
EVERY dominant culture has those who believe that such dominance is a
permanent reality based on their limited worldview.
My own country the US DOES receive some special protection as far as
I'm concerned, but not the UK.
The UK is on its own. But that is as it should be and I'm sure Brits
would be insulted anyway for me to dare claim that they need my help.
They do not need it, of course. And they will not get it.
James Harris
Mark Murray
> Sounds nutty.
Can't recognise irony, then?
> My optimal path algorithm has been available on the web for over a
> year. Insults on Usenet aside, there is the real possibility that
> somewhere in SOME country, it is being used.
The probability is "non-zero".
As your algorithm is, as usual, very badly explained and very badly
analysed, the probability is more likely a good approximation to
zero, or the mathematical "epsilon".
Why use crap when Dijkstra can help out?
> History has turned on smaller things as scientific advances often make
> the difference in who wins or loses.
Huh?
> Brits may be arrogant for the moment, but each moment in history, is
> just a moment in time.
We are arrogant anyway.
> EVERY dominant culture has those who believe that such dominance is a
> permanent reality based on their limited worldview.
Huh?
> My own country the US DOES receive some special protection as far as
> I'm concerned, but not the UK.
Huh?
Protection? What, like the army/navy?
> The UK is on its own. But that is as it should be and I'm sure Brits
> would be insulted anyway for me to dare claim that they need my help.
PLEASE HELP!!!!
> They do not need it, of course. And they will not get it.
Oh. I thought we needed it?
M
Rotwang
>
> [...]
>
> For those who don't note "Joshua Cranmer" is the one and only person
> who was the proud and loud person I mention in my original post that
> declared the algorithm to be wrong.
>
> Now I disagree, but hey, if he's right then it just doesn't work.
You obviously missed my post from the 17th. I coded your algorithm and
tested it, and as a result I believe that it does not work. You can
see my implementation of the algorithm, as well as an example input
for which it failed to find the optimal path, here:
http://groups.google.co.uk/group/sci.physics/msg/ee792022c2a95bd5
JSH
> On 26 Nov, 23:52, JSH <jst...@gmail.com> wrote:
>
>
>
> > [...]
>
> > For those who don't note "Joshua Cranmer" is the one and only person
> > who was the proud and loud person I mention in my original post that
> > declared the algorithm to be wrong.
>
> > Now I disagree, but hey, if he's right then it just doesn't work.
>
> You obviously missed my post from the 17th. I coded your algorithm and
Oh yeah, I missed that one. I'm considering it now.
> tested it, and as a result I believe that it does not work. You can
Hey, if it doesn't work it doesn't work.
> see my implementation of the algorithm, as well as an example input
> for which it failed to find the optimal path, here:
>
> http://groups.google.co.uk/group/sci.physics/msg/ee792022c2a95bd5
I'm looking over the post now. So it DID work for some? Neat!!!
But not for all? If not for all then, of course, it's not a solution
to TSP.
But if it worked at all, I find that fascinating.
But I actually hope it's wrong and does not work, as I've scared
myself with its implications.
If it does NOT work then possibly Google search results have pulled it
up as a partial solution, or people just like the life advice given in
the post that DOES come up with the search: optimal path algorithm
It actually is good advice to see yourself in the future, and work
towards where you wish to be, so that could be the reason.
James Harris
JSH
Google Groups is slow in displaying new posts so I'm stuck with
replying again to this one, and actually wouldn't mind if "Rotwang"
would post his Python code on this newsgroup, as it might be better
appreciated here than on sci.physics and sci.math as this newsgroup
has more expertise in that direction.
But I would add also as an aside that it is fascinating that the
poster is noting a case of failure as an outlier if you read the post
to which he is linking, as usually his implementation he claims was
actually succeeding. Wild if true.
Way wild as he went up to 10 nodes. So 10! possible paths.
I'm curious about comments on his code and his results.
For Patricia Shanahan (hopefully she's still around, haven't checked)
actual code!
My position on this still is that I think it's an interesting
algorithm in its own right, even if it turns out to not be a solution
to TSP.
James Harris
Rotwang
> On Nov 28, 5:00 am, Rotwang <sg...@hotmail.co.uk> wrote:
>
>
> >http://groups.google.co.uk/group/sci.physics/msg/ee792022c2a95bd5
>
> Google Groups is slow in displaying new posts so I'm stuck with
> replying again to this one, and actually wouldn't mind if "Rotwang"
> would post his Python code on this newsgroup, as it might be better
> appreciated here than on sci.physics and sci.math as this newsgroup
> has more expertise in that direction.
Sure. The code is reproduced below. For the results of tests, and some
explanation of the implementation for those unfamiliar with Python,
see the above GG link, as well as the following:
http://groups.google.co.uk/group/sci.math/msg/93eaffa45999556e
http://groups.google.co.uk/group/sci.math/msg/93a8ce4532c48df9
The function takes as input a list G of lists, in which each element
of G is assumed to have the same length as G itself; G[i][j] is the
cost of travelling from node i to node j, where nodes are labelled by
integers from 0 to len(G) - 1. It outputs a tuple with two elements,
the first being a list which is the path found by the algorithm, and
the second being the total cost of said path. Here it is:
def tsj(G):
n = range(len(G))
T = []
for i in n:
T1 = [i]
T2 = [i]
m = [j for j in n if j != i]
while len(m) > 1:
c1 = []
for j in m:
c2 = []
for k in m:
if j != k:
c2.append([k,G[T1[-1]][j]*G[T2[0]][k]])
r = 0
for q in xrange(1,len(c2)):
if c2[q][1] < c2[r][1]:
r = q
c1.append([j,c2[r][0],c2[r][1]])
r = 0
for q in xrange(1,len(c1)):
if c1[q][2] < c1[r][2]:
r = q
T1 = T1 + [c1[r][0]]
T2 = [c1[r][1]] + T2
m.remove(T1[-1])
m.remove(T2[0])
S = T1 + m + T2
T.append([S,sum([G[S[j]][S[(j+1)]] for j in n])])
r = 0
for q in xrange(1,len(G)):
if T[q][1] < T[r][1]:
r = q
return [T[r][0][i] for i in n],T[r][1]