Home  Forums  Reviews  Guides  Newsgroups  Register  Search 
Thread Tools 
JSH
Guest
Posts: n/a

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 nodessay, going through European citiesthey 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 nonoptimal path. My problem solving methods often involve using additional variables more degrees of freedomwhich 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 surebut 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 shutdown. 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/vol203.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 careeven 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 




JSH 


 
Owen Jacobson 


 
Joshua Cranmer
Guest
Posts: n/a

JSH wrote:
> 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. No matter how many levels you look through in local optimization, unless you look at all the nodes globally, you'll find that a bad choice could exist just beyond wherever you look. > 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. I doubt this will be an optimal path, but I don't have the time right now to confirm. In any case, the antics of the second couple is still undefined, AFAICT.  Beware of bugs in the above code; I have only proved it correct, not tried it.  Donald E. Knuth 




Joshua Cranmer 
JSH
Guest
Posts: n/a

On Aug 17, 11:24*am, Owen Jacobson <(EMail Removed)> wrote:
> On Aug 17, 2:04*pm, JSH <(EMail Removed)> wrote: > > > 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. > > [snip] > > You've opened a project which, if successful, will aggrandize you and > nobody else, and if unsuccessful, will waste everyone involved's > time. *It's no surprise you've gotten no responders: for that sort of Well I don't exactly agree with that but if that is someone's assessment of the situation then I can understand why they'd stay away from the project. > work, you need to *pay* people. *You'll have better luck with > Rentacoder than with Google Code. Hey, you may be right. I'm just putting the opportunity out there. It's up to individuals to make their own decisions, as always, whether or not to join a particular open source project. James Harris 




JSH 
JSH
Guest
Posts: n/a

On Aug 17, 11:31*am, Joshua Cranmer <(EMail Removed)> wrote:
> JSH wrote: > > 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. > > No matter how many levels you look through in local optimization, unless > you look at all the nodes globally, you'll find that a bad choice could > exist just beyond wherever you look. The global decision is limiting the distance between the two travelers. So a bad choice takes them farther away from each other which is distance that has to be made up as eventually they come together creating a longer path than optimal. So the algorithm actually uses a global variable at EACH decision point, which is a subtle but very important point. The optimal path engine actually uses GLOBAL information that is minimized by local choices that chop the problem up from BOTH ends, which is the deceptively simple leap needed to solve the problem which also points to how to solve any NP hard problem. > > 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. > > I doubt this will be an optimal path, but I don't have the time right > now to confirm. In any case, the antics of the second couple is still > undefined, AFAICT. Without following the optimal path algorithm no matter what they do they will end up having a greater distance to make up in order to get closer to each other. Simplest thing I think is to just trace out known Euclidean TSP solutions with two travelers, where one starts at the end while the other starts at the beginning and look at how the distance between them behaves. Trivially, for ANY optimal path, the total distance they travel in meeting each other must be the minimum, but the debate then is whether or not they can make decisions where locally they make a decision that increases that distance more than another choice would but still get the minimum path, which intuitively may seem to be possible. But if that is your intuition then in this case it is wrong. My guess is that the best way to prove it is in phase space but that gets to a more complicated discussion. It is maybe for many a counterintuitive solution which will be VERY hard to accept if you've played with the TSP a lot and have an ingrained belief that local decisions can't be global as well because of a global variable that is being locally decided upon. But that's why starting from scratch can be such a useful way to solve problems. For some of you, unlearning what you think you know about the TSP may be the hardest thing here, which could actually be somewhat painful if you've invested a lot of mental energy in learning things that ultimately turn out to be quite wrong. Unlearning can take as much time as learning and can be literally painful, so people avoid it like they avoid pain in general. James Harris 




JSH 
Patricia Shanahan
Guest
Posts: n/a

JSH wrote:
> 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 don't see any need for a team project on this. Take a look at http://groups.google.com/group/comp....1bbb43303d1fbc In it, I posted code for a simple test environment for the java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem that I thought would result in a suboptimal path in the algorithm as you had posted it, and a brute force solver. I wrote the program during a coffee break from my research, no multiprogrammer, multiday project needed. All you need to do is to make two copies of that program. Keep one with my brute force solver, and rewrite the solve() method in the other to use the latest and best version of your algorithm. Try the problem I gave. Try other problems. See if your algorithm always picks a cycle with as low a cost, within Java double accuracy, as the one selected by the brute force algorithm. Of course, there are more sophisticated and flexible ways of doing this, but I don't think they are worth the effort until my simple approach has been used to its limits. The brute force solver is exponential time, so it will not be usable for large problems, but it only takes a few seconds for a problem with twelve nodes, so you should be able to test a good range of small problems. You can, of course, stretch it to slightly bigger problems by allowing it to run for a day or two, but it will never be useful for even moderate size problems. Let me know if your algorithm works correctly for all the largest, most difficult problems you can think of that are small enough for the brute force solver. At that point, I may look at your code and think about new challenge problems for it. Patricia 




Patricia Shanahan 
Joshua Cranmer
Guest
Posts: n/a

Time to put my visualization skills back together with graphs instead of
merely thinking about amorphous inheritance charts... JSH wrote: > 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 two travelers are near each other. That's about it. Let me show you an example of where this fails. This is the weight table: A B C D E F A  10 10 5 5 1 B 10  1 6 6 4 C 10 1  6 6 4 D 5 6 6  2 5 E 5 6 6 2  5 F 1 4 4 5 5  That should be Euclidean. Start on A. Travelers look for the closest pair of nodes. These are B and C. So the path has an A>B and an A>C route, costing 20 so far. Next pair of close nodes: D and E. Since the distance is the same, it doesn't matter whether the one on B goes to D or vice versa; the extra cost is 12, to a cumulative of 32. One node left, F, which costs an extra 10 for both to come to. The total is 42. There is a shorter path (I'm fairly sure it's the shortest, but I'm not going to make that claim). Go from A to B (10) to C (total 11) to D (17) to E (19) to F (24) to A again (25). It is, however, better than the path your algorithm gives. Analytically, why does it fail? If you picture a group of nodes, two of which are far out of the way but extremely close, the shortest tour must necessarily travel between them so that it pays the travel cost of going out there only twice instead of four times. Your previous attempt to resolve a case where you had to visit nodes in a certain sequence by declaring "try starting at every node" won't work here again, because I could have an arbitrary number of remote node pairs. I have a strong intuition that factoring in the distance to get to the pair as well as their proximity won't work, but to be sure, I'd have to play around with some graphical utilities. I haven't seen Patricia's application, but if it had a GUI that allowed you to put nodes in, it would ease the burden of trying to come up with the edge cases. > 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. Another easy graphical example: imagine a circle, and at several points, you had pairs of nodes straddling the circle. Your algorithm will have the travelers moving in pairs around the circle, which means the path is approximately twice the circumference; the optimal path will go between the nodes in a zigzaglike fashion, at approximately the circumference. > 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. I'm tempted to say that this algorithm will perform poorly in realworld circumstances: when nodes aggregate in clusters, it moves between clusters in pairs whereas optimal solutions will only travel once between clusters.  Beware of bugs in the above code; I have only proved it correct, not tried it.  Donald E. Knuth 




Joshua Cranmer 
Patricia Shanahan
Guest
Posts: n/a

Joshua Cranmer wrote:
.... > I have a strong intuition that factoring in the distance to get to the > pair as well as their proximity won't work, but to be sure, I'd have to > play around with some graphical utilities. I haven't seen Patricia's > application, but if it had a GUI that allowed you to put nodes in, it > would ease the burden of trying to come up with the edge cases. No GUI, but the nodes are specified by coordinates, and it calculates the Euclidean distances from them. That means you can play with any visualization system from which you can extract coordinates. Patricia 




Patricia Shanahan 
JSH
Guest
Posts: n/a

On Aug 17, 1:16*pm, Joshua Cranmer <(EMail Removed)> wrote:
> Time to put my visualization skills back together with graphs instead of > merely thinking about amorphous inheritance charts... > > JSH wrote: > > 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 two travelers are near each other. That's about it. > > Let me show you an example of where this fails. This is the weight table: > * * A *B *C *D *E *F > A * 10 10 *5 *5 *1 > B 10 * *1 *6 *6 *4 > C 10 *1 * *6 *6 *4 > D *5 *6 *6 * *2 *5 > E *5 *6 *6 *2 * *5 > F *1 *4 *4 *5 *5 * > > That should be Euclidean. Why? If A to B is 10 and A to C is 10, then they are on an arc centered at A, so I see you're not on a grid. But you have A to F at 1, while F to B and F to C is 4. There is no way on a flat plane that those distances can work. If you're moving to higher dimensions you should so state, but even going to a surface in 3d I don't readily see one that will work, and I'm not bothering at this point to consider a hyperspace surface though if you say that is necessary I may. James Harris 




JSH 
JSH
Guest
Posts: n/a

On Aug 17, 12:32*pm, Patricia Shanahan <(EMail Removed)> wrote:
> JSH wrote: > > 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 don't see any need for a team project on this. Take a look athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43... > > In it, I posted code for a simple test environment for the > java.lang.Math.sqrt approximation to Euclidean TSP. I included a problem > that I thought would result in a suboptimal path in the algorithm as you > had posted it, and a brute force solver. I wrote the program during a > coffee break from my research, no multiprogrammer, multiday project > needed. Ok, I checked the link and it seems simple enough. To help see that your intuition is wrong though I suggest you make one simple addition which should not take you long given the short time you say the original post took. Not even a full coffee break! I suggest you output the distance between two travelers with one going backwards along the path as I've explained previously, at each decision point for each of your brute force attempts. That means you will have a graph of step and distance, which is phase space, for each. > All you need to do is to make two copies of that program. Keep one with > my brute force solver, and rewrite the solve() method in the other to > use the latest and best version of your algorithm. Try the problem I > gave. Try other problems. See if your algorithm always picks a cycle > with as low a cost, within Java double accuracy, as the one selected by > the brute force algorithm. You're focused on the desired goal while I'm solving the problem in phase space, which I know GIVES the desired goal, which is kind of counterintuitive. In phase space the minimum path will traverse the minimum separation between the two travelers at each decision point. That will give the optimal path which is equivalent to picking the cycle with the lowest cost in the Euclidean TSP, as the Euclidean always (thankfully) gives what I call a perfect graph, which means you can pick any node to start. > Of course, there are more sophisticated and flexible ways of doing this, > but I don't think they are worth the effort until my simple approach has > been used to its limits. > > The brute force solver is exponential time, so it will not be usable for > large problems, but it only takes a few seconds for a problem with > twelve nodes, so you should be able to test a good range of small > problems. You can, of course, stretch it to slightly bigger problems by > allowing it to run for a day or two, but it will never be useful for > even moderate size problems. > > Let me know if your algorithm works correctly for all the largest, most > difficult problems you can think of that are small enough for the brute > force solver. At that point, I may look at your code and think about new > challenge problems for it. > > Patricia I believe I have a solution from considering phase space so am not interested in playing with your code, while I think it might be a useful exercise for you to add the second traveler to it and see what happens when you look over the distance between travelers as explained. My algorithm turns the problem into finding the minimum path through phase space with only two variables: distance between the two travelers and decision point. IN phase space the minimum corresponds with minimizing the distance between the two travelers at EACH decision point, which is how local decisions impact a global variable, and in phase space every path maps to a unique phase space set of decision points and distances between travelers. James Harris 




JSH 


 
Thread Tools  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
how can i get particular datafrom #<Net::HTTP google.co ope  Priyank Shah  Ruby  2  09142010 04:51 AM 
My TSP idea, google code and google group, thanks!  JSH  Java  0  08032008 05:43 PM 
Distance normalized TSP algorithm  JSH  Java  18  07272008 03:31 AM 
Richard Heathfield's TSP permutation algorithm  whitehatmiracle@gmail.com  C Programming  12  09222006 10:12 AM 
How to get CiscoIOSTSP3.1.zip (TSP Light TAPI driver)?  Cisco  0  06182005 08:19 AM 
Powered by vBulletin®. Copyright ©2000  2014, vBulletin Solutions, Inc..
SEO by vBSEO ©2010, Crawlability, Inc. 