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

[…] 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 […]

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

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

[…] 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 […]

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:

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

In the c program there is an error inthe distance function:

in sqrtf()

please help