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

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

Expand Messages
  • chenyu468
    hello, I am asking why is there a requirement for a complete graph? kind regards/chenyu ... every
    Message 1 of 5 , Dec 5, 2003
    • 0 Attachment
      hello,
      I am asking "why is there a requirement for a complete graph?"


      kind regards/chenyu



      --- In aima-talk@yahoogroups.com, "Brandon Corfman" <bcorfman@a...>
      wrote:
      > Are you asking "why is there a requirement for a complete graph?"
      > or "why is the check-tsp-map function called where it is?"
      >
      > Brandon
      >
      > --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...>
      wrote:
      > > Hello,
      > > I am studying "/search/domains/tsp.lisp" source code, which is
      > > about "Travelling salesperson Problem".
      > >
      > > In the source code, there is a requirement to the city map,
      > that's,
      > > the map should be complete graph. Every city is connected to
      every
      > > other city, in the function ( check-tsp-map?).
      > >
      > > I don't know why the requirement should be added here? What's the
      > > reason behind it. Could you help me?
      > >
      > >
      > > Thank you for your attention.
      > > kind regards/chenyu
    • 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 2 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 3 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.