Traveling Salesman: Brute Force

March 12, 2010

The traveling salesman problem is classic: Find the minimum-length tour that visits each city on a map exactly once, returning to the origin. It is an important problem in practice; consider, for instance, that the cities are soldering points on a large circuit board, each of which must be visited by a soldering robot. It is also an important problem in mathematics, and is known to be in NP, meaning that optimal solutions for non-trivial problems are impossible. Nonetheless, there exist heuristic algorithms that do a good job at minimizing the tour length.

We will examine the traveling salesman problem in an occasional series of exercise, beginning with today’s exercise that looks at the brute-force solution of examining all possible tours. The algorithm is simple: First, select a tour at random, then determine all possible permutations of the tour. Second, determine the length of each tour. Third, report the tour with minimum length as the solution.

Your task is to write a program that solves the traveling salesman problem using the brute-force algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

7 Responses to “Traveling Salesman: Brute Force”

  1. [...] Praxis – Traveling Salesman: Brute Force By Remco Niemeijer In today’s Programming Praxis exercise we have to implement a brute-force algorithm for solving the well-known [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/12/programming-praxis-traveling-salesman-brute-force/ for a version with comments):

    import Data.List
    import qualified Data.List.Key as K
    
    dist :: Floating a => (a, a) -> (a, a) -> a
    dist (x1, y1) (x2, y2) = sqrt ((x1 - x2) ** 2 + (y1 - y2) ** 2)
    
    tours :: [b] -> [[(Int, b)]]
    tours = map (\(x:xs) -> x:xs ++ [x]) . permutations . zip [0..]
    
    cost :: Floating a => [(b, (a, a))] -> a
    cost xs = sum $ zipWith dist xs (tail xs)
    
    shortestPath :: [(Double, Double)] -> [Int]
    shortestPath = init . map fst . K.minimum cost . tours
    
  3. Jebb said

    A C solution. Quite verbose obviously, and I did manage to fall into a couple of pitfalls along the way. It is fast, though (1 second for the 10-second problem).

    #include <stdio.h>
    #include <math.h>
    #define NUMCITY	10
    #define LANDSIZE 100
    #define square(A) ((A) * (A))
    
    typedef int City[2];
    
    void generate(City cities[]);
    void print_cities(City cities[]);
    float distance(City city1, City city2);
    void copy_tour(City citiesDest[], City citiesSource[]);
    void copy_City(City dest, City source);
    void swap_cities(City city1, City city2);
    void circ_perm(City cities[], int numCities);
    void scramble(City cities[], City *pivot, int numCities);
    void target_function(City cities[]);
    float tour_length(City cities[]);
    
    float shortestTourLength;
    City shortestTour[NUMCITY];
    
    int main()
    {
    	City cities[NUMCITY];
    	generate(cities);
    	shortestTourLength = tour_length(cities);
    	copy_tour(shortestTour, cities);
    	scramble(cities, cities, NUMCITY);
    	printf("found the shortest tour:\n");
    	print_cities(shortestTour);
    	printf("Length is: %f\n", shortestTourLength);
    	return 0;
    }
    
    float tour_length(City cities[])
    {
    	int i;
    	float length = 0.0;
    	for(i = 0; i < NUMCITY - 1; i++)
    		length += distance(cities[i], cities[i+1]);
    	length += distance(cities[NUMCITY - 1], cities[0]);
    	return length;
    }
    
    void target_function(City cities[])
    {
    	float length;
    	length = tour_length(cities);
    	if (length < shortestTourLength) {
    		shortestTourLength = length;
    		copy_tour(shortestTour, cities);
    	}
    }
    
    /*pivot is the base address in the cities[NUMCITY] array
     *for the recursive scrambling; the only reason we also
     *pass the unchanged cities address is because we need it
     *to call the target function (which does *something* to
     *the scrambled array) at each recursive call to scramble
     */
    void scramble(City cities[], City *pivot, int numCities)
    {
    	int i;
    	City *newPivot;
    	if (numCities <= 1) { //Scrambled! Call the target function
    		target_function(cities);
    		return;
    	}
    	for (i = 0; i < numCities; i++) {
    		newPivot = &pivot[1];
    		scramble(cities, newPivot, numCities - 1);
    		circ_perm(pivot, numCities);
    	}
    }
    
    void circ_perm(City cities[], int numCities)
    {
    	int i;
    	City tmp;
    	copy_City(tmp, cities[0]);
    	for (i = 0; i < numCities - 1; i++)
    		copy_City(cities[i], cities[i + 1]);
    	copy_City(cities[numCities - 1], tmp);
    }
    
    void copy_tour(City citiesDest[], City citiesSource[])
    {
    	int i;
    	for (i = 0; i < NUMCITY; i++)
    		copy_City(citiesDest[i], citiesSource[i]);
    }
    
    void copy_City(City dest, City source)
    {
    	dest[0] = source[0];
    	dest[1] = source[1];
    }
    
    void swap_cities(City city1, City city2)
    {
    	City tmp;
    	copy_City(tmp, city1);
    	copy_City(city1, city2);
    	copy_City(city2, tmp);
    }
    
    float distance(City city1, City city2)
    {
    	float result;
    	result = sqrtf((float)square(city2[0] - city1[0]) +
    				 (float)square(city2[1] - city1[1]));
    	return result;
    }
    
    void generate(City cities[])
    {
    	int i, j;
    	for (i = 0; i < NUMCITY; i++)
    		for (j = 0; j < 2; j++)
    			cities[i][j] = rand() % LANDSIZE;
    }
    
    void print_cities(City cities[])
    {
    	int i;
    	for (i = 0; i < NUMCITY; i++) {
    		printf("(%d,%d)", cities[i][0], cities[i][1]);
    		if (i < NUMCITY - 1)
    			printf(" , ");
    	}
    	printf("\n");
    }
    
  4. [...] with the length of the data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the [...]

  5. Mike said

    One observation is that most of the permutations of the cities are mere rotations of another permutation. For example, the tour [city2, ... cityN, city1] is a rotation of the tour [city1, city2, ... cityN]. Indeed, any tour starting with any of city2 .. cityN is a rotation of a tour starting with city1.

    A smarter brute force solution is to only consider permutations that start with city1. For 10 cities this optimisation eliminates 90% of the calculations.

    In python:

    def brute_force(cities):
        other_cities = cities.copy()
        start_city = tuple(other_cities.pop())
    
        return min((start_city+p for p in permutations(other_cities)), key=path_cost)
    
  6. harsha said

    On executing this programme on C-free5.0 version, it showed an error for “rand()” at line no.:121
    so i overcomed it by including “stdlib.h” header file for this “rand()” function

  7. Anusha said

    In the c program there is an error inthe distance function:
    in sqrtf()
    please help

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 632 other followers

%d bloggers like this: