My OPE & the Euclicidean TSP

Discussion in 'Java' started by JSH, Aug 17, 2008.

  1. JSH

    JSH Guest

    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 nodes--say, going
    through European cities--they 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 non-optimal path.

    My problem solving methods often involve using additional variables--
    more degrees of freedom--which 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 sure--but
    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
    shut-down. 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/vol2-03.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 care--even 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, Aug 17, 2008
    #1
    1. Advertising

  2. On Aug 17, 2:04 pm, 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.


    [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
    work, you need to *pay* people. You'll have better luck with
    Rentacoder than with Google Code.
     
    Owen Jacobson, Aug 17, 2008
    #2
    1. Advertising

  3. 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, Aug 17, 2008
    #3
  4. JSH

    JSH Guest

    On Aug 17, 11:24 am, Owen Jacobson <> wrote:
    > On Aug 17, 2:04 pm, 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.

    >
    > [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, Aug 17, 2008
    #4
  5. JSH

    JSH Guest

    On Aug 17, 11:31 am, Joshua Cranmer <> 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 counter-intuitive 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, un-learning 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.

    Un-learning 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, Aug 17, 2008
    #5
  6. 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.lang.java.programmer/msg/c11bbb43303d1fbc

    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 multi-programmer, multi-day 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, Aug 17, 2008
    #6
  7. 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 zig-zag-like 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 real-world
    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, Aug 17, 2008
    #7
  8. 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, Aug 17, 2008
    #8
  9. JSH

    JSH Guest

    On Aug 17, 1:16 pm, Joshua Cranmer <> 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 3-d I don't readily see one that will work, and
    I'm not bothering at this point to consider a hyper-space surface
    though if you say that is necessary I may.


    James Harris
     
    JSH, Aug 17, 2008
    #9
  10. JSH

    JSH Guest

    On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day 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
    counter-intuitive.

    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, Aug 17, 2008
    #10
  11. JSH wrote:
    > On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day project
    >> needed.

    >
    > Ok, I checked the link and it seems simple enough.

    ....
    > 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.

    ....
    > 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.



    I don't have any travelers at all in my implementation, just a search
    through the set of permutations of the nodes starting with a given node.
    That makes it hard to add a "second traveler".

    In any case, my implementation of solve() is interesting only for
    verifying that a claimed solution to a non-trivial problem is actually
    optimal.

    Also, note that there are 11!, 39,916,800, Hamiltonian cycles
    considering a single start node in my twelve node case. I do prune the
    search space whenever the current permutation prefix has a higher cost
    than the best Hamiltonian cycle so far, but I would not expect that to
    help enough to make decision-by-decision output useful.

    The important thing is your Java implementation of your algorithm. All
    you need to do is replace my solve() with a method representing it. The
    rest of the code is useful for enabling identical problem specifications
    for your algorithm and the brute force method.

    Patricia
     
    Patricia Shanahan, Aug 17, 2008
    #11
  12. JSH

    Guest

    On Aug 17, 5:19 pm, JSH <> wrote:
    >
    > 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.  
    >
    >

    James, your stupidity truly is a natural wonder.
     
    , Aug 17, 2008
    #12
  13. JSH

    JSH Guest

    On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    > JSH wrote:
    > > On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day project
    > >> needed.

    >
    > > Ok, I checked the link and it seems simple enough.

    > ...
    > > 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.

    > ...
    > > 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.

    >
    > I don't have any travelers at all in my implementation, just a search
    > through the set of permutations of the nodes starting with a given node.
    > That makes it hard to add a "second traveler".


    You just take an outputted path and output the distance between nodes
    going from the outside in, for example if the path is

    ABCDEF

    then you'd output distances between A & F, B & E, and C & D.

    If you had

    ABCDEFG

    you'd output distances between A & G, B & F, and C & E, as with the
    algorithm, either traveler can move to E, so the algorithm exits after
    C & E.

    > In any case, my implementation of solve() is interesting only for
    > verifying that a claimed solution to a non-trivial problem is actually
    > optimal.
    >
    > Also, note that there are 11!, 39,916,800, Hamiltonian cycles
    > considering a single start node in my twelve node case. I do prune the
    > search space whenever the current permutation prefix has a higher cost
    > than the best Hamiltonian cycle so far, but I would not expect that to
    > help enough to make decision-by-decision output useful.


    That's the intuitive feel, but no other algorithm uses a global
    variable because none exists without additional degrees of freedom.

    My algorithm unlike others uses local decisions with a GLOBAL
    variable.

    > The important thing is your Java implementation of your algorithm. All
    > you need to do is replace my solve() with a method representing it. The
    > rest of the code is useful for enabling identical problem specifications
    > for your algorithm and the brute force method.
    >
    > Patricia


    You were arguing against the need for a multi-team effort to code my
    full optimal path algorithm based on code you stated you wrote on your
    coffee break.

    I merely noted how you could advance that code a little further to
    directly test this approach, and explained why I don't see a need to
    do so myself because of a phase space argument.

    I've further explained how you can simply do the addition after you
    noted you didn't have travelers in your code, where I gave you a
    specific example for how you output the desired information, giving
    the phase space results.

    To me it's about a solution that I can see which is counter-intuitive
    to people who have a serious intellectual investment in different
    beliefs, like your learned response that local decisions can't matter
    globally with the TSP.

    I'd gain little by using your code to prove something I feel I already
    know by other means, but you'd gain much more by making the addition
    to your code to quickly and easily see how your intuition is wrong.

    It shouldn't take as long as you took to do the original code, which
    you said you did on a coffee break.


    James Harris
     
    JSH, Aug 17, 2008
    #13
  14. JSH

    Guest

    On Aug 17, 10:40 pm, JSH <> wrote:
    >
    > On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    > > ...

    >
    > I'd gain little by using your code to prove
    > something I feel I already know...


    What Patricia is trying to say, in her very modest and polite way,
    is that it's obvious to all of us that your algorithm doesn't work.
    By using her framework, you can at least input a test case and see
    that
    your algorithm produces a lousy solution, and you can then
    compare and see the error of your way.

    > I'd gain little by using your code to prove
    > something I feel I already know...


    On the contrary, you have a lot to gain.
    Having a scientific test bench allows you to (potentially) prove that
    your algorithm truly works on all the test cases people throw at you.
    You will then have great credibility and people will have no choice
    but to take you very seriously.

    You're either delusional (and truly believe that you alone knows how
    to solve NP problem in P time), or you subconsciously are trying to
    avoid
    facing your own stupidity and thus you push away all the people trying
    to help you.
     
    , Aug 17, 2008
    #14
  15. JSH

    JSH Guest

    On Aug 17, 3:49 pm, "" <>
    wrote:
    > On Aug 17, 10:40 pm, JSH <> wrote:
    >
    >
    >
    > > On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    > > > ...

    >
    > > I'd gain little by using your code to prove
    > > something I feel I already know...

    >
    > What Patricia is trying to say, in her very modest and polite way,
    > is that it's obvious to all of us that your algorithm doesn't work.
    > By using her framework, you can at least input a test case and see
    > that
    > your algorithm produces a lousy solution, and you can then
    > compare and see the error of your way.


    All of us? So you speak for every member of the entire group
    worldwide?

    That is a sign of delusional thinking on your part.

    And I disagree with you. Disproof by counter to your assertion.

    > > I'd gain little by using your code to prove
    > > something I feel I already know...

    >
    > On the contrary, you have a lot to gain.
    > Having a scientific test bench allows you to (potentially) prove that
    > your algorithm truly works on all the test cases people throw at you.
    > You will then have great credibility and people will have no choice
    > but to take you very seriously.


    Nope. In my experience people simply ignore such data to hold on to
    their own view, or look around to see if someone else will do
    something, which I know from my prime counting function.

    It's better to get people to do things themselves or they tend to walk
    away from painful results, like information that forces them to
    discount knowledge they previously worked hard to attain.

    > You're either delusional (and truly believe that you alone knows how
    > to solve NP problem in P time), or you subconsciously are trying to
    > avoid
    > facing your own stupidity and thus you push away all the people trying
    > to help you.


    I'm not pushing anyone away. I'm simply not taking non-optimal paths,
    which I know from past experience do not work.

    You on the other hand have been rather insulting as well as delusional
    in your global statement of agreement from all readers worldwide of
    this newsgroup as if you were an uber-mind with access to all.

    Are you claiming to be God?


    James Harris
     
    JSH, Aug 17, 2008
    #15
  16. JSH wrote:
    > On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    >> JSH wrote:
    >>> On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day project
    >>>> needed.
    >>> Ok, I checked the link and it seems simple enough.

    >> ...
    >>> 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.

    >> ...
    >>> 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.

    >> I don't have any travelers at all in my implementation, just a search
    >> through the set of permutations of the nodes starting with a given node.
    >> That makes it hard to add a "second traveler".

    >
    > You just take an outputted path and output the distance between nodes
    > going from the outside in, for example if the path is
    >
    > ABCDEF
    >
    > then you'd output distances between A & F, B & E, and C & D.
    >
    > If you had
    >
    > ABCDEFG
    >
    > you'd output distances between A & G, B & F, and C & E, as with the
    > algorithm, either traveler can move to E, so the algorithm exits after
    > C & E.


    OK, that is doable:

    Best Score 32.0000
    Best Cycle: A W H G Z F E Y D C X B A
    Elapsed time: 3.66239 seconds
    Distance A to B = 2.00000
    Distance W to X = 2.00000
    Distance H to C = 8.00000
    Distance G to D = 8.00000
    Distance Z to Y = 2.00000
    Distance F to E = 2.00000

    It seems to be rather sensitive to which node I start at. Here are the
    results starting at G, without changing the coordinates of any point:

    Best Score 32.0000
    Best Cycle: G H W A B X C D Y E F Z G
    Elapsed time: 3.87479 seconds
    Distance G to Z = 3.00000
    Distance H to F = 5.83095
    Distance W to E = 5.38516
    Distance A to Y = 5.38516
    Distance B to D = 5.83095
    Distance X to C = 3.00000

    What is this supposed to tell me? Looking only at one optimal path makes
    it hard to pick out features that are related to being optimal.

    Patricia
     
    Patricia Shanahan, Aug 18, 2008
    #16
  17. JSH

    JSH Guest

    On Aug 17, 4:00 pm, Patricia Shanahan <> wrote:
    > JSH wrote:
    > > On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    > >> JSH wrote:
    > >>> On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day project
    > >>>> needed.
    > >>> Ok, I checked the link and it seems simple enough.
    > >> ...
    > >>> 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.
    > >> ...
    > >>> 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.
    > >> I don't have any travelers at all in my implementation, just a search
    > >> through the set of permutations of the nodes starting with a given node.
    > >> That makes it hard to add a "second traveler".

    >
    > > You just take an outputted path and output the distance between nodes
    > > going from the outside in, for example if the path is

    >
    > > ABCDEF

    >
    > > then you'd output distances between A & F, B & E, and C & D.

    >
    > > If you had

    >
    > > ABCDEFG

    >
    > > you'd output distances between A & G, B & F, and C & E, as with the
    > > algorithm, either traveler can move to E, so the algorithm exits after
    > > C & E.

    >
    > OK, that is doable:
    >
    > Best Score 32.0000
    > Best Cycle: A W H G Z F E Y D C X B A
    > Elapsed time: 3.66239 seconds
    > Distance A to B = 2.00000
    > Distance W to X = 2.00000
    > Distance H to C = 8.00000
    > Distance G to D = 8.00000
    > Distance Z to Y = 2.00000
    > Distance F to E = 2.00000
    >
    > It seems to be rather sensitive to which node I start at. Here are the
    > results starting at G, without changing the coordinates of any point:


    Hmmm...my hypothesis was that with the Euclidean TSP it wouldn't
    matter which node was the start...

    > Best Score 32.0000
    > Best Cycle: G H W A B X C D Y E F Z G
    > Elapsed time: 3.87479 seconds
    > Distance G to Z = 3.00000
    > Distance H to F = 5.83095
    > Distance W to E = 5.38516
    > Distance A to Y = 5.38516
    > Distance B to D = 5.83095
    > Distance X to C = 3.00000
    >
    > What is this supposed to tell me? Looking only at one optimal path makes
    > it hard to pick out features that are related to being optimal.
    >
    > Patricia


    Oh, you just compare with any other non-optimal paths. The distances
    along an optimal path should be less at each decision point from the
    outside in, so like with

    ABCDEFG

    versus

    BCDEFGA

    you'd compare A & G from the first to B & A from the second and so
    forth, and if the first is the optimal path, then at each such
    comparison you'd find the distance is shorter.

    That's it. It's that simple. If I'm wrong that is not true.


    James Harris
     
    JSH, Aug 18, 2008
    #17
  18. JSH

    Kenny Riodan Guest

    JSH wrote:
    > > What Patricia is trying to say, in her very modest and polite way,
    > > is that it's obvious to all of us that your algorithm doesn't work.

    >
    > All of us? So you speak for every member of the entire group
    > worldwide?


    I certainly did not (and do not) speak for every member of this
    newsgroup.
    It's this kind of logical fallacy that you're exhibiting time and time
    again
    in your flawed reasoning.

    I meant me and several people who have pointed out
    that it has been proven that local optimal prefixes are not
    guaranteed to be part of the global optimal solution.

    > > On the contrary, you have a lot to gain...

    >
    > Nope. In my experience people simply ignore such data...


    That is not the case here. Each time, you revise your algorithm,
    and several people almost immediately produce a counterexample
    showing that your algorithm is not optimal.

    Several people here produce data.
    You're the ony who "simply ignore such data".
    You're the one standing against progress.
     
    Kenny Riodan, Aug 18, 2008
    #18
  19. JSH

    JSH Guest

    On Aug 17, 4:06 pm, JSH <> wrote:
    > On Aug 17, 4:00 pm, Patricia Shanahan <> wrote:
    >
    >
    >
    > > JSH wrote:
    > > > On Aug 17, 3:24 pm, Patricia Shanahan <> wrote:
    > > >> JSH wrote:
    > > >>> On Aug 17, 12:32 pm, Patricia Shanahan <> 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 multi-programmer, multi-day project
    > > >>>> needed.
    > > >>> Ok, I checked the link and it seems simple enough.
    > > >> ...
    > > >>> 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.
    > > >> ...
    > > >>> 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.
    > > >> I don't have any travelers at all in my implementation, just a search
    > > >> through the set of permutations of the nodes starting with a given node.
    > > >> That makes it hard to add a "second traveler".

    >
    > > > You just take an outputted path and output the distance between nodes
    > > > going from the outside in, for example if the path is

    >
    > > > ABCDEF

    >
    > > > then you'd output distances between A & F, B & E, and C & D.

    >
    > > > If you had

    >
    > > > ABCDEFG

    >
    > > > you'd output distances between A & G, B & F, and C & E, as with the
    > > > algorithm, either traveler can move to E, so the algorithm exits after
    > > > C & E.

    >
    > > OK, that is doable:

    >
    > > Best Score 32.0000
    > > Best Cycle: A W H G Z F E Y D C X B A
    > > Elapsed time: 3.66239 seconds
    > > Distance A to B = 2.00000
    > > Distance W to X = 2.00000
    > > Distance H to C = 8.00000
    > > Distance G to D = 8.00000
    > > Distance Z to Y = 2.00000
    > > Distance F to E = 2.00000

    >
    > > It seems to be rather sensitive to which node I start at. Here are the
    > > results starting at G, without changing the coordinates of any point:

    >
    > Hmmm...my hypothesis was that with the Euclidean TSP it wouldn't
    > matter which node was the start...
    >
    > > Best Score 32.0000
    > > Best Cycle: G H W A B X C D Y E F Z G
    > > Elapsed time: 3.87479 seconds
    > > Distance G to Z = 3.00000
    > > Distance H to F = 5.83095
    > > Distance W to E = 5.38516
    > > Distance A to Y = 5.38516
    > > Distance B to D = 5.83095
    > > Distance X to C = 3.00000

    >
    > > What is this supposed to tell me? Looking only at one optimal path makes
    > > it hard to pick out features that are related to being optimal.

    >
    > > Patricia

    >
    > Oh, you just compare with any other non-optimal paths.  The distances
    > along an optimal path should be less at each decision point from the
    > outside in, so like with
    >
    > ABCDEFG
    >
    > versus
    >
    > BCDEFGA


    Sorry. That's wrong.

    You have to have the same starting node, so a better example would be:

    ABCDEFG

    versus

    ACBDEGF

    > you'd compare A & G from the first to B & A from the second and so
    > forth, and if the first is the optimal path, then at each such
    > comparison you'd find the distance is shorter.


    And that's wrong as well. You'd add all the distances together and
    get the average, and compare averages between different paths.

    Sorry but I made a quick reply before, without thinking it all through
    carefully and realized later I was wrong.

    > That's it.  It's that simple.  If I'm wrong that is not true.


    Um, sorry about changing criteria midstream but this research is all
    new.

    I'm figuring things out as I go along.

    Main change is to compare apples to apples versus apples to oranges as
    with the original criteria you could have the same optimal path with
    different starting points along it and get a contradiction.


    James Harris
     
    JSH, Aug 18, 2008
    #19
  20. Patricia Shanahan 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 at
    > http://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43303d1fbc


    One feature I think many would find helpful is the ability to input the
    graph via a GUI editor.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
     
    Joshua Cranmer, Aug 18, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    12
    Views:
    651
  2. JSH
    Replies:
    18
    Views:
    887
    Patricia Shanahan
    Jul 27, 2008
  3. JSH
    Replies:
    0
    Views:
    390
  4. JSH
    Replies:
    38
    Views:
    1,030
    Lits O'Hate
    Aug 29, 2008
  5. Priyank Shah
    Replies:
    2
    Views:
    101
    Justin Collins
    Sep 14, 2010
Loading...

Share This Page