home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 288_01 / hybrid.c < prev    next >
Text File  |  1989-05-25  |  3KB  |  79 lines
  1. /*
  2.         HEADER:         CUG000.04;
  3.         TITLE:          Hybrid;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    Point Proximity/2-Opt Hybrid Tour Improvement Algorithm;
  6.         VERSION:        2.0;
  7.         FILENAME:       HYBRID.C;
  8.         SEE-ALSO:       TSP.C, NN.C, POPT.C, 2OPT.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 Hybrid (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.          D1 = ArcCost (Kth->position, Kth->next->next->position) /* Point-Opt */
  33.             + ArcCost (First->position, Kth->next->position)
  34.             + ArcCost (Kth->next->position, Last->position);
  35.          D3 = ArcCost (First->position, Last->position)
  36.             + ArcCost (Kth->position, Kth->next->position)
  37.             + ArcCost (Kth->next->position, Kth->next->next->position);
  38.          D2 = ArcCost (First->position, Kth->next->position)  /* 2-Opt */
  39.             + ArcCost (Kth->position, Last->position);
  40.          D4 = ArcCost (First->position, Last->position)
  41.             + ArcCost (Kth->position, Kth->next->position);
  42.          if ((D1 < D3) || (D2 < D4)) {
  43.             if (D1 < D3) {
  44.                Save = Kth->next;
  45.                Kth->next = Kth->next->next;
  46.                Kth->next->prior = Kth;
  47.                Last->next = Save;
  48.                First->prior = Save;
  49.                Save->next = First;
  50.                Save->prior = Last;
  51.             } else {
  52.                for ( Reverse = First; Reverse != Kth; Reverse = Save) {
  53.                   Save = Reverse->next;
  54.                   Reverse->next = Reverse->prior;
  55.                   Reverse->prior = Save;
  56.                }
  57.                First->next = Kth->next;
  58.                Kth->next->prior = First;
  59.                Kth->next = Kth->prior;
  60.                Kth->prior = Last;
  61.                Last->next = Kth;
  62.             }
  63.             count = 0;
  64.             First = Last->next;
  65.             Kth = First->next;
  66.          } else
  67.             Kth = Kth->next;
  68.       } while ((Kth != Last->prior->prior) && (count != 0));
  69.       if (count != 0)
  70.          First = First->next;
  71.       count++;
  72.    } while (count < NumberOfVirteces);
  73.    Last = First->prior;
  74.    CircuitCost = ArcCost (Last->position, First->position);
  75.    for ( Kth = First; Kth != Last; Kth = Kth->next)
  76.       CircuitCost += ArcCost (Kth->position, Kth->next->position);
  77.    return (CircuitCost);
  78. } /* Hybrid */
  79.