Traveling salesman, idea, easy to program?

[JSH]

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

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.

That doesn't mean that the distance is meaningful in any way. In the

Why? Because you say so despite every rational person reading your
reply knowing that distance IS important when it comes to traveling in
the real world?

Can you truly plan a trip with say, just cost information alone?

PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.

Only academics would argue this point where an over abstraction has
forced important information to be inferred.

case of printed-circuit board design, the distance between two holes is
unimportant if the drill bit has to be changed between them.

That is an additional weight.

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

But that's false.

Even with just a single weight you can graph the nodes one a two-
dimensional plane and simply give them a distance from each node equal
to the size of the weight in whatever units you prefer, though you'd
have to adjust them so that you get all the weights correctly, but
then you'd have physical coordinates. If you have multiple weights
you'd just pick one.

So why make a claim that is so trivially wrong to hold on to a
position denying the most basic reality that in real world travel or
other areas where the problem is relevant, there is distance
information between nodes?

I'm going to scan down and see if you have anything better. If not
I'll quit replying at this point.


James Harris

 

[JSH]

...

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.

That is true, which is why you have weights in TSP.

Distance is in actuality one weight that is always there, whether it's
stated or inferred as people intuitively realize that the further
something is from them and their final destination the greater the
"cost" of that trip.

Academics I'd guess over abstracted the problem and threw out that
information and tried to just use other weights which may or may not
correlate closely with distance but often in the real world do
correlate well with distance.

So if our traveling salesman lives in New York and at one leg of his
trip has to go to Hong Kong, then he may feel a greater "weight" with
the longer trip than he will about another trip to Chicago, simply
because one is closer than the other, regardless of what he will pay
for airplane flights.

Academics throwing out important information for no good reason is an
oddly common problem.

When challenged on it, they typically talk down to other people as if
challenging them about throwing away valuable information is stupid.

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.

Which is an additional "weight" on the salesman's mind!!!

Or do you deny that?

It appears you have no clue what a "weight" is in the problem.

A weight is ANY limiting factor which impacts the decision problem of
which path is preferable.

You went to some school where you got taught the problem one way,
right?

If it was a really good school they should also have taught you some
flexibility in your thinking.

Problem solving is not about going just by what you were taught!!!

Learning can be about un-learning, and growth can be about
perspective.

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

You say so, why?

Because some person a long time ago told you so?

Because you were taught to ignore the most basic information that you
yourself probably use in the real world, as you over abstracted the
problem as an academic exercise?

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

I worked a simple example with 4 nodes. Um, it seemed to me that at
the end of that example I had a TSP problem solution.

So your assertion is a direct denial of a simple demonstration.

What really can I do in the face of obstinate denial?

Nothing. Discussion ends up being futile at that point as one person
refuses to be reasonable.

Which is what I often face with my research: some person tells me what
must be, and refuses to acknowledge the most basic things including
direct examples or mathematical proof.

There is no way to go beyond that point while the other person so
behaves.


James Harris

 

[Owen Jacobson]

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

Rather. I'm reminded of another poster from several years ago, who
insisted that the halting problem would be solvable if only he were
permitted to modify the problem to include a "secure" output channel
or write-only region of memory which the user could read but which no
modification of the halting problem solver could access. Arguments
that the halting problem is about computability and that all of those
can be simulated within a Turing machine without affecting the
solution one iota fell on deaf ears for a *very* long time.

Modifying the problem to make it easier to solve is not, and never has
been, a valid solution method.

-o

 

[Jeff Higgins]

JSH wrote:

Academics throwing out important information for no good reason is an
oddly common problem.

Trolls flinging dung yet another.

 

[Joshua Cranmer]

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.

Since you have stated that your intention is to solve P = NP, I would
like to point out that you should really be considering the NP-complete
version of the problem instead of even the NP-hard version or the
"annotated" NP-hard version, regardless of its actual applicability.

Computational theory tries to look at /worst-case/ results, not
/average-case/ or /best-case/.

PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.

And P = NP is precisely not about the real world. Obligatory XKCD

But that's false.

Even with just a single weight you can graph the nodes one a two-
dimensional plane and simply give them a distance from each node equal
to the size of the weight in whatever units you prefer, though you'd
have to adjust them so that you get all the weights correctly, but
then you'd have physical coordinates. If you have multiple weights
you'd just pick one.

So you've finally explained: the distance is, in lieu of other
information, the weight. Which, I might add, is a backtrack from your
previous statements that the distances were needed. Since the distance
is a heuristic (and one that could potentially make time worse), why not
just drop it in your algorithm and use the weights like everyone else?

 

[Junoexpress]

Why? Because you say so despite every rational person reading your
reply knowing that distance IS important when it comes to traveling in
the real world?

Can you truly plan a trip with say, just cost information alone?

PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.

Sometimes, but not always. Simple example: two possible routes go from
A to B. Route one route is shorter, but goes through a major city with
lots of traffic and a toll road. Route 2 is longer, but goes through
the country and there are no toll roads. How do you weight these two
routes? Depending on what quantity I choose to measure as being
important, the routes can have a wide variety of weights. It is easy
to envision scenarios where route one will have a larger weight than
route 2, and it is equally easy to envision cases where route one will
have a smaller weight than route 2. It is also totally possible to
have weights that have absolutely no distance dependence at all
associated with them (maybe I rank the routes based on how scenic a
view they offer or the risk of me being car-jacked or by the measure
of safety I feel if my car breaks down somewhere on the way).

Despite your (self-proclaimed) creativity, you can't seem to liberate
your mind from the concrete. Pity.

M

 

[John W Kennedy]

Can you truly plan a trip with say, just cost information alone?

OMG you think "cost" means....

OMG OMG OMG OMG OMG OMG!

--
John W. Kennedy
"The pathetic hope that the White House will turn a Caligula into a
Marcus Aurelius is as naïve as the fear that ultimate power inevitably
corrupts."
-- James D. Barber (1930-2004)

 

[JSH]

No, you did not miss it.  You read it, and acknowledged that your
algorithm did not handle it:

<http://groups.google.com/group/comp.lang.java.programmer/msg/a81862346a2
a576a?hl=en&dmode=source>

You'd have a better chance of success in all your endeavors if you could
get your multiple personalities to each be aware of what the others are
doing.

Yes and no. The pure algorithm when faced with exactly three nodes
where T_1 is at N_1 and T_2 is at the end node, leaving only one node
available, will exit, but the solution then is that T_1 moves to the
only node left (or T_2 does).

Which I noted in my replies on this subject.

One of the tiring things about these kinds of discussions is that
their length and so many replies depends on people refusing to
acknowledge solutions already presented.

So Patricia Shanahan and Joshua Cranmer kept ignoring the reality of a
worked simple example to claim that I wasn't actually doing TSP!

And you declare boldly that a case isn't handled when I replied
handling that case.

The issue here is willful denial.

Against it, proof does not work. Explanation does not work.

And I've been down this road before: people like you clog up the
discussion, fight against getting to the bottom of things, and make a
mess so that you can hide the truth.

But here, you're fighting to hide an algorithm to solve the TSP, and
prove that P=NP, once and for all.

Why would any person do that?

I suggest readers understand that academic evolution may have been
towards complexity against solution so that from game theory our
current system rewards people for denying simple answers for complex
ones that drive public funding.

We pay people to get complex answers, not to just get answers.

It's publish or perish in the academic world. Simple answers do not
necessarily drive a lot of papers.

We trained our academics to fight against simplicity, and we're paying
the price all over our world.


James Harris

 

[Patricia Shanahan]

You say so, why?

Because some person a long time ago told you so?

No, I say so because I have seen equivalent definitions many times in
books, classes, and papers over a period of decades, and you are the
first person I have seen apply the term to anything different.

The definition I am using is consistent, for example, with the one in
Garey and Johnson's "Computers and Intractability A Guide to the Theory
of NP-Completeness". It is the version of the problem that I have seen
proved NP-Complete. Everyone except you who has expressed an opinion on
the issue in this thread seems to agree on the definition.

This is a matter of communication. Maybe your definition of the problem
would be a superior one in some absolute sense, though that is
impossible to tell without seeing your definition. However, effective
communication depends on consensus terminology. There is a specific
problem that is commonly called "Traveling Salesman". My example is a
valid instance of that problem, but not, apparently, of the problem you
call "Traveling Salesman".

Why not just post a precise definition of the problem you are trying to
solve?

I worked a simple example with 4 nodes. Um, it seemed to me that at
the end of that example I had a TSP problem solution.

Finding a combination of simple algorithm and special case for which the
algorithm is correct and efficient is far, far too easy to be
interesting. The challenge is to provide an algorithm that efficiently
solves *any* instance of some difficult problem.

Patricia

 

[JSH]

Indeed.  That is accurate.

Yup. And of course both sides say it's the other side that refuses to
be reasonable.

I have publication to know about the truth. I have proofs that I've
explained to top mathematicians including one in person, to know the
truth. And I have my results that do fun things like count prime
numbers to know the truth.

My final assessment is that often in our world people lie to maintain
social status.

So problems are not solved simply because the "wrong person" solves a
problem.

The not discussed reality here is that people like you are willing to
not only ignore a solution to something like the TSP because you've
decided that your social world cannot handle me in a certain position,
but you will work hard at other ways of approaching the problem--
wasting your time and energy--because the real issue is your social
status.

Ok, evolution has the answer for people like you.

As our world warms up and people like you fight for that social
status, and ignore solutions for that social status, it will die with
your groups.

As the world population dies, so will the behavior as evolution takes
over.

When there is no one around who cares about who solves the problem but
only that the problem is solved, then that path of the optimal
algorithm will have completed.

At the end of the day, problem solving is ultimately about life and
death.

On that point then, I say that time will tell. Nations will fall.
Civilizations will crumble, but those who can solve the problems
necessary to stay alive, by definition, will continue.

It is the one way that life IS fair.


James Harris

 

[JSH]

Yup.  And of course both sides say it's the other side that refuses to
be reasonable.

I have publication to know about the truth.  I have proofs that I've
explained to top mathematicians including one in person, to know the
truth.  And I have my results that do fun things like count prime
numbers to know the truth.

My final assessment is that often in our world people lie to maintain
social status.

So problems are not solved simply because the "wrong person" solves a
problem.

The not discussed reality here is that people like you are willing to
not only ignore a solution to something like the TSP because you've
decided that your social world cannot handle me in a certain position,
but you will work hard at other ways of approaching the problem--
wasting your time and energy--because the real issue is your social
status.

Ok, evolution has the answer for people like you.

As our world warms up and people like you fight for that social
status, and ignore solutions for that social status, it will die with
your groups.

As the world population dies, so will the behavior as evolution takes
over.

Ok, way over the top as clearly this discussion has degenerated to a
point where there is no point in continuing, so after this post, I'm
done for now.

I know how this goes having had proof after proof, result after
result, blocked by people who literally would often call me insane.

Proof does not always work in the real world.

It's not fair, but that's the reality.

But the dark side of it is that catastrophe is too often preventable,
but is not prevented because there are comfortable people who say
nothing is wrong.

Like consider the economy in the US today: many rich and powerful
people feel no problems so like the Bush advisor talking of a "mental
recession", they see no reason for meaningful change.

Or for better solutions...

Oh yeah, global warming will not be addressed by rich and powerful
nations for that reason--until and if it takes away their richness and
power.


James Harris

 

[John W Kennedy]

Finding a combination of simple algorithm and special case for which the
algorithm is correct and efficient is far, far too easy to be
interesting. The challenge is to provide an algorithm that efficiently
solves *any* instance of some difficult problem.

Well, doesn't that depend on the individual special case? I mean, say
someone came up with an algorithm that could be proven to work
efficiently for n<1729 cities, wouldn't that be interesting -- at least
until something better came along? Wasn't the five-color proof
interesting? (I grant that what JSH is suggesting here does not seem to
be interesting, but that's a different issue.)

 

[Patricia Shanahan]

Well, doesn't that depend on the individual special case? I mean, say
someone came up with an algorithm that could be proven to work
efficiently for n<1729 cities, wouldn't that be interesting -- at least
until something better came along? Wasn't the five-color proof
interesting? (I grant that what JSH is suggesting here does not seem to
be interesting, but that's a different issue.)

I'm assuming one is allowed to choose both the algorithm and the simple
case, as JSH is doing when he argues that I should be convinced that an
algorithm he wrote works because it gets the right answer for a single
example he selected.

Patricia

 

[Junoexpress]

We pay people to get complex answers, not to just get answers.

It's publish or perish in the academic world. Simple answers do not
necessarily drive a lot of papers.

What you call "complex" is really "simple". Problems are generalized
because it makes possible the solution of a wide range of problems
with the same structure. That is simplification, not complexity. Such
work may be detailed or difficult to understand, but one thing it is
*not* is complex in the sense of making things unnecessarily
complicated. To me, what you do, going down a million blind alleys
without a clue, is inefficient and unnecessarily complex.

The sad fact is that the simple solution train left the station a
couple of centuries ago. If you want problems dealing with the
physical world, having nice simple solutions that can be solved on the
back of an envelope, pick up a book on the history of math and work
through some of the problems Bernoulli, Descartes, and Fermat tackled
back in the 1600 and 1700's. They may be more your speed and
consistent with your abilities.

M

 

[Joshua Cranmer]

So Patricia Shanahan and Joshua Cranmer kept ignoring the reality of a
worked simple example to claim that I wasn't actually doing TSP!

A point already belabored to death by others, but I wish to point out
again that one example is not sufficient to demonstrate the efficacy of
a solution. You have not shown us any strenuous cases--even four nodes
alone is insufficient to demonstrate a solution since there is (in your
algorithm) essentially but a choice between two that needs to be
decided. That's why I suggest around 7 to 8, small enough to be handled
easily by manpower but big enough to not be trivial.

Against it, proof does not work. Explanation does not work.

You have provided neither (to the satisfaction of the heavyweights in
this group), so how can you say?

But here, you're fighting to hide an algorithm to solve the TSP, and
prove that P=NP, once and for all.

Actually, as I mentioned earlier, I personally do believe that P=NP, I
just don't believe that your algorithm solves it.

If, in fact, you are so sure of your solution, why don't you submit it
to the Clay Institute to claim the prize?

 

[Christian]

Ok, way over the top as clearly this discussion has degenerated to a
point where there is no point in continuing, so after this post, I'm
done for now.

I know how this goes having had proof after proof, result after
result, blocked by people who literally would often call me insane.

Proof does not always work in the real world.

It's not fair, but that's the reality.

But the dark side of it is that catastrophe is too often preventable,
but is not prevented because there are comfortable people who say
nothing is wrong.

Like consider the economy in the US today: many rich and powerful
people feel no problems so like the Bush advisor talking of a "mental
recession", they see no reason for meaningful change.

Or for better solutions...

Oh yeah, global warming will not be addressed by rich and powerful
nations for that reason--until and if it takes away their richness and
power.


James Harris

I personnaly would recommend you to write down your proof that the
algorithm works in formal language.
If you believe in it and it works that shouldn't be too hard. After
having it written down either flaws might be better visible or if
written down in program code obviously findable.
As you might have realised asking here for help writing it is probably
not gonna work.

Christian

 

[Christian]

Actually, as I mentioned earlier, I personally do believe that P=NP, I
just don't believe that your algorithm solves it.

Would be interesting to have a voting in this group to what others
believe.. independent of this threads algo.

Personally Iwould rather see P != NP as P = NP would have some very
strange implications. Most important for me:
"Effective guessing is possible". That one can actually guess some
solution without knowloedge in a way that is better than just picking
something randomly.

Anyone else want to make a guess?


Once had the idea to open a betting agency for geeks where you could bet
on mathematical problems. With the interest of the bets one could
finance Mathematical research to get the problems Verified or Falsified.

Christian

 

[Rotwang]

But that's false.

Even with just a single weight you can graph the nodes one a two-
dimensional plane and simply give them a distance from each node equal
to the size of the weight in whatever units you prefer, though you'd
have to adjust them so that you get all the weights correctly, but
then you'd have physical coordinates.

No, in general you can't. Several people have already independently
pointed out an obvious way to construct examples of weighted graphs
which can't be embedded in a 2-dimensional plane (or any metric space)
with distances equal to the weights, namely by constructing a weighted
graph which doesn't satisfy the triangle inequality.

 

[willo_thewisp]

No, in general you can't. Several people have already independently
pointed out an obvious way to construct examples of weighted graphs
which can't be embedded in a 2-dimensional plane (or any metric space)
with distances equal to the weights, namely by constructing a weighted
graph which doesn't satisfy the triangle inequality.

My understanding of James's "algorithm" is this: To each edge E, you
are given
a weight w(E). Now immerse your graph in 2-space any way you like
(surely you
can always do this; just place the vertices pretty much anywhere,
subject to the
condition that no two edges overlap); this assigns to each edge E a
length
l(E). Now do something or another that involves both the l's and the
w's,
and in the end you'll get a result that depends on just the w's.

On the face of it, this sounds implausible but not impossible. On the
other
hand, James is probably far too confused (and certainly far too
stupid) to
figure out whether this is really what he means or not.

 

[thufir]

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)

Ooh, that's a good one because, of course, you cannot disprove it. Also,
it's nicely self-referential because it, of course, *is* a conspiracy
theory, whose purpose, according to said theory, is to make people
believe in a conspiracy theory, such as itself...ouch, my head hurts



-Thufir