Loading ...
Sorry, an error occurred while loading the content.

Re: lisp source code "/search/domains/tsp.lisp" complete graph requirement?

Expand Messages
  • Brandon Corfman
    A TSP does not require a complete graph, but it becomes more difficult to solve it otherwise**. For instance, a fast but effective algorithm like 2-Opt (that
    Message 1 of 5 , Dec 8, 2003
    • 0 Attachment
      A TSP does not require a complete graph, but it becomes more difficult
      to solve it otherwise**. For instance, a fast but effective algorithm
      like 2-Opt (that hill-climbs by inverting subsequences along the path)
      would be rendered ineffective if the graph was not complete. You would
      have to start checking constraints on the path at each exchange, which
      requires different techniques (perhaps a constraint satisfaction
      problem).

      Best regards,
      Brandon

      ** Source: Michalwicz, Zbigniew and Fogel, David B.; How to Solve It:
      Modern Heuristics, Springer-Verlag, 1999.


      --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:
      > hello,
      > I am asking "why is there a requirement for a complete graph?"
    • chenyu468
      I understand your meaning now. Thank you very much. Best regards/chenyu ... difficult ... algorithm ... path) ... would ... which
      Message 2 of 5 , Dec 9, 2003
      • 0 Attachment
        I understand your meaning now. Thank you very much.

        Best regards/chenyu

        --- In aima-talk@yahoogroups.com, "Brandon Corfman" <bcorfman@a...>
        wrote:
        > A TSP does not require a complete graph, but it becomes more
        difficult
        > to solve it otherwise**. For instance, a fast but effective
        algorithm
        > like 2-Opt (that hill-climbs by inverting subsequences along the
        path)
        > would be rendered ineffective if the graph was not complete. You
        would
        > have to start checking constraints on the path at each exchange,
        which
        > requires different techniques (perhaps a constraint satisfaction
        > problem).
        >
        > Best regards,
        > Brandon
        >
        > ** Source: Michalwicz, Zbigniew and Fogel, David B.; How to Solve
        It:
        > Modern Heuristics, Springer-Verlag, 1999.
        >
        >
        > --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...>
        wrote:
        > > hello,
        > > I am asking "why is there a requirement for a complete graph?"
      Your message has been successfully submitted and would be delivered to recipients shortly.