Traveling Salesman: Brute Force

March 12, 2010

The traveling salesman problem is classic: Find the minimum-length tour that visits each city on a map exactly once, returning to the origin. It is an important problem in practice; consider, for instance, that the cities are soldering points on a large circuit board, each of which must be visited by a soldering robot. It is also an important problem in mathematics, and is known to be in NP, meaning that optimal solutions for non-trivial problems are impossible. Nonetheless, there exist heuristic algorithms that do a good job at minimizing the tour length.

We will examine the traveling salesman problem in an occasional series of exercise, beginning with today’s exercise that looks at the brute-force solution of examining all possible tours. The algorithm is simple: First, select a tour at random, then determine all possible permutations of the tour. Second, determine the length of each tour. Third, report the tour with minimum length as the solution.

Your task is to write a program that solves the traveling salesman problem using the brute-force algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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