## 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.

Pages: 1 2

### 9 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

```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;

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);
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;
scramble(cities, newPivot, numCities - 1);
circ_perm(pivot, numCities);
}
}

void circ_perm(City cities[], int numCities)
{
int i;
City tmp;
copy_City(tmp, cities);
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 = source;
dest = source;
}

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 - city1) +
(float)square(city2 - city1));
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], cities[i]);
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()