Traveling salesman, idea, easy to program?

[Owen Jacobson]

Once again, this would be more appropriate to comp.programming,
sci.logic, or any newsgroup dedicated to computing and algorithms.
comp.lang.java.programmer is primarily devoted to implementation
details as they apply to Java. Followup-To once again set
appropriately.

I see a lot of objections in this thread from guys distressed about
the original problem not using the distance between the cities which
is where creativity is hard!!!

Making use of additional information not present in the problem's
definition imposes constraints on your solution. Specifically, it
implies that your solution only applies to a subset of the cases
admitted by the problem. For example, your solution, assuming for the
moment it works[0], only applies to complete graphs whose nodes are
members of a metric space. The problem space includes /all/ complete
graphs.

Solving[0] a subset of the problem in polynomial time[0] is useful,
but nowhere near as useful as a polynomial-time general-purpose
solution would be[1]. A general solution cannot "creatively" take
into account information that's not part of the problem definition
without first formally proving that the additional information is
logically implied by information in the problem definition.

Finally, you may have been mislead by the name of the problem: while
informal discussions of the "travelling salesman" problem are framed
in terms of flights or trains, cities, and travel time, this doesn't
mean you can drag in aspects of the real world in your solution. A
formal treatment of the travelling salesman problem will frame it only
in terms of nodes, edges, and edge weights, with the goal of
minimizing the sum of edge weights along a path with particular
properties.

-o

[0] ...which you haven't formally proven...
[1] In particular, your solution[0] does not imply or prove anything
in either direction about P = NP.

 

[Christian]

The algorithm itself is polynomial time, as if there are m+2 nodes,
where 2 of them are the starting and ending nodes then the first
iteration has (m-1)^2 value calculations, while the second has (m-3)^2
and so forth.

here you lost me .. as you have just said that P = NP .

Mathematicians around the world DESPISE me for posts like this one as
they see them as insulting to think that I could dare to solve a hard
and difficult problem that brilliant people have worked on for years.

But I say, why can't I just toss some ideas out there? What really is
so wrong with that?

If you say your algo can solve TSP in polynomial time that means P = NP
.... probably the hardest and most important problems in Comp sci ...

I would rather say your algorithm is incorrect. Actually I don'T even
look at it ... its not worth it .. the probability for it to be working
with al the vagueness and everything is so close to zero that the
potential win no matter how high if it works is not worth it..

If you think you just prooved that P = NP .. do some work to get you
Turing Award.

Christian

 

[Christian]

Well, keep in mind his prior accomplishments:

1. Proof of Fermat's Last Theorem, long before Wiles.

so he is rather old .. good Mathematicians are maximum age 11 .. see
xkcd: http://www.xkcd.com/447/

2. Discovered fundamental contradiction in algebra, completely
demolishing modern ring theory. Paper accepted for publication in a
journal, then mysteriously pulled after world wide conspiracy of
mathematicians intervened.

Ah I love conspiracy theorys. Some Atheist told me that Conspiracy
theorys are in reality just a conspiracy to keep people believing in
something. A replacement for God without actually becoming Atheist. (The
Vatican must be behind this)

3. Complete solution to integer factoring, rendering RSA completely
broken.

Don't care ... discrete logarhytm is way better imho as integer
factorization is already possible in sub exponential time (luckily for
us its not polynomial just subexponential)

If anyone can decide P = NP...

hmm I have once proven that P == NP or P != NP this isn't that but may
be you meant something else with your 3 dots.. just prooving one side of
the or seems to be much harder. To hard for anyone above 11.

Christian

p.s.
Proof for P != NP

We assume P = NP
We assume that mathematical proofs are in NP .. as it is rather easy to
verify them.
If P = NP finding a proof would also be in P ... and so the Question to
P = NP should already have been solved several years ago. Therefore we
have a contradiction and P must not contain NP.

 

[JSH]

Here's an example I'd like to see worked using your algorithm:

Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
B is the same cost as B to A.

C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1..

Patricia

My idea won't work with that example.


James Harris

 

[Michael Press]

Well, keep in mind his prior accomplishments:

1. Proof of Fermat's Last Theorem, long before Wiles.

2. Discovered fundamental contradiction in algebra, completely
demolishing modern ring theory. Paper accepted for publication in a
journal, then mysteriously pulled after world wide conspiracy of
mathematicians intervened.

3. Complete solution to integer factoring, rendering RSA completely
broken.

If anyone can decide P = NP...

4. Prime counting function has immediate consequences
for deciding the Riemann hypothesis.

 

[Patricia Shanahan]

My idea won't work with that example.

In that case, your idea is obviously not an algorithm for Traveling
Salesman, which explains why I didn't understand how it could possibly work.

Perhaps you need to state what, if anything, it does solve?

Patricia

 

[JSH]

In that case, your idea is obviously not an algorithm for Traveling
Salesman, which explains why I didn't understand how it could possibly work.

Yes it is. I don't understand why you can't comprehend how it works,
especially after a simple example. Possibly you should read the reply
by Joshua Cranmer and my reply to him?

Might that help you?

Perhaps you need to state what, if anything, it does solve?

Patricia

I already did, and worked an example, which, did in fact give the
optimal path--solving a Traveling Salesman Problem!!!

So we're going in circles here.

You believe one thing and a direct, simple example has no impact on
your belief so there's no point in continuing the discussion until
this crucial crossroad is passed.


James Harris

 

[Joshua Cranmer]

Yes it is. I don't understand why you can't comprehend how it works,
especially after a simple example. Possibly you should read the reply
by Joshua Cranmer and my reply to him?

This is the fully correct statement of the TSP:

Given a complete weighted graph, what is the minimum weight Hamiltonian
circuit?

Or, if you prefer the NP-complete version,

Given a complete weighted graph, does there exist a Hamiltonian circuit
of weight less than X?

Therefore, any solution to TSP must be able to produce a result given
/solely/ the vertexes and the weights of the edges (and the total weight
to search for, in the decision form of the problem). Any algorithm which
requires more information than that cannot solve the TSP.

Logically speaking, if I could require more information, I could simply
require someone to pass in the minimum cost Hamiltonian circuit as well
and go "OH NOES!!!!!1111one11! I FOUND AN O(1) SOLUTION!!! I AM T3H
H4X0RZ!!!!!!11111"

Note especially that the graph need not conform to the triangle identity.

I already did, and worked an example, which, did in fact give the
optimal path--solving a Traveling Salesman Problem!!!

It didn't solve a TSP. You had more information than the TSP gave you.

 

[JSH]

This is the fully correct statement of the TSP:

I didn't say it was not.

Given a complete weighted graph, what is the minimum weight Hamiltonian
circuit?

Or, if you prefer the NP-complete version,

Given a complete weighted graph, does there exist a Hamiltonian circuit
of weight less than X?

Therefore, any solution to TSP must be able to produce a result given
/solely/ the vertexes and the weights of the edges (and the total weight
to search for, in the decision form of the problem). Any algorithm which
requires more information than that cannot solve the TSP.

That is a leap and is not provable. (Try it.)

You have a problem definition which ignores information available in
any metric space, or to keep it simple, in any real world problem.

In any REAL WORLD problem, there is a distance between the nodes.

I say the problem is not solvable with a polynomial time algorithm
without using that information!!!

You and Patricia I guess, disagree, but you cannot logically disagree.

I say you're wrong and if not, prove it. PROVE IT. Don't just tell
me over and over again what you know the Traveling Salesman Problem is
an is not.

I'll give you an example for your position showing you how unknowingly
people use distance information anyway.

Say with a simple 4 node example one node is at the moon and goes to
all other nodes at a cost of #100 US while the remaining nodes are one
block away from each other with a cost in either direction of
$100,000,000 U.S., what is the answer from a typical Traveling
Salesman Problem algorithm?

Please answer that question.

I DARE you to honestly answer that question.

You already use distance information, but just never admitted it.

I simply solved the problem without inference. You deep down know
that the cost between nodes roughly correlates with DISTANCE!!!

Your human intuition--gut instinct--has ALWAYS been part of solutions
you consider ANYWAY!!!

Or are you sending that salesman to the moon with my simple example?

Are you?


James Harris

 

[JSH]

I didn't say it was not.





That is a leap and is not provable.  (Try it.)

You have a problem definition which ignores information available in
any metric space, or to keep it simple, in any real world problem.

In any REAL WORLD problem, there is a distance between the nodes.

I say the problem is not solvable with a polynomial time algorithm
without using that information!!!

You and Patricia I guess, disagree, but you cannot logically disagree.

I say you're wrong and if not, prove it.  PROVE IT.  Don't just tell
me over and over again what you know the Traveling Salesman Problem is
an is not.

I'll give you an example for your position showing you how unknowingly
people use distance information anyway.

Say with a simple 4 node example one node is at the moon and goes to
all other nodes at a cost of #100 US while the remaining nodes are one
block away from each other with a cost in either direction of
$100,000,000 U.S., what is the answer from a typical Traveling
Salesman Problem algorithm?

OOPS! Problems with that example is if one node is at the moon then
yeah, the salesman HAS to go to the moon.

Proper example is that all nodes are one block away from each other,
but all paths have a cost of $100,000,000 U.S. while one path goes and
loops around the moon at a cost of $100.

So are you looping that salesman around the moon?

Sorry, I rushed a bit and got the initial example wrong.

Still my point remains that you use DISTANCE information intuitively
in the improperly states original problem.

I'm removing your intuition from the equation.


James Harris

 

[JSH]

In that case, your idea is obviously not an algorithm for Traveling
Salesman, which explains why I didn't understand how it could possibly work.

Perhaps you need to state what, if anything, it does solve?

Patricia

I've replied before but I figured out a way to prove your intuition is
part of your supposed solutions: say the path from C,A goes around the
moon? While all other paths are 100 miles long, what is the proper
answer?

You may argue: but no one can go around the moon!

That's not REASONABLE, right?

But what does that have to do with a properly stated problem?

Why can't I have one path loop around the moon?

Oh, I know, no way you can loop someone around the moon for $1000 U.S,
right?

Well, yeah, I KNOW that and you know that, but how does that relate to
a properly stated problem?

See what I mean? Your GUT instinct is part of what you think the
answers are to the problem and that gut instinct intuitively knows
that the distances between nodes are not outrageously different as you
can't go to the freaking moon cheaper than you can walk down the
goddamn street.

Now can you?


James Harris

 

[Patricia Shanahan]

Yes it is. I don't understand why you can't comprehend how it works,
especially after a simple example. Possibly you should read the reply
by Joshua Cranmer and my reply to him?

It would be very bad if I were to "comprehend how it works" since it
does not work in exactly the sort of case I thought it would not handle
correctly. My ability to construct an example on which it fails strongly
suggests that the flaws I thought I saw in it are real.

Might that help you?


I already did, and worked an example, which, did in fact give the
optimal path--solving a Traveling Salesman Problem!!!

A valid Traveling Salesman algorithm must correctly solve *any* instance
of Traveling Salesman, not just selected, convenient examples. It might
be a valid algorithm for some restricted version of Traveling Salesman.
As is typical of NP-complete problems, it does have restricted versions
that are known to be in P. I suspect you are really solving one of those.

You believe one thing and a direct, simple example has no impact on
your belief so there's no point in continuing the discussion until
this crucial crossroad is passed.

Indeed, no finite number of examples, unsupported by generalized
reasoning, will convince me of the correctness of an algorithm that is
claimed to solve a problem for which there are an infinite number of
instances. On the other hand, a single example for which it does not
work is sufficient to convince me it is not correct.

I could claim a constant time algorithm for ascending value sorting an
int array. It just returns the original array, unchanged. It must
be a valid sort algorithm, because it returns the correct answer for
this example:

new int[]{1, 3, 1000, 5000, Integer.MAX_VALUE}.

Of course, it would not work for new int[]{2,1}.

Would it be OK to go on claiming it is a valid sort algorithm after
admitting it does not work for that example, just because I have
presented a direct, simple example for which it does work?

It is, in fact, a correct algorithm for the restricted version of the
int[] sort problem in which the elements are already in ascending order.
It is incorrect as a solution to the unrestricted int[] sort problem.

Patricia

 

[Joshua Cranmer]

That is a leap and is not provable. (Try it.)

It cannot solve the TSP because the TSP doesn't give it sufficient
information.

In any REAL WORLD problem, there is a distance between the nodes.

That doesn't mean that the distance is meaningful in any way. In the
case of printed-circuit board design, the distance between two holes is
unimportant if the drill bit has to be changed between them.

I say the problem is not solvable with a polynomial time algorithm
without using that information!!!

Then you say P != NP, because the problem does not *permit* you to have
that information.

I say you're wrong and if not, prove it. PROVE IT. Don't just tell
me over and over again what you know the Traveling Salesman Problem is
an is not.

Returning to the definition of NP-complete, I can rewrite the SAT
problem into a form of the decision problem version of the TSP. Do you
disagree with this statement? If you do, you need to study computational
complexity again.

Now, we can both agree that SAT is very much a real-world problem, with
useful applications. Look at the usages of Prolog if you disagree with
me there.

Now, we are in agreement that I can write a TSP that will solve a SAT
problem, which (we agree) is a real world problem. I pose this question
to you: How do I define a distance distinct from the edge weight here?

Say with a simple 4 node example one node is at the moon and goes to
all other nodes at a cost of #100 US while the remaining nodes are one
block away from each other with a cost in either direction of
$100,000,000 U.S., what is the answer from a typical Traveling
Salesman Problem algorithm?

Well, I would go earth node -> earth node -> moon node -> earth node ->
earth node (first one). Oh wait, /that's the only unique path/, since
the three earth nodes are by your example indistinguishable. Bad example.

You already use distance information, but just never admitted it.

Nope. There's one unique path and I picked it.

Or are you sending that salesman to the moon with my simple example?

If I'm not, I'm not providing a Hamiltonian circuit, so therefore I have
to. I really don't understand your point in all of this.

 

[Patricia Shanahan]

I've replied before but I figured out a way to prove your intuition is
part of your supposed solutions: say the path from C,A goes around the
moon? While all other paths are 100 miles long, what is the proper
answer?

....

Traveling Salesman is about *cost* of travel between the cities, or more
abstractly about weights associated with graph edges, not *distance*.
Anyone who has paid for airline tickets or used toll roads knows cost
and distance are not necessarily proportionate to each other.

In my example, it happens that cities A, B, D, and E are all in the same
country. That country's public transportation system directly connects
each pair, and has a flat $1 fare. Unfortunately for our salesman, C is
in a different country with no legal border crossings.

Gang X controls illegal activity in D and E. X charges $2000 to smuggle
someone between either of those cities and C. Gang Y, which controls
illegal activity in cities A and B, is establishing its own smuggling
route to C. In order to attract business to the new route, Y only
charges $1000 to smuggle a person between a city it controls and C.

Neither gang can safely smuggle to or from a city controlled by the
other. The police force in C ignores smuggling, but arrests anyone
involved in a gang fight, so either gang can smuggle to or from C
without any risk of interference by the other gang.

If you are dealing with distances, not costs, you are not solving the
problem conventionally known as "Traveling Salesman". You may be solving
some other problem that you choose, rather confusingly, to call
"Traveling Salesman", but if so you need to define it, so that the rest
of us know what you are talking about.

Patricia

 

[Lits O'Hate]

See what I mean? Your GUT instinct is part of what you think the
answers are to the problem and that gut instinct intuitively knows
that the distances between nodes are not outrageously different as you
can't go to the freaking moon cheaper than you can walk down the
goddamn street.

James Harris said "freaking." Everybody drink!

It's good to see you back to your "real self," James.

 

[Lits O'Hate]

4. Prime counting function has immediate consequences
for deciding the Riemann hypothesis.

5. Wrote "the" definition of "mathematical proof."

6. Solved all problems surrounding Digital Rights Management.

7. Released a very popular open source program that nobody uses.

8. Can "understand the Internet, I think, far better than any
of you can possibly come close to comprehending, with, your,
I'm afraid, um, limited intellects."

9. Is a "true, living super genius."

 

[Junoexpress]

I already did, and worked an example, which, did in fact give the

optimal path--solving a Traveling Salesman Problem!!!

You seem to be having a little trouble with logic here James, so let
me help you out.
It is *the* traveling salesman problem. There is no such thing as "a"
traveling salesman problem.
There are given examples of the traveling saselsman problem, maybe a
few of which your "backwards" traveling salesman approach can solve.
See? Yeah, probably not...

So we're going in circles here.

Seems that all the going in circles has got you a bit dizzy in the
head: maybe you should have a sit-down James...

You believe one thing

You are the only one who has to rely on belief here my friend: the
others are simply pointing out painfully obvious facts to you.
Fortunately for you, though, since you cannot understand what they are
saying, you're about affected by their responses as my dog is to me
reading MacBeth to him.

and a direct, simple example has no impact on your belief

I guess by the same logic, all odd numbers should sum to 6. I mean
3+3=6 and 1+5=6. These are two concrete examples, yet I'll be those
picky mathematicians probably will not accept these perfectly valid
examples.

...so there's no point in continuing the discussion until
this crucial crossroad is passed.

James Harris

How will that happen? Another threat of a lawsuit against very US
college and university? Perhaps a warning that every professor of
computer science will lose their jobs once people find out they are
blocking another one of your brilliant discovers. Can't wait to find
out...

M

 

[JSH]

I had forgotten that one.  If I recall correctly, his prime counting
function was actually correct.  It was very inefficient, and was just a
slight variation on previously known work--but it worked.

It counts primes, so there was no way to lie about the result, as,
well, I could simply program it (which I did) and, yup, it'd count
primes. Math people lie a lot but in that case they were kind of
stuck, though there would be people every once in a while who'd claim
that nothing I did ever worked!!!

Oh, and I'd talk about my Class Viewer for Java program to point out
that I have a tool used by people around the world--and they ripped on
it. And then they'd go back to saying I was just some crackpot who
never did anything that worked!

No matter what I did, they'd go back to calling me names and often say
that nothing I did ever worked, though they would at times admit that
I DID find a prime counting function that DID work, but then they'd
say it wasn't useful information even though there is no other known
prime counting function in all of human history that uses a P(x,y)
function, and leads to a partial differential equation.

Math people lie all the time.

It is P(x,y) function that counts primes when y=sqrt(x), and so it
fails with many people by the same argument now being used against my
traveling salesman problem algorithm--it has more information than
classical methods. Math people typically use a pi(x) equation.

The three dimensional function I use is different in that it leads to
a partial differential equation, unlike any others, which was disputed
by math people until, yup, I showed the derivation, though in that
case some STILL disputed the reality that no other known in human
history does the same thing.

It didn't, of course, give any insight into the Riemann hypothesis.

What's funny about what math people ultimately did is that at the end
they simply chose, like the poster I'm replying to, to simply state
something that could not be true, and stayed with that no matter how
much I explained, no matter how much I derived, no matter what I could
prove.

I said, it was like they just said, no.

They don't want to know the actual answer.

Just like people replying in this thread do not want a best solution
to the traveling salesman problem.

You know, and I know that distance information is wrapped up in the
problem, so denying an algorithm because it uses what is normally
inferred is as insane as claiming that because a P(x,y) function has
an extra variable, it's not worth caring about just because math
people normally use a pi(x), single variable function.

It's stupid behavior. But stupid often rules in the real world.


James Harris

 

[Lew]

The improperly formulated form of the TSP does not have distance
information between all nodes, though practitioners intuitively use
such information or intuitively realize it still is in the problem by
way of the weights themselves.

So it's just sloppy formulation of the problem.

BWAAAA-HA-HA-HA-HA-HAAAAA!

--
Lew


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
[Freemasonry, occult, Kabbalah, KKK,
deception, Illuminati, NWO]

"We shall unleash the Nihilists and Atheists,
and we shall provoke a formidable
social cataclysm which in all its horror
will show clearly to the nations the
effects of absolute atheism, origin
of savagery and of the most bloody turmoil.
Then everywhere, the citizens, obliged to defend
themselves against the world minority of
revolutionaries, will exterminate those
destroyers of civilization, and the multitude,
disillusioned with Christianity, whose deistic
spirits will be from that moment without compass,
anxious for an ideal, but without knowing where
to render its adoration, will receive the pure
doctrine of brought finally out in the
public view, a manifestation which will result
from the general reactionary movement which will
follow the destruction of Christianity and atheism,
both conquered and exterminated at the same time."

Illustrious Albert Pike 33°
Letter 15 August 1871
Addressed to Grand Master Guiseppie Mazzini 33°

[Pike, the founder of KKK, was the leader of the U.S.
Scottish Rite Masonry (who was called the
"Sovereign Pontiff of Universal Freemasonry,"
the "Prophet of Freemasonry" and the
"greatest Freemason of the nineteenth century."),
and one of the "high priests" of freemasonry.

He became a Convicted War Criminal in a
War Crimes Trial held after the Civil Wars end.
Pike was found guilty of treason and jailed.
He had fled to British Territory in Canada.

Pike only returned to the U.S. after his hand picked
Scottish Rite Succsessor James Richardon 33° got a pardon
for him after making President Andrew Johnson a 33°
Scottish Rite Mason in a ceremony held inside the
White House itself!]

 

[JSH]

No, everyone here would like a polynomial time solution to TSP.  
However, what you've proposed does not solve TSP at all, let alone in
polynomial time.  To be a solution to TSP, it has to work for *all*
instances of TSP.  You were given a small instance for which it did not
work.

Really? I missed that. Oh, I didn't read all replies in this
thread. I guess maybe I should before I comment further about my
latest algorithm...

Heck, if we are going to count a problem solved with algorithms that
only solve some instances, then I have a very fast solution to integer
factoring:

   Let N be the number we want to factor.
   Let a = floor(sqrt(N))
   Let b = floor(N/a)

   Then the factors of N are a and b.

No point in being silly.

I have no problems with a demonstration that the idea is wrong. What
I have a problem with is people telling me it can't be an algorithm
for TSP because it relies on the straight line distance between nodes
as well as weights, and other people can just use weights between
nodes without the distance info.

And I notice you simply deleted out what I said about my prime
counting function.

That's the reality I face: math people will simply ignore what they do
not like.

I won't bore readers here with a digression on how easily I proved
some rather big things just by using a multi-variable P(x,y) function
versus the classical approach of a single variable pi(x) function--for
those wondering the issue here is counting primes so to 100, you have
pi(100) = 25, while with my function you have P(100,10) = 25.

But I assure you that if you wish to feel sick to your stomach about
even top mathematicians like Odlyzko and Lagarias who I have been in
contact by email on this issue, then do even the most basic research
on what I found, and see what they did in response.

They are traitors to their field and to the pursuit of human knowledge
and the only thing I can figure is that they are afraid of simplifying
research removing a cash cow.

I suggest that they do not like simple answers that I guess they fear
will remove reasons for funding because the main questions are
answered.


James Harris