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

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

Expand Messages
  • 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 1 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 2 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 3 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 4 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.