• Choose a category
• All
• Classic-Fiction

Interface for the Traveling-Salesman Problem

Name

tsp

Synopsis

int tsp(List *vertices, const TspVertex *start, List *tour, int (*match)

(const void *key1, const void *key2))

Return Value

0if computing the approximate traveling-salesman tour is successful, or -1 otherwise.

Description

Computes an approximate traveling-salesman tour of the points specified as vertices in vertices. The tour begins at the vertex specified by start. The operation modifies vertices, so a copy should be made before calling the operation, if necessary. Each element in vertices must be of type TspVertex. Use the data member of each TspVertex structure to store data associated with the vertex, such as an identifier. Use the x and y members of the structure to specify the coordinates associated with the vertex. The function specified by match determines whether two vertices match. It should only compare the data members of TspVertex structures. The tour is returned in tour, which is a list of TspVertex structures. Each vertex appears in tour in the order it would be encountered during the tour. The elements in tour point to the actual vertices in vertices, so the caller must ensure that the storage in vertices remains valid as long as tour is being accessed. Use list_destroy to destroy tour once it is no longer needed.

Complexity

O (V 2), where V is the number of vertices to visit in the tour.

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

#include

#include

#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