J
JSH
A little while back I posted for a while on a creative algorithm I
came up with for tracing out a path through nodes, and discussions got
bogged down on the issue of whether or not it solved the TSP, where
the consensus of several members was that it did not. But I have made
a project for the full algorithm at Google Code for coding in java and
while the welcome mat for coders has been put out, I have no
responses, so I have decided to talk more about the algorithm here
with the Euclidean TSP as I realized it'd be simpler to explain.
I will not give the full detailed algorithm here as I wish to simply
explain, but the gist of it is that you have TWO travelers who start
from the same node, every node is connected to every other node, and
the weight is the distance between nodes as it's the Euclidean
Traveling Salesman Problem being considered, and the two travelers
choose nodes such that they stay as physically close together as
possible where they can't choose the same node.
The weird thing in considering that as a solution is wondering how
local choices can have a global impact as playing with any TSP problem
for any length of time can, I'm sure, lead to the belief that the main
issue has to do with unknowns far away from the initial nodes, while
my idea says that local choices from BOTH sides of the path solve the
problem, so to help understand how local solves global, consider two
other travelers not using the algorithm.
To make it easier to imagine let's say the nodes are cities, and you
have two teams, where both teams are couples, and they all start from
the same city, but as they travel through all nodes--say, going
through European cities--they avoid again going to the same city, or
to a city their couple has already visited, but the first couple tries
to stay as close together physically as possible in their choices
while the other couple doesn't care, and makes different choices.
What happens after iteration 1?
Well the first couple has moved from the starting city to two other
different cities, choosing them such that their physical distance
apart is the LEAST possible given all possible city choices, while the
other couple has gone to different cities for some other reason, so
what do we now know?
We know that the second couple is further away from each other as they
traveled FARTHER than the first and MUST eventually make up that
distance, as eventually they come back together, so we already know
that the second couple has already traveled further and will have to
travel still further to make up the distance than the first. It's
like a double whammy. They traveled to more distant cities, and are
farther apart so will have a greater distance to travel in coming back
together down the line.
You may say, but what about the second choice, and the next and the
next?
Well, in each case the first couple remains as close as possible so
the second couple gets further behind, but can actually catch up as
the first couple can kind of bounce off each other if they're
traversing through very close cities until they're forced apart by
running through all of those so they have to get further apart as they
go to unvisited cities, so here is where the other couple can start
catching up.
Eventually each couple comes to a point where they're each at the last
two cities, so they can just pick one at which to meet, or there is
only one city left in the middle and they both move forward to meet
there, and tracing out the two routes you have just two routes along
which you can imagine a SINGLE traveler.
So at the end of the exercise you can collapse out the second traveler
and have a route for a single traveler in each case.
My hope is that pondering that problem and how each local choice leads
to a global result: distance apart, will help understanding of how
this algorithm works, and why it works.
Maybe the simplest thing for those of you who actually play with TSP
problems is to trace out a route for a Euclidean TSP, using two
travelers, where one starts at the end and works back to one starting
from the beginning and working forward and check the distance between
them at any point, versus two travelers using a non-optimal path.
My problem solving methods often involve using additional variables--
more degrees of freedom--which just help with solving the problem but
collapse out from the final solution and here using two travelers
allows a handle to be placed on the optimal path, which handles the
global problem piecewise with local decisions from BOTH ends.
I generalized the full algorithm to handle the TSP in general, where
you may not necessarily have distance information, and then I
generalized to situations where all nodes are not connected to every
other node, and got the full algorithm for what I call the optimal
path engine, or the OPE, which is waiting to be designed and coded.
The project space is optimalpathengine at Google Code. There is also
a newsgroup:
http://groups.google.com/group/optimalpathengine
Where you can discuss the idea including criticizing it if you like.
I'll only manage to the extent that I keep out flaming or any other
kind of deliberately disruptive behavior, so if you post there
disagreement with the idea, don't worry I won't get rid of it, though
if you're looking to simply sabotage the project with criticism, no
need to bother as so far nothing is happening anyway, which is why I'm
posting.
As a sidenote, for those interested in more in theory, if you look for
paths that are not round trip, so you're going to have a starting
node, and a different ending node, the algorithm behaves rather
interestingly in that if you start and finish at opposite ends then
the algorithm works in reverse in that you have the travelers pick in
a way that maximizes the distance between them, as otherwise they will
take the LONGEST path. Also, you can get the longest path with the
original by having them pick to maximize the distance between them.
Oh yeah, in closing, if this algorithm does work to pick the shortest
path then it proves that P=NP which is worth mentioning because the
solution then explains why "hard" problems are hard as they require
additional degrees of freedom not evident in the final solution e.g.
the second traveler of the algorithm and the distance between the two
travelers.
These additional degrees of freedom give the range necessary for
solving NP hard problems, but are invisible to people searching for
solutions unless they figure out an angle, so they can work for as
long as they won't and find various techniques that don't provide a
general solution, and yes, I have used additional variables in other
areas and I did go to TSP because I had this insight about this
problem solving approach and the TSP was the natural thing to
consider. The approach I use was born December 1999 out of attempts
at proving Fermat's Last Theorem. I'd exhausted very way I knew of
paying with x^p + y^p = z^p, so I thought to myself, wouldn't it be
neat if I had more degrees of freedom? So I've used the approach now
for over 8 years with amazing successes that are the subject of
controversy.
Another example of a problem where I used an additional degree of
freedom is my prime counting function, which is worth mentioning again
because of the reception it receives, as in chilly. There I found a
much simpler way to count prime numbers than is currently taught where
I have a P(x,y) function (fully mathematicized, but a P(x,n) in sieve
form), versus the pi(x) function of traditional mathematics.
It has been six years since that innovation. I have little
expectation that a solution proving P=NP would be rapidly picked up--
against the intuition or gut feelings of many of you I'm sure--but
fully expect MASSIVE resistance against the solution without any
objections being given that show the idea is actually flawed!!!
Amazingly enough.
(Consider that I actually had some of my research published in a
mathematical journal once. Readers on the sci.math newsgroup found
out about it, some conspired in posts an email campaign against the
paper. The editors just yanked my paper after that email campaign,
after publication, as it was an electronic journal, so they just left
a gap! They managed one more edition and then the entire math journal
shut-down. Its hosting university, Cameron University, part of the
Oklahoma state university system, removed ALL MENTION of the journal
from its website. That math journal had been around for 9 years. The
mathematical paper published in it over that timeframe might have been
lost except EMIS maintained the archives. Don't believe that amazing
story? See for yourself:
http://www.emis.de/journals/SWJPAM/
Link to edition that HAD my paper:
http://www.emis.de/journals/SWJPAM/vol2-03.html
An entire mathematical journal died quietly over a controversial paper
accepted from a supposed "crackpot" and the world just kept on going
like nothing happened. No big news story. No intrepid reporters from
ANY of the world's press that bothered to care--even though I tried to
bug them about it!!!
Revolutionary results run into the problem of defense against the
truth.)
But I could be wrong, so here's this post to see. Obviously if you
study this idea and see viability or prove it (remember you can trace
out actual Euclidean TSP solutions) then you can sign on and help
design and code the OPE. Even if you think I'm right, make no
mistake, it could take YEARS or even decades before the world accepts
the truth as that's how it really works, unlike fantasies some may
have from stories, legends or Hollywood movies. The fantasy world is
not the reality. Reality is a slog through the mud, and massive
resistance against the truth, and lots of people maybe willing to say
really mean things to you for a period of years.
There is no instant on, I like to say. So you can face ridicule, or
mostly being totally ignored for years no matter what you can prove,
or demonstrate even with a program. So only those who can move
forward without that social stuff like approval and accolades need
even consider signing on.
James Harris
came up with for tracing out a path through nodes, and discussions got
bogged down on the issue of whether or not it solved the TSP, where
the consensus of several members was that it did not. But I have made
a project for the full algorithm at Google Code for coding in java and
while the welcome mat for coders has been put out, I have no
responses, so I have decided to talk more about the algorithm here
with the Euclidean TSP as I realized it'd be simpler to explain.
I will not give the full detailed algorithm here as I wish to simply
explain, but the gist of it is that you have TWO travelers who start
from the same node, every node is connected to every other node, and
the weight is the distance between nodes as it's the Euclidean
Traveling Salesman Problem being considered, and the two travelers
choose nodes such that they stay as physically close together as
possible where they can't choose the same node.
The weird thing in considering that as a solution is wondering how
local choices can have a global impact as playing with any TSP problem
for any length of time can, I'm sure, lead to the belief that the main
issue has to do with unknowns far away from the initial nodes, while
my idea says that local choices from BOTH sides of the path solve the
problem, so to help understand how local solves global, consider two
other travelers not using the algorithm.
To make it easier to imagine let's say the nodes are cities, and you
have two teams, where both teams are couples, and they all start from
the same city, but as they travel through all nodes--say, going
through European cities--they avoid again going to the same city, or
to a city their couple has already visited, but the first couple tries
to stay as close together physically as possible in their choices
while the other couple doesn't care, and makes different choices.
What happens after iteration 1?
Well the first couple has moved from the starting city to two other
different cities, choosing them such that their physical distance
apart is the LEAST possible given all possible city choices, while the
other couple has gone to different cities for some other reason, so
what do we now know?
We know that the second couple is further away from each other as they
traveled FARTHER than the first and MUST eventually make up that
distance, as eventually they come back together, so we already know
that the second couple has already traveled further and will have to
travel still further to make up the distance than the first. It's
like a double whammy. They traveled to more distant cities, and are
farther apart so will have a greater distance to travel in coming back
together down the line.
You may say, but what about the second choice, and the next and the
next?
Well, in each case the first couple remains as close as possible so
the second couple gets further behind, but can actually catch up as
the first couple can kind of bounce off each other if they're
traversing through very close cities until they're forced apart by
running through all of those so they have to get further apart as they
go to unvisited cities, so here is where the other couple can start
catching up.
Eventually each couple comes to a point where they're each at the last
two cities, so they can just pick one at which to meet, or there is
only one city left in the middle and they both move forward to meet
there, and tracing out the two routes you have just two routes along
which you can imagine a SINGLE traveler.
So at the end of the exercise you can collapse out the second traveler
and have a route for a single traveler in each case.
My hope is that pondering that problem and how each local choice leads
to a global result: distance apart, will help understanding of how
this algorithm works, and why it works.
Maybe the simplest thing for those of you who actually play with TSP
problems is to trace out a route for a Euclidean TSP, using two
travelers, where one starts at the end and works back to one starting
from the beginning and working forward and check the distance between
them at any point, versus two travelers using a non-optimal path.
My problem solving methods often involve using additional variables--
more degrees of freedom--which just help with solving the problem but
collapse out from the final solution and here using two travelers
allows a handle to be placed on the optimal path, which handles the
global problem piecewise with local decisions from BOTH ends.
I generalized the full algorithm to handle the TSP in general, where
you may not necessarily have distance information, and then I
generalized to situations where all nodes are not connected to every
other node, and got the full algorithm for what I call the optimal
path engine, or the OPE, which is waiting to be designed and coded.
The project space is optimalpathengine at Google Code. There is also
a newsgroup:
http://groups.google.com/group/optimalpathengine
Where you can discuss the idea including criticizing it if you like.
I'll only manage to the extent that I keep out flaming or any other
kind of deliberately disruptive behavior, so if you post there
disagreement with the idea, don't worry I won't get rid of it, though
if you're looking to simply sabotage the project with criticism, no
need to bother as so far nothing is happening anyway, which is why I'm
posting.
As a sidenote, for those interested in more in theory, if you look for
paths that are not round trip, so you're going to have a starting
node, and a different ending node, the algorithm behaves rather
interestingly in that if you start and finish at opposite ends then
the algorithm works in reverse in that you have the travelers pick in
a way that maximizes the distance between them, as otherwise they will
take the LONGEST path. Also, you can get the longest path with the
original by having them pick to maximize the distance between them.
Oh yeah, in closing, if this algorithm does work to pick the shortest
path then it proves that P=NP which is worth mentioning because the
solution then explains why "hard" problems are hard as they require
additional degrees of freedom not evident in the final solution e.g.
the second traveler of the algorithm and the distance between the two
travelers.
These additional degrees of freedom give the range necessary for
solving NP hard problems, but are invisible to people searching for
solutions unless they figure out an angle, so they can work for as
long as they won't and find various techniques that don't provide a
general solution, and yes, I have used additional variables in other
areas and I did go to TSP because I had this insight about this
problem solving approach and the TSP was the natural thing to
consider. The approach I use was born December 1999 out of attempts
at proving Fermat's Last Theorem. I'd exhausted very way I knew of
paying with x^p + y^p = z^p, so I thought to myself, wouldn't it be
neat if I had more degrees of freedom? So I've used the approach now
for over 8 years with amazing successes that are the subject of
controversy.
Another example of a problem where I used an additional degree of
freedom is my prime counting function, which is worth mentioning again
because of the reception it receives, as in chilly. There I found a
much simpler way to count prime numbers than is currently taught where
I have a P(x,y) function (fully mathematicized, but a P(x,n) in sieve
form), versus the pi(x) function of traditional mathematics.
It has been six years since that innovation. I have little
expectation that a solution proving P=NP would be rapidly picked up--
against the intuition or gut feelings of many of you I'm sure--but
fully expect MASSIVE resistance against the solution without any
objections being given that show the idea is actually flawed!!!
Amazingly enough.
(Consider that I actually had some of my research published in a
mathematical journal once. Readers on the sci.math newsgroup found
out about it, some conspired in posts an email campaign against the
paper. The editors just yanked my paper after that email campaign,
after publication, as it was an electronic journal, so they just left
a gap! They managed one more edition and then the entire math journal
shut-down. Its hosting university, Cameron University, part of the
Oklahoma state university system, removed ALL MENTION of the journal
from its website. That math journal had been around for 9 years. The
mathematical paper published in it over that timeframe might have been
lost except EMIS maintained the archives. Don't believe that amazing
story? See for yourself:
http://www.emis.de/journals/SWJPAM/
Link to edition that HAD my paper:
http://www.emis.de/journals/SWJPAM/vol2-03.html
An entire mathematical journal died quietly over a controversial paper
accepted from a supposed "crackpot" and the world just kept on going
like nothing happened. No big news story. No intrepid reporters from
ANY of the world's press that bothered to care--even though I tried to
bug them about it!!!
Revolutionary results run into the problem of defense against the
truth.)
But I could be wrong, so here's this post to see. Obviously if you
study this idea and see viability or prove it (remember you can trace
out actual Euclidean TSP solutions) then you can sign on and help
design and code the OPE. Even if you think I'm right, make no
mistake, it could take YEARS or even decades before the world accepts
the truth as that's how it really works, unlike fantasies some may
have from stories, legends or Hollywood movies. The fantasy world is
not the reality. Reality is a slog through the mud, and massive
resistance against the truth, and lots of people maybe willing to say
really mean things to you for a period of years.
There is no instant on, I like to say. So you can face ridicule, or
mostly being totally ignored for years no matter what you can prove,
or demonstrate even with a program. So only those who can move
forward without that social stuff like approval and accolades need
even consider signing on.
James Harris