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

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

Expand Messages
  • chenyu468
    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
    Message 1 of 5 , Dec 3, 2003
    • 0 Attachment
      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
      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 ... that s,
      Message 2 of 5 , Dec 4, 2003
      • 0 Attachment
        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
      • chenyu468
        hello, I am asking why is there a requirement for a complete graph? kind regards/chenyu ... every
        Message 3 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 4 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 5 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.