Implementation and Analysis of the Traveling-Salesman Problem

To solve the traveling-salesman problem, we begin with a graph that is represented simply as a list of vertices. In this representation, an edge connecting every pair of vertices is implied. Each vertex in the list is a TspVertex structure (see Example 16.5). This structure consists of four members: data is the data associated with the vertex, x and y are coordinates for the point the vertex represents, and color is the color of the vertex.

The tsp operation begins by coloring every vertex white, except the start vertex, which is colored black and added to the tour immediately. The coordinates of the start vertex are also recorded so that we can compute distances between it and every other vertex during the first iteration of the main loop. In the main loop, we add all of the remaining vertices to the tour. During each iteration, we look for the white vertex closest to the last vertex. Each time we add a vertex, we record its coordinates for the next iteration and color the vertex black. After the loop terminates, we add the start vertex again to complete the tour.

The runtime complexity of tsp is O (V 2), where V is the number of vertices to visit in the tour. This is because for each of the V - 1 iterations of the main loop, we search the vertices in the graph to determine which is white and needs a distance computed to it. Notice that O (V 2) is quite an improvement over the runtime complexity for computing an optimal tour, which was O (V !).

Example 16.5. Implementation for Solving the Traveling-Salesman Problem
/*****************************************************************************
*                                                                            *
*  --------------------------------- tsp.c --------------------------------  *
*                                                                            *
*****************************************************************************/

#include <float.h>
#include <math.h>
#include <stdlib.h>

#include "graph.h"
#include "graphalg.h"
#include "list.h"

/*****************************************************************************
*                                                                            *
*  ---------------------------------- tsp ---------------------------------  *
*                                                                            *
*****************************************************************************/

int tsp(List *vertices, const TspVertex *start, List *tour, int (*match)
   (const void *key1, const void *key2)) {

TspVertex          *tsp_vertex,
                   *tsp_start,
                   *selection;

ListElmt           *element;

double             minimum,
                   distance,
                   x,
                   y;

int                found,
                   i;

/*****************************************************************************
*                                                                            *
*  Initialize the list for the tour.                                         *
*                                                                            *
*****************************************************************************/

list_init(tour, NULL);

/*****************************************************************************
*                                                                            *
*  Initialize all of the vertices in the graph.                              *
*                                                                            *
*****************************************************************************/

found = 0;

for (element = list_head(vertices); element != NULL; element =
   list_next(element)) {

   tsp_vertex = list_data(element);

   if (match(tsp_vertex, start)) {

      /***********************************************************************
      *                                                                      *
      *  Start the tour at the start vertex.                                 *
      *                                                                      *
      ***********************************************************************/

      if (list_ins_next(tour, list_tail(tour), tsp_vertex) != 0) {

         list_destroy(tour);
         return -1;

      }

      /***********************************************************************
      *                                                                      *
      *  Save the start vertex and its coordinates.                          *
      *                                                                      *
      ***********************************************************************/

      tsp_start = tsp_vertex;
      x = tsp_vertex->x;
      y = tsp_vertex->y;

      /***********************************************************************
      *                                                                      *
      *  Color the start vertex black.                                       *
      *                                                                      *
      ***********************************************************************/

      tsp_vertex->color = black;
      found = 1;

      }

   else {

      /***********************************************************************
      *                                                                      *
      *  Color all other vertices white.                                     *
      *                                                                      *
      ***********************************************************************/

      tsp_vertex->color = white;

   }

}

/*****************************************************************************
*                                                                            *
*  Return if the start vertex was not found.                                 *
*                                                                            *
*****************************************************************************/

if (!found) {

   list_destroy(tour);
   return -1;

}

/*****************************************************************************
*                                                                            *
*  Use the nearest-neighbor heuristic to compute the tour.                   *
*                                                                            *
*****************************************************************************/

i = 0;

while (i < list_size(vertices) - 1) {

   /**************************************************************************
   *                                                                         *
   *  Select the white vertex closest to the previous vertex in the tour.    *
   *                                                                         *
   **************************************************************************/

   minimum = DBL_MAX;

   for (element = list_head(vertices); element != NULL; element =
      list_next(element)) {

      tsp_vertex = list_data(element);

      if (tsp_vertex->color == white) {

         distance = sqrt(pow(tsp_vertex->x-x,2.0) + pow(tsp_vertex->y-y,2.0));

         if (distance < minimum) {

            minimum = distance;
            selection = tsp_vertex;

         }

      }

   }

   /**************************************************************************
   *                                                                         *
   *  Save the coordinates of the selected vertex.                           *
   *                                                                         *
   **************************************************************************/

   x = selection->x;
   y = selection->y;

   /**************************************************************************
   *                                                                         *
   *  Color the selected vertex black.                                       *
   *                                                                         *
   **************************************************************************/

   selection->color = black;

   /**************************************************************************
   *                                                                         *
   *  Insert the selected vertex into the tour.                              *
   *                                                                         *
   **************************************************************************/

   if (list_ins_next(tour, list_tail(tour), selection) != 0) {

      list_destroy(tour);
      return -1;

   }

   /**************************************************************************
   *                                                                         *
   *  Prepare to select the next vertex.                                     *
   *                                                                         *
   **************************************************************************/

   i++;

}

/*****************************************************************************
*                                                                            *
*  Insert the start vertex again to complete the tour.                       *
*                                                                            *
*****************************************************************************/

if (list_ins_next(tour, list_tail(tour), tsp_start) != 0) {

   list_destroy(tour);
   return -1;

}

return 0;

}
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset