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.
Programming Praxis 
[…] 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).
#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"); }[…] 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:
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)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
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
[…] https://programmingpraxis.com/2010/03/12/traveling-salesman-brute-force/ […]