hw4 2-opt remark

From: Michelangelo Grigni (mic@mathcs.emory.edu)
Date: Tue Apr 03 2012 - 12:50:48 EDT

• Next message: Michelangelo Grigni: "hw4 partial credit"
• Previous message: Michelangelo Grigni: "hw4 turnin"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Note that for 2-opt, you should keep trying until
there is no edge in G that triggers a 2-opt improvement
of the tour. In particular, don't just try each edge once
(for run1000, that leaves too many crossings in TSP2.png).

Something like this:

   again = true
   while (again)
   {
      again = false
      for each edge e of G
         if (2-opt at e succeeds in improving the tour)
            again = true
   }

• Next message: Michelangelo Grigni: "hw4 partial credit"
• Previous message: Michelangelo Grigni: "hw4 turnin"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

This archive was generated by hypermail 2.1.4 : Wed Apr 04 2012 - 17:34:17 EDT