Traveling salesman, idea, easy to program?
in [Java Programming]
|
From: JSH on 15 Jul 2008 00:33 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. James Harris
From: Patricia Shanahan on 15 Jul 2008 00:51 JSH wrote: > 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. .... Your algorithm looks rather more like a shortest path algorithm than a traveling salesman algorithm. How do you ensure that *every* node is visited in the solution? Patricia
From: Owen Jacobson on 15 Jul 2008 03:17 On Jul 15, 12:33 am, JSH <jst...(a)gmail.com> wrote: > 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. *massive snip* comp.programming would be a better forum for discussion of algorithms. comp.lang.java.programmer is concerned with the implementation details as they apply to Java. Followup-To set appropriately. However, I will say this: your algorithm is incomplete, as Patricia noted; it also relies on several concepts with no solid definition within the scope of the problem, like "straight-line distance"[0]. You may also have confused yourself by thinking in terms of "backwards in time" -- walking a graph to construct a path is the same operation no matter how you choose to look at the graph data. Finally, the phrase "I hope" does not constitute formal proof, and since this is your algorithm, you are responsible for formally proving that it is complete and has the complexity you think it does. -o [0] However, this is awfully suggestive of the "heuristic" employed in A* and other informed path search algorithms. You may be reinventing the wheel.
From: JSH on 15 Jul 2008 20:26 On Jul 14, 9:51 pm, Patricia Shanahan <p...(a)acm.org> wrote: > JSH wrote: > > 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. > > ... > > Your algorithm looks rather more like a shortest path algorithm than a > traveling salesman algorithm. How do you ensure that *every* node is > visited in the solution? > > Patricia Yeah I forgot to put in a crucial condition--which I had in mind-- which is that the two travelers do not travel to, nor consider the same node at the same time. So, for instance, if you had only three nodes, with the travelers at nodes at either end and one node in the middle, then you'd exit as neither traveler could move, and that may be a typical exit state. The other exit would be if each traveler is at their own node and no other nodes are available, but then you have the full path anyway. Regardless of whether this idea solves the problem it's interesting to consider the path that you'd get with the algorithm, which I'll formalize better here: Given two travelers T_1 and T_2 and m nodes N, where m is a natural number, each traveler can be at a particular node, and each node has a distance from every other node in the space. There is also a value associated with the path from each node to another, which for simplicity can be considered to be the time of travel from that node to the other. For instance, if it takes two hours to go from N_1 to N_2, then that time is what's used in considered a traveler at N_1 considering going to N_2. Assume T_1 is at N_1 and T_2 is at N_m. For the first iteration T_1 considers moving to N_2, and then T_2 considers moving to each node in turn EXCEPT N_1 or N_2 as it excludes the node that T_1 is already at, and also excludes the one being considered. For each potential move T_2 calculates the time from N_m to that node and then it calculates the straight line distance to T_1 at N_2--not at N_1, as it is checking where T_1 will be--and it multiplies the time for that move times the distance to T_1, and stores that data. After T_2 has gone through every possible it simply takes the one that is smallest time*distance, and stores that info. Now T_1 considers moving to another node, like N_3, to keep it simple, and T_2 does the same calculation again, and stores the smallest time*distance. This process continues until all possible moves by T_1 are done, and now T_1 has a set of times*distance values from the calculations by T_2, and selects the smallest one. Now both T_1 and T_2 actually move to their respective nodes given by that smallest value. Now nodes N_1 and N_m are removed from consideration. And you have a complete iteration. Note that you have (m-2)^2 checks, if the travelers start at different nodes, for the first iteration and (m-4)^2 for the next and so forth, so the algorithm is polynomial time. T_1 and T_2 continue until there are no more nodes available or there is only one node available. Note that in the latter case then EITHER can move to complete, so you can arbitrarily say that T_1 moves forward in that case. And that is how every node is reached. Note: To have a complete circle back to a starting point, you have both T_1 and T_2 start at the same node, like N_1. So that's the more abstract explanation. The fuller one was given before where T_1 is the forwards traveler and T_2 is the backwards traveler going backwards in time. Intriguingly, this approach can lead to a shortest path algorithm with some rule adjustments, but I won't digress on that point now. I am seriously thinking of programming a Java implementation and putting it on Google Code. It would be nice to have help. James Harris
From: Lew on 15 Jul 2008 21:14
Patricia Shanahan wrote: >> Your algorithm looks rather more like a shortest path algorithm than a >> traveling salesman algorithm. How do you ensure that *every* node is >> visited in the solution? JSH wrote: > Yeah I forgot to put in a crucial condition--which I had in mind-- > which is that the two travelers do not travel to, nor consider the > same node at the same time. So, for instance, if you had only three > nodes, with the travelers at nodes at either end and one node in the > middle, then you'd exit as neither traveler could move, and that may > be a typical exit state. You just provided the example that proves Patricia's objection is valid. It shows that your algorithm does not solve the Traveling Salesman problem in what is nearly the simplest case. -- Lew |