Tuesday, July 15, 2008
Traveling salesman, idea, easy to program?
Besides my open source Class Viewer project I have a rep for throwing ideas out on Usenet, where I did that for years with math, argued with a lot of math people, and they hate me, but that's a side issue to the subject of this post as I was wondering today what problem I might solve to kind of prove myself and came up with an algorithm for the traveling salesman problem.
My algorithm has TWO travelers: the forward traveler and the backwards traveler.
Where to understand the idea I don't have the traveler get back to his original destination at first, though that's easily added later.
The backwards traveler is actually the same traveler, but traveling backwards in time along the optimal path, so the assumption is that the problem is solved, but so what? What good is a backwards traveler added with the normal forward traveler?
Well, now you can optimize the path from both ends simply enough: with nodes and paths like normal, assume your forwards traveler is at the start while your backwards traveler is at the end.
Now the forwards traveler steps forward to a node, doesn't matter which one so say the closest to keep it simple. The backwards traveler then BACKS to each node that is left in turn, and at each calculates the time from that node—he's traveling backwards in time—and multiplies that for each node times its straight line distance to the forwards traveler at his node.
Then the backwards traveler just picks whichever node has the minimum time*straight-line distance value, and holds that value.
The forwards traveler now goes to another node, and the backwards traveler does the same thing as above, and they do this process until each first possible step is covered.
So now there is a series of values for each node for the forwards traveler, and he picks the one that is minimal, and then each traveler steps to the appropriate node for that path, which notice is covering the ends of your total path.
And then they do the same process again.
As they iterate through, they must eventually meet, so the forward times traveler meets himself going backwards through time and you have the minimal path—I hope.
You need one more rule: each node is only visited once, so as each node is visited paths to it are removed.
And that's it.
Looking over literature quickly while checking to see if anyone else already had this algorithm, I noticed that no one did and that the algorithms I saw looked forward only, while this approach chops the problem up iteratively from both sides, so you're solving it at both ends.
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.
The idea is generalizable to other limiting factors like cost, as you just multiply everything together, so like to get the shortest possible path in the shortest time with the shortest cost, you'd multiply distance*time*cost for each path and take the minimum.
Oh yeah, so how do you do the classical problem of getting back to your original destination?
Easy. Both travelers start from the same point, and otherwise everything is the same.
The proof that it is a solution has to do with other stuff more mathematical so I leave that off, as even if you don't think it does, how hard is that idea to program, eh?
And now you know how I got hated by mathematicians with my wild ideas and extreme creativity.
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?
So I think math people are the ones with the problem. Not me.
My algorithm has TWO travelers: the forward traveler and the backwards traveler.
Where to understand the idea I don't have the traveler get back to his original destination at first, though that's easily added later.
The backwards traveler is actually the same traveler, but traveling backwards in time along the optimal path, so the assumption is that the problem is solved, but so what? What good is a backwards traveler added with the normal forward traveler?
Well, now you can optimize the path from both ends simply enough: with nodes and paths like normal, assume your forwards traveler is at the start while your backwards traveler is at the end.
Now the forwards traveler steps forward to a node, doesn't matter which one so say the closest to keep it simple. The backwards traveler then BACKS to each node that is left in turn, and at each calculates the time from that node—he's traveling backwards in time—and multiplies that for each node times its straight line distance to the forwards traveler at his node.
Then the backwards traveler just picks whichever node has the minimum time*straight-line distance value, and holds that value.
The forwards traveler now goes to another node, and the backwards traveler does the same thing as above, and they do this process until each first possible step is covered.
So now there is a series of values for each node for the forwards traveler, and he picks the one that is minimal, and then each traveler steps to the appropriate node for that path, which notice is covering the ends of your total path.
And then they do the same process again.
As they iterate through, they must eventually meet, so the forward times traveler meets himself going backwards through time and you have the minimal path—I hope.
You need one more rule: each node is only visited once, so as each node is visited paths to it are removed.
And that's it.
Looking over literature quickly while checking to see if anyone else already had this algorithm, I noticed that no one did and that the algorithms I saw looked forward only, while this approach chops the problem up iteratively from both sides, so you're solving it at both ends.
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.
The idea is generalizable to other limiting factors like cost, as you just multiply everything together, so like to get the shortest possible path in the shortest time with the shortest cost, you'd multiply distance*time*cost for each path and take the minimum.
Oh yeah, so how do you do the classical problem of getting back to your original destination?
Easy. Both travelers start from the same point, and otherwise everything is the same.
The proof that it is a solution has to do with other stuff more mathematical so I leave that off, as even if you don't think it does, how hard is that idea to program, eh?
And now you know how I got hated by mathematicians with my wild ideas and extreme creativity.
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?
So I think math people are the ones with the problem. Not me.
# posted by James Harris @ 00:33 
