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.

Posted by programmingpraxis

Filed in Exercises

9 Comments »

9 Responses to “Traveling Salesman: Brute Force”

Programming Praxis – Traveling Salesman: Brute Force « Bonsai Code said
March 12, 2010 at 9:57 AM
[…] 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 […]

Remco Niemeijer said

March 12, 2010 at 9:57 AM

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

Jebb said

March 15, 2010 at 7:40 AM

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");
}

Travelling salesman « Wrong Side of Memphis said
March 16, 2010 at 4:56 PM
[…] 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 […]
Mike said
March 18, 2010 at 6:22 PM
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)
```
harsha said
January 9, 2011 at 4:05 AM
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
Anusha said
April 28, 2013 at 10:39 AM
In the c program there is an error inthe distance function:
in sqrtf()
please help
mumus said
May 7, 2015 at 11:30 AM
Why use brute force when you can do it easily ? Just visit this link and try the actual program.

http://stackoverflow.com/questions/28702426/no-matching-function-for-call-to-mapflatfunctionname/29174891#29174891
Kompleksitas Algoritma - ryandhikafm's blog said
October 9, 2015 at 8:59 AM
[…] https://programmingpraxis.com/2010/03/12/traveling-salesman-brute-force/ […]

Programming Praxis