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

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

Expand Messages
  • chenyu468
    I understand your meaning now. Thank you very much. Best regards/chenyu ... difficult ... algorithm ... path) ... would ... which
    Message 1 of 5 , Dec 9, 2003
    View Source
    • 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.