Thursday, July 24, 2008

 

Distance normalized TSP algorithm

I came up with this idea for figuring out a path with the Traveling Salesman Problem and posted about it, and an objection that came up was the the algorithm required the distance between each of the nodes, while the standard problem does not require this information.

In reaction to that objection I got upset, but now after taking some time to think and ponder the problem I found I could handle the issue easily so that a new distance normalized algorithm could handle any TSP setup.

The simple idea is that if there are m nodes, and there is no distance information between nodes given, then they are to be considered to be embedded in an m−1 dimensional space equidistant from each other.

Then the algorithm proceeds as before, where you have two travelers T1 and T2, where I'll talk through a single weight, but you can have multiple weights. With a single weight between nodes, I'll use cost to keep the idea closer to the standard way of stating the problem, and also so that they complete a round trip circuit, I'll say they begin from the same node N1.

To use the algorithm and take them to the next nodes, T1 considers moving to another node, which I'll say is N2.

Then T2 considers moving to all other nodes available, not currently under consideration by T1, and not already visited, so T2 might start with N3 and proceed from there, and calculates the cost×distance from each path BACK to N1 because T2 is moving BACKWARDS, while T1 is moving forwards.

Notice that with the distance normalized algorithm you just have cost considered as distance=1. Also if there are multiple weights you simply multiply by each weight, so if there were a cost and a time for each path, you'd have cost×time×distance and so forth.

T2 considers every available move back to N1, and selects the one with the least value, and returns that information.

T1 stores that info and now considers moving to N3, and T2 now calculates for all available nodes again, excluding the one under consideration or already visited, so now T2 could start with N2 and loop through all available, and again T2 picks the lowest cost move BACK to N1 and returns that to T1.

In this way, all possible moves by T1 and T2 are considered, and after T1 has gotten values back from T2 for each possible move, T1 selects the lowest cost move, and then BOTH T1 and T2 make their moves, and T1 moves forward to the node that fits that least path, while T2 moves BACKWARD to the node that does, where those will be different nodes and there is a rule that T1 and T2 can never move to the same node.

A special case occurs if there are only 3 nodes left, meaning only one is unvisited, and in this case the algorithm arbitrarily has T1 move forward to that node.

Notice that when the algorithm exits you have a path taken by T1 and a path taken by T2, but you collapse that into a single journey by a single traveler moving along the path of T1, and then continuing forward along the path of T2, where to conceptualize it, T2 is the same traveler moving backwards in time to meet himself moving forwards.

I am prepared to step through a simple example if that is necessary but would not mind if someone else might help out in that regard, as I'm curious to know if ANYONE else in the world can understand this algorithm!!!

It seems so simple to me but often it's hard to explain something new to people so I understand that it may take some time and patience for others to know how to do the algorithm and I apologize for getting frustrated and angry before, versus just coming up with the normalized algorithm earlier.

Oh yeah, I'm still angling for coders if I can get some people interested in this thing, as I have a Google Code project called optimalpathengine.

Saturday, July 19, 2008

 

What I learned from Class Viewer

One of the reasons I bothered to create the open source project Class Viewer for Java was that I'd had years of arguing with math people on newsgroups which kind of happened by accident, as kind of as a lark I thought I'd ponder some math problems and talked about it. Yuck, what a mistake.

Math people ripped on me endlessly and told me to shut-up.

I got angry and refused and found I LIKED pondering math problems they had claimed as their exclusive property and screw them. Over the years I learned many of them are idiots and they lie a LOT. It is scary how much they lie about, and there's nothing you can do about it and most people will not believe it's true because they think these math people are geniuses.

So I did Class Viewer partly to convince myself that these people calling me insane, telling me I was "subhuman" and behaving very badly in many ways as they mounted a very successful smear campaign against me, were wrong.

To understand how successfully they smeared me, do a search on "James Harris" in Yahoo! where a hate page attacking my research comes up #6 last time I checked in Yahoo! and consider the millions of people with that name in the world, but somehow a hate page against me is so important?

So I wrote Class Viewer and sat back and waited and one day I pointed out on a math newsgroup that I had this open source project, and what did they do?

They ripped on it. They argued that it was worthless and not of value to anyone and pointed to the lack of activity on the SourceForge page as they maintained that I am just a crackpot loser.

Math people lie all the time.

If you agree then goddamn you if you ever use Class Viewer for Java and if you agree with them and have it now, delete it off your system.

Tuesday, July 15, 2008

 

Optimal path engine project, coders needed

Had this idea that should be simple to develop that goes after the Traveling Salesman Problem, where there is another thread where you can read details, but here I'm wondering if anyone would like to help code what I'm calling the optimal path engine.

I started a Google Code project: code.google.com/p/optimalpathengine

Trying to learn from my mistakes with my open source project Class Viewer for Java, I'm wanting to try and get as much outside help as possible which is the why for this post, versus it being a single developer project, though I'm sure I can code the entire algorithm myself.

It's to be all in Java as that is the language I use.

It'd be nice to have a project manager other than myself as it's tiring and I'm out of practice. It's been years since I actually worked as a developer where the highest I managed anyway was being a lead developer.

Here's my one try to be more community oriented as part of me would rather just be the absolute ruler of the project like I am with Class Viewer. But hey, maybe I should at least try to be more communal, so, I'm trying.

 

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.

Tuesday, July 01, 2008

 

JSH: We have a problem

Go local. Message. Finish it this time. Clear. Tag.

No permissions on the other. Hanging on a limb.

Code. Expedite. Time it.

Finish.
Across. Dog. Triangulate. Window. Fingerprint. Tag.

Finish.

This page is powered by Blogger. Isn't yours?