home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 288_01 / 2opt.c < prev    next >
Text File  |  1989-05-25  |  2KB  |  63 lines
  1. /*
  2.         HEADER:         CUG000.03;
  3.         TITLE:          TwoOpt;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    2-Opt Tour Improvement Algorithm;
  6.         VERSION:        2.0;
  7.         FILENAME:       2OPT.C;
  8.         SEE-ALSO:       TSP.C, NN.C, POPT.C, HYBRID.C, 3OPT.C, FN.C,
  9.                         BOOLEAN.H, NODELIST.H, TSP.H,
  10.                         BLDMTX.C, PRTMTX.C, TIME.C;
  11.         AUTHORS:        Kevin E. Knauss;
  12. */
  13.  
  14. #include <nodelist.h>
  15.  
  16. long TwoOpt (NumberOfVirteces, Path)
  17.    unsigned NumberOfVirteces;
  18.    NODE *Path;
  19. {
  20.    unsigned ArcCost();
  21.    long CircuitCost;
  22.    unsigned count, index, pindex, sindex, k;
  23.    unsigned D1, D2, D3, D4;
  24.    NODE *First, *Last, *Kth, *Save, *Reverse;
  25.  
  26.    count = 1;
  27.    First = Path;
  28.    do {
  29.       Last = First->prior;
  30.       Kth = First->next;
  31.       do {
  32.          D2 = ArcCost (First->position, Kth->next->position)  /* 2-Opt */
  33.             + ArcCost (Kth->position, Last->position);
  34.          D4 = ArcCost (First->position, Last->position)
  35.             + ArcCost (Kth->position, Kth->next->position);
  36.          if (D2 < D4) {
  37.             for ( Reverse = First; Reverse != Kth; Reverse = Save) {
  38.                Save = Reverse->next;
  39.                Reverse->next = Reverse->prior;
  40.                Reverse->prior = Save;
  41.             }
  42.             First->next = Kth->next;
  43.             Kth->next->prior = First;
  44.             Kth->next = Kth->prior;
  45.             Kth->prior = Last;
  46.             Last->next = Kth;
  47.             count = 0;
  48.             First = Last->next;
  49.             Kth = First->next;
  50.          } else
  51.             Kth = Kth->next;
  52.       } while ((Kth != Last->prior->prior) && (count != 0));
  53.       if (count != 0)
  54.          First = First->next;
  55.       count++;
  56.    } while (count < NumberOfVirteces);
  57.    Last = First->prior;
  58.    CircuitCost = ArcCost (Last->position, First->position);
  59.    for ( Kth = First; Kth != Last; Kth = Kth->next)
  60.       CircuitCost += ArcCost (Kth->position, Kth->next->position);
  61.    return (CircuitCost);
  62. } /* TwoOpt */
  63.