What I learned from Class Viewer
in [Java Programming]
|
From: Patricia Shanahan on 20 Jul 2008 11:08 rossum wrote: > On Sat, 19 Jul 2008 18:04:52 -0700 (PDT), JSH <jstevh(a)gmail.com> > wrote: > >> Like look at my Traveling Salesman Problem solution. > How can it be a solution if there are instances of the TSP which it > cannot solve? At best you have a partial solution. > >> If it is correct, how many researchers in this area are suddenly >> displaced by such a trivially easy algorithm? > "If it is correct ..." Do not get ahead of yourself James. First you > need to have a correct solution. Start by amending your initial > attempt so it can deal with Patricia's example that your current > algorithm cannot solve. I get the impression that his algorithm is not intended to handle that case. If so, it is not a solution to the problem researchers have been working on under the name "Traveling Salesman". It may be a solution to some other problem, possibly one of the restricted forms of TSP. The first step is to precisely define the problem it is designed to solve. Only JSH can do that. Until that is done it is impossible to know, for example, whether or not he is solving a problem whose decision form is NP-complete. It is also impossible to evaluate correctness without knowing what problem the algorithm is intended to solve. Patricia
From: JSH on 20 Jul 2008 13:55 On Jul 20, 4:12 am, rossum <rossu...(a)coldmail.com> wrote: > On Sat, 19 Jul 2008 18:04:52 -0700 (PDT), JSH <jst...(a)gmail.com> > wrote: > > >Like look at my Traveling Salesman Problem solution. > > How can it be a solution if there are instances of the TSP which it > cannot solve? At best you have a partial solution. > You can always get distances between every node to the other by just putting the nodes on a two-dimensional plane and saying one of the weights is a distance measure. So there are no instances for which my algorithm will not give an answer. > > >If it is correct, how many researchers in this area are suddenly > >displaced by such a trivially easy algorithm? > > "If it is correct ..." Do not get ahead of yourself James. First you > need to have a correct solution. Start by amending your initial > attempt so it can deal with Patricia's example that your current > algorithm cannot solve. > > rossum She added in additional weights which she did not give values for, though in her case those "weights" had to do with smuggling and gangs. A weight is ANYTHING that impacts the decision problem of whether or not a particular path should be taken. James Harris
From: JSH on 20 Jul 2008 14:01 On Jul 20, 8:08 am, Patricia Shanahan <p...(a)acm.org> wrote: > rossum wrote: > > On Sat, 19 Jul 2008 18:04:52 -0700 (PDT), JSH <jst...(a)gmail.com> > > wrote: > > >> Like look at my Traveling Salesman Problem solution. > > How can it be a solution if there are instances of the TSP which it > > cannot solve? At best you have a partial solution. > > >> If it is correct, how many researchers in this area are suddenly > >> displaced by such a trivially easy algorithm? > > "If it is correct ..." Do not get ahead of yourself James. First you > > need to have a correct solution. Start by amending your initial > > attempt so it can deal with Patricia's example that your current > > algorithm cannot solve. > > I get the impression that his algorithm is not intended to handle that > case. If so, it is not a solution to the problem researchers have been > working on under the name "Traveling Salesman". It may be a solution to > some other problem, possibly one of the restricted forms of TSP. > > The first step is to precisely define the problem it is designed to > solve. Only JSH can do that. I went the extra mile of working an example with 4 nodes which was the simplest I could think of, where you could have alternate paths. My algorithm did in fact pick the proper path, given an answer with paths only, as the distance information dropped away. My algorithm can be used against any TSP type problem, even if only a single weight is given and no distance information between nodes is given, by simply assuming that the weight is a distance between nodes and graphing the nodes on a two-dimensional plane. > Until that is done it is impossible to know, for example, whether or not > he is solving a problem whose decision form is NP-complete. It is also > impossible to evaluate correctness without knowing what problem the > algorithm is intended to solve. > > Patricia I worked an example so that people can see how the idea works. There isn't anything more I can do besides the general explanation, with the idea of a backwards traveler going back in time for people who like the wordy explanation, a more formalized explanation with symbols and variables AND a worked example showing the simplest case possible where the algorithm is stepped through to give a solution. There is nothing more that can be done when people obstinately refuse to be reasonable. I've done my best, as I've often done before, which is why I rely on objective measures people can't take away from me, like my Class Viewer program. I live in a world that doesn't like answers if I'm the person who gives them. That is my weight to bear. A weight often born by people like me, often hated in our own times. James Harris
From: Owen Jacobson on 20 Jul 2008 14:12 On Jul 20, 2:01 pm, JSH <jst...(a)gmail.com> wrote: > On Jul 20, 8:08 am, Patricia Shanahan <p...(a)acm.org> wrote: > > > > > rossum wrote: > > > On Sat, 19 Jul 2008 18:04:52 -0700 (PDT), JSH <jst...(a)gmail.com> > > > wrote: > > > >> Like look at my Traveling Salesman Problem solution. > > > How can it be a solution if there are instances of the TSP which it > > > cannot solve? At best you have a partial solution. > > > >> If it is correct, how many researchers in this area are suddenly > > >> displaced by such a trivially easy algorithm? > > > "If it is correct ..." Do not get ahead of yourself James. First you > > > need to have a correct solution. Start by amending your initial > > > attempt so it can deal with Patricia's example that your current > > > algorithm cannot solve. > > > I get the impression that his algorithm is not intended to handle that > > case. > > My algorithm can be used against any TSP type problem, even if only a > single weight is given and no distance information between nodes is > given, by simply assuming that the weight is a distance between nodes > and graphing the nodes on a two-dimensional plane. If that is so, then your algorithm should be able to provide a minimum- cost Hamiltonion circuit for the following complete graph: The graph contains five nodes (A, B, C, D, and E). The weights of the edges between nodes are as follows: A->B: 1 A->C: 1000 A->D: 1 A->E: 1 B->A: 1 B->C: 1000 B->D: 1 B->E: 1 C->A: 1000 C->B: 1000 C->D: 2000 C->E: 2000 D->A: 1 D->B: 1 D->C: 2000 D->E: 1 E->A: 1 E->B: 1 E->C: 2000 E->D: 1 You are free to treat these weights as distances, costs, combined distances and costs, number of donuts required, or any other "real world" quantity you like. The resulting path may begin at any node, must pass through each node other than the origin node exactly once, and must end at the origin node. For example, [E, C, D, A, B, E] is a valid circuit (but not a valid solution, as it is not minimum-cost), while [A, B, D, E, A] is not a valid circuit as a node is omitted. -o
From: rossum on 20 Jul 2008 15:36
On Sun, 20 Jul 2008 08:08:36 -0700, Patricia Shanahan <pats(a)acm.org> wrote: >rossum wrote: >> On Sat, 19 Jul 2008 18:04:52 -0700 (PDT), JSH <jstevh(a)gmail.com> >> wrote: >> >>> Like look at my Traveling Salesman Problem solution. >> How can it be a solution if there are instances of the TSP which it >> cannot solve? At best you have a partial solution. >> >>> If it is correct, how many researchers in this area are suddenly >>> displaced by such a trivially easy algorithm? >> "If it is correct ..." Do not get ahead of yourself James. First you >> need to have a correct solution. Start by amending your initial >> attempt so it can deal with Patricia's example that your current >> algorithm cannot solve. > >I get the impression that his algorithm is not intended to handle that >case. If so, it is not a solution to the problem researchers have been >working on under the name "Traveling Salesman". It may be a solution to >some other problem, possibly one of the restricted forms of TSP. > >The first step is to precisely define the problem it is designed to >solve. Only JSH can do that. > >Until that is done it is impossible to know, for example, whether or not >he is solving a problem whose decision form is NP-complete. It is also >impossible to evaluate correctness without knowing what problem the >algorithm is intended to solve. From his insistence on "distance" rather than "weight" I would suspect that he is trying to solve either the Euclidian TSP or the Metric TSP. rossum > >Patricia |