Traveling Salesman: Brute Force

March 12, 2010

Before we can write a solution, we need a function that generates a problem. Make-tsp returns a vector of x,y points (both x and y are non-negative integers), stored in cons pairs, of length n:

(define (make-tsp n)
  (let loop ((n n) (xs '()))
    (if (zero? n) (list->vector xs)
      (let ((x (cons (randint (* n 10)) (randint (* n 10)))))
        (if (member x xs) (loop n xs)
          (loop (- n 1) (cons x xs)))))))

The distance between two points is computed using the normal Euclidean distance function based on the hypotenuse of a triangle:

(define (dist points a b)
  (define (point k) (vector-ref points k))
  (define (square x) (* x x))
  (sqrt (+ (square (- (car (point a)) (car (point b))))
           (square (- (cdr (point a)) (cdr (point b)))))))

To find the cost of a tour we add the distances between successive points on the tour, including the cost of returning to the starting point:

(define (cost points tour)
  (if (or (null? tour) (null? (cdr tour))) 0
    (let ((start (car tour)))
      (let loop ((tour tour) (sum 0))
        (if (null? (cdr tour))
            (+ sum (dist points (car tour) start))
            (loop (cdr tour) (+ sum (dist points (car tour) (cadr tour)))))))))

Then the minimal tour can be calculated by choosing an initial tour and computing the cost of all its permutations:

(define (tsp ps)
  (let* ((len (vector-length ps))
         (k (fact len))
         (t (reverse (range len))))
    (let loop ((k k) (t t) (min-t '()) (min-c #f))
      (if (zero? k) min-t
        (let ((c (cost ps t)))
          (if (or (not min-c) (< c min-c))
              (loop (- k 1) (next-perm < t) t c)
              (loop (- k 1) (next-perm < t) min-t min-c)))))))

Here’s an example:

> (define p (make-tsp 8))
> p
#((5 . 2) (19 . 13) (4 . 8) (6 . 32) (23 . 7) (57 . 54) (55 . 8) (70 . 59))
> (tsp p)
(3 2 0 1 4 6 7 5)

This is, of course, dreadfully slow: there is a noticeable pause after pressing the ENTER key before returning an 8-point tour, and computing the tour for ten points takes over a minute. We’ll see better algorithms in future exercises.

We used sum, range, rand and randint from the Standard Prelude, and fact and next-perm from the previous exercise. You can run the program at http://programmingpraxis.codepad.org/EyLs49LA.

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 628 other followers

%d bloggers like this: