home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 288_01 / nn.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  3.9 KB  |  96 lines
  1. /*
  2.         HEADER:         CUG000.01;
  3.         TITLE:          NearNeighbor, CheapArc;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    Nearest Neighbor Tour Building Algorithm;
  6.         VERSION:        2.0;
  7.         FILENAME:       NN.C;
  8.         SEE-ALSO:       TSP.C, POPT.C, 2OPT.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 <stdio.h>
  15. #include <boolean.h>
  16. #include <nodelist.h>
  17. #include <tsp.h>
  18.  
  19. long NearNeighbor (NumberOfVirteces, SavePath)
  20.    unsigned NumberOfVirteces;
  21.    NODE *SavePath;
  22. {
  23.    unsigned ArcCost(), CheapArc();
  24.    long CircuitCost;
  25.    unsigned NewVirtex, ToIndex, CurrentVirtex, FromIndex;
  26.    BOOLEAN Available[MAXROWS][MAXCOLS];
  27.    NODE *Path;
  28.  
  29.    CircuitCost = 0;
  30.    for ( FromIndex = 1; FromIndex <= NumberOfVirteces; FromIndex++) {
  31.       for ( ToIndex = 1; ToIndex <= NumberOfVirteces; ToIndex++)
  32.          Available [FromIndex][ToIndex] = TRUE;
  33.       Available [FromIndex][FromIndex] = FALSE;
  34.    }
  35.    /* STEP 1: Find virtex from which cheapest arc eminates */
  36.       CurrentVirtex = 1;
  37.       NewVirtex = CheapArc (CurrentVirtex, NumberOfVirteces, Available);
  38.       for ( FromIndex = 2; FromIndex <= NumberOfVirteces; FromIndex++) {
  39.          ToIndex = CheapArc (FromIndex, NumberOfVirteces, Available);
  40.          if (ArcCost (FromIndex, ToIndex) <
  41.            ArcCost (CurrentVirtex, NewVirtex)) {
  42.             CurrentVirtex = FromIndex;
  43.             NewVirtex = ToIndex;
  44.          }
  45.       }
  46.    /* STEP 2: Establish current virtex as base of path */
  47.       Path = SavePath;
  48.       Path->position = CurrentVirtex;
  49.    /* STEP 7 Init */
  50.    do {
  51.       /* STEP 3: Set all paths unavailable to the current virtex */
  52.          for ( FromIndex = 1; FromIndex <= NumberOfVirteces; FromIndex++)
  53.             Available [FromIndex][CurrentVirtex] = FALSE;
  54.       /* STEP 4: Add cheapest arc from current virtex to cost of path */
  55.          CircuitCost += ArcCost (CurrentVirtex, NewVirtex);
  56.       /* STEP 5: Add new virtex to path */
  57.       if ((Path->next = calloc (1, sizeof(NODE))) == NULL) {
  58.          printf("\n*******************************************");
  59.          printf("\n Execution Terminated - Insuficient Memory!");
  60.          printf("\n*******************************************\n\n");
  61.          exit(-1);
  62.       } else {
  63.          Path->next->prior = Path;
  64.          Path = Path->next;
  65.          Path->position = NewVirtex;
  66.       }
  67.       /* STEP 6: Establish the new virtex as the current virtex */
  68.          CurrentVirtex = NewVirtex;
  69.       /* STEP 7: Find the next virtex at the opposite end of the cheapest
  70.                  arc from current virtex; if found, continue with step 3 */
  71.          NewVirtex = CheapArc (CurrentVirtex, NumberOfVirteces, Available);
  72.    } while (Available [CurrentVirtex][NewVirtex]);
  73.    /* STEP 8: Find the cost of the arc between the new current virtex and
  74.               the initial virtex in the path and add to cost of path */
  75.       SavePath->prior = Path;
  76.       Path->next = SavePath;
  77.       CircuitCost += ArcCost (CurrentVirtex, SavePath->position);
  78.       return (CircuitCost);
  79. } /* NearNeighbor */
  80.  
  81. unsigned CheapArc (FromIndex, NumberOfVirteces, Available)
  82.    unsigned FromIndex, NumberOfVirteces;
  83.    BOOLEAN Available[MAXROWS][MAXCOLS];
  84. {
  85.    unsigned ArcCost();
  86.    unsigned ToIndex, NewIndex;
  87.  
  88.    for ( ToIndex = 1; ((ToIndex < NumberOfVirteces) &&
  89.       (!Available [FromIndex][ToIndex])); ToIndex++);
  90.    for ( NewIndex = ToIndex + 1; NewIndex <= NumberOfVirteces; NewIndex++)
  91.       if (Available [FromIndex][NewIndex])
  92.          if (ArcCost (FromIndex, NewIndex) < ArcCost (FromIndex, ToIndex))
  93.             ToIndex = NewIndex;
  94.    return (ToIndex);
  95. } /* CheapArc */
  96.