J

#### JSH

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.

James Harris