The *traveling salesman problem*, referred to as the *TSP*, is one of the most
famous problems in all of computer science. It’s a problem that’s easy to
describe, yet fiendishly difficult to solve. In fact, it remains an open
question as to whether or not it is possible to *efficiently* solve all TSP
instances.

Here is the problem. Suppose you are a salesman travelling that has a list of cities that you want to visit. You want to go to each city exactly once. Naturally, you want to tour all the cities in the order that requires traveling the shortest distance.

For instance, suppose you’re visiting these four cities:

```
0 1
2 3
```

You always start, and end, at 0, your home city. We assume the following distances between cities:

dist(0, 1) = 10

dist(0, 2) = 10

dist(0, 3) = 14

dist(1, 2) = 14

dist(1, 3) = 10

dist(2, 3) = 10

In this case the distances are *symmetric*, i.e. dist(a, b) is always the same
as dist(b, a). So for example we know dist(3, 2) = 10 because we are told
dist(2, 3) = 10.

Here are some different tours of the cities:

0 to 1 to 3 to 2 (and back to 0); total distance = 10 + 10 + 10 + 10 = 40

Or:

0 to 2 to 3 to 1 (and back to 0); total distance = 10 + 10 + 10 + 10 = 40

Or:

0 to 3 to 1 to 2 (and back to 0); total distance = 14 + 10 + 14 10 = 48

Or:

0 to 2 to 1 to 3 (and back to 0); total distance = 10 + 14 + 10 + 14 = 48

Clearly, some tours are shorter than others. For this small 4-city example it is easy to see that the shortest way to visit all the cities is to go around the edges and avoid the long diagonals.

But not all instances of the TSP are so simple or so small. For instance, suppose you want to visit all 4600-plus Canadian cities. It is not at all obvious how you should go about finding the shortest possible tour of so many cities.

If you think about it, representing a TSP tour is not too hard: it is just a
*permutation* of the cities, with the added restriction that the first city
must always be 0 (your home city). For instance, we can write the above tours
compactly like this:

0, 2, 3, 2

0, 2, 3, 1

0, 3, 1, 2

0, 2, 1, 3

Once we realize a tour is a permutation, then a brute-force algorithm that is guaranteed to always solve the TSP becomes evident:

Brute-force algorithm: Examine all possible permutations of cities, and keep the one that is shortest.

It turns out that there are exactly different permutations of the numbers from 0 to . Since we only care about permutations that start with 0, to solve an -city TSP instance with brute force requires that we look at exactly different permutations.

Lets give some thought to the overall structure and organization of our program.

First, we will assume that the cities are named 0 to n - 1, and that a tour of these n cities is a permutation of the numbers from 0 to n - 1. We assume that 0 is the home city, and that all tours start with 0.

Second, we need some way to store the cities. Since our cities are on a
2-dimensional map, we can store them as (x, y) points using the `Point`
class from previous notes. We’ll store the cities as a
`vector<Point>`, where each city’s name is the same as its index number in
the `vector`, i.e. the city at index location 0 is named 0, the city at
index location 1 is named 1, and so on.

We’re also going to need a function to calculate the distance between two
cities, and another function to calculate the total length of a tour of
cities. So lets write a class called `Tsp_map` whose responsibility is to
take care of such details. A `Tsp_map` object will store a collection of
cities, provide functions for calculating distances, and maybe some other
helper functions as well.

Note

Recall from math class that distance between the points (x, y) and (a, b) is given by this formula:

Third, lets agree to represent a tour (i.e. a permutation of city names) as a
`vector<int>`. The numbers in it represent the names of the cities in a
particular `Tsp_map`, and the order of the numbers is the order in which the
cities will be visited.

Using the above notes as a guide, lets start to write the `Tsp_map` class:

```
#include "Point.h"
class Tsp_map {
private:
vector<Point> cities;
public:
// add a city at point p
void add(const Point& p) {
cities.push_back(p);
}
// add a city at (x, y)
void add(double x, double y) {
Point p(x, y);
add(p);
}
// # of cities
int size() const {
return cities.size();
}
// calculate the distance between cities i and j
double dist_between(int i, int j) const {
return dist(cities[i], cities[j]); // dist is from Point.h
}
// calculate the score of the given tour
double score(const vector<int>& tour) const {
double result = dist_between(tour[0], tour[size() - 1]);
for(int i = 1; i < size(); ++i) { // i starts at 1, not 0!
result += dist_between(tour[i - 1], tour[i]);
}
return result;
}
// return a starting tour of all the cities in the order 0, 1, 2, 3,
// ...
vector<int> get_default_tour() const {
vector<int> tour(size());
for(int i = 0; i < size(); ++i) {
tour[i] = i;
}
return tour;
}
}; // class Tsp_map
```

Note the following:

The variable

`cities`is of type`vector<Point>`, and it stores a list of cities as`Point`objects.We’ve declared

`cities`to be private as a matter of good design: by default, all variables in a class should be private unless there is a clear reason for making them public.No constructor has been written for this function because no special initialization is need. C++ automatically initializes

`cities`to be empty when a`Tsp_map`object is created.Two

`add`functions are provided for adding cities to the`Tsp_map`. Note that one calls the other.The

`dist_between`functions takes the names (i.e. index locations) of two cities and returns the distance between them using the`dist`function from`Point.h`. If either of the parameters`i`or`j`is not a legal name of a city, then an error will be thrown because`cities`is a`checked_vector`.The

`score`functions calculates the total length of a given tour. Note that the distance between the first city and last city is included.The

`get_default_tour`function is a handy way to get a list of all the cities for a particular`Tsp_map`. It just returns a`vector<int>`initialized to 0, 1, 2, 3, ..., n - 1.`size`,`dist_between`,`score`, and`get_default_tour`have all been declared`const`functions. In general, you should always declare functions in class to be`const`if possible. That way they will work with`const``Tsp_map`objects.The two

`add`functions are not declared`const`because they modify`cities`.

We can use a `Tsp_map` like this:

```
Tsp_map cities;
cities.add(0, 0);
cities.add(10, 0);
cities.add(0, 10);
cities.add(10, 10);
// get a starting tour
vector<int> tour(cities.get_default_tour());
// ...
```

Our tours are represented as plain `vector<int>` objects. A problem with
this is that writing `vector<int>` all the time is a bit tedious, and it
also doesn’t clearly indicate that it is being used to represent a tour. So we
what we can do is to use `typedef` to create a synonym for `vector<int>`
with a more descriptive name:

```
typedef vector<int> Tour; // Tour is a synonym for vector<int>
// ...
```

Now we can write `Tour` instead of `vector<int>`:

```
// get a starting tour
Tour tour(cities.get_default_tour());
```

This makes the purpose of the code clearer, and clearer code is always a good thing.

Now lets write a function that uses brute force to solve a TSP problem. The header will look like this:

```
void brute_force(const Tsp_map& cities) {
// ...
}
```

This is *not* inside the `Tsp_map` function. Instead, it is a stand-alone
function that takes a `Tsp_map` as input.

In pseudocode, the brute force algorithm goes like this:

- get an initial tour; call it T
- best_tour ⇦ T
- best_score ⇦ score(T)
- while there are more permutations of T do the following

- generate a new permutation of T
- if score(T) < best_score then

- best_tour ⇦ T
- best_score ⇦ score(T)
- print best_tour and best_score

As is often done in pseudocode, we use an arrow “⇦” to indicate variable assignment. The reason for this is that it is more suggestive than “=”, plus it lets us use “=” in the usual mathematical way in pseudocode if we need it.

The next step is to convert the pseudocode to C++:

```
void brute_force_solver(const Tsp_map& cities) {
Tour tour(cities.get_default_tour());
double best_score = cities.score(tour);
Tour best_tour(tour);
cout << tour << " score = " << best_score << endl;
while (next_permutation(tour.begin() + 1, tour.end())) {
double s = cities.score(tour);
if (s < best_score) {
best_score = s;
best_tour = tour;
}
cout << tour << " score = " << s << endl;
} // while
cout << "best tour: " << best_tour
<< "\nscore = " << best_score << endl;
}
```

The most interesting detail here is how the permutations are generated. It
turns out that the C++ standard template library (the STL) has a function
called `next_permutation` that will re-arrange the elements of a sequence to
the next permutation in *lexicographic order*.

Lexicographic order is a generalization of alphabetical order that works with
numbers. By starting with the permutation 0, 1, 2, ..., n - 1,
`next_permutation` guarantees to cycle through all possible permutations,
returning `false` when it as the last one.

Notice that we pass in `tour.begin() + 1` instead of `tour.begin()`:

```
while (next_permutation(tour.begin() + 1, tour.end())) {
// ...
```

That’s because we know, from our definition of the problem, that the first element of a tour should always be 0. Thus we only need to permute the n - 1 numbers after 0.

Solving the TSP by brute force has a couple of important benefits:

- It is guaranteed to find a shortest tour through the cities.
- It is conceptually quite straightforward, i.e. it just looks at all possible tours and finds the shortest one.

For small number of cities the brute-force solver works well. For example:

```
int main() {
Tsp_map cities;
cities.add(0, 0);
cities.add(10, 0);
cities.add(0, 10);
cities.add(10, 10);
cities.add(4, 5);
cities.add(7, 1);
cities.add(9, 2);
cities.add(5, 0);
cities.add(6, 1);
cities.add(5, 5);
cities.add(0, 5);
brute_force_solver(cities);
}
```

This 11-city problem checks in about 3.6 seconds on my computer. Adding one more city causes it to run in about 44 seconds, which is close to what you would expect given that it is checking 11 times as many permutations.

As you can see from these two examples, the big problem solving the TSP by brute force is that it’s incredibly slow. To solve an n-city TSP problem requires generating exactly permutations. For even smallish values of , turns out to be huge. For example:

```
n n!
-----
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
```

As n get bigger, grows *worse than exponentially*. If you want to
use brute-force to solve a 20-city problem, then you’ll need to generate
121645100408832000 different permutations, i.e. over 120 *quintillion*
permutations. But that’s nothing compared to the different
permutations you would need to search through for a 100-city problem:

```
933262154439441526816992388562667004907159682643816214685929638\
952175999932299156089414639761565182862536979208272237582511852\
109168640000000000000000000000
```

In practice, no matter how fast your computer, or how many you have, you won’t be able to generate this many permutations in a reasonable amount of time.

If generating all permutations is too slow in practice, then lets try another extreme: generating permutations at random.

Random Tour Algorithm: Generate random tours, and save the shortest one. Stop when you have no more time left to search for tours.

The code for this algorithm is very similar to the code for generating all permutations:

```
void random_guesser(const Tsp_map& cities, int num_guesses = 1000000) {
Tour tour(cities.get_default_tour());
double best_score = cities.score(tour);
Tour best_tour(tour);
for(int i = 0; i < num_guesses; ++i) {
random_shuffle(tour.begin() + 1, tour.end());
double s = cities.score(tour);
if (s < best_score) {
best_score = s;
best_tour = tour;
}
}
cout << "best tour: " << best_tour
<< "\nscore = " << best_score << endl;
}
```

As with the brute-force solver, we use `best_score` and `best_tour` to
keep track of the shortest tour seen so far. Each time through the for-loop,
the tour cities are shuffled using the standard `random_shuffle` algorithm,
and then scored. If this shuffled tour is shorter than the shortest one seen
so far, it’s saved.

It’s up to the programmer to decided how many random guesses should be made. By default, a million random guesses are made, which runs in a couple of seconds on my computer.

However, for large TSP problems random guessing is terrible because it blindly
takes permutations from a *huge* search space. It’s like searching for a
needle in a giant haystack by randomly plucking out one straw at a time.

As mentioned, the TSP is an extremely well-studied problem, and numerous fast algorithms that usually find pretty short (not always the shortest) tour have been created. As just one example of a better method, consider this algorithm for constructing a tour a city at a time:

- Start with city 0 in the tour
- Look at the last city in the tour, and then add to the end of the tour the closest city not already in it.
- Repeat the previous step until all cities have been added.

While this algorithm does not guarantee to always find a shortest possible tour, it is certainly better than random guessing, and fast enough to be applied to very large TSP instances.

It’s currently unknown if there is an algorithm that can *always* guarantee to
efficiently find the shortest tour in any TSP. The majority of computer
scientists probably believe that there is *no* such algorithm, but this has
not been proved.

If you’d like to learn more about the TSP and how to solve it efficiently, a
good starting place is this TSP page. One of
the many interesting things on that page is an *optimal* tour of all of
Canada’s 4,663 main cities.

Brute force doesn’t work well for the TSP, but for some problems it is a good solution method. For example, perhaps you have heard of “alphametic”, or “cryptarithm” puzzles like this:

```
S E N D
+ M O R E
---------
M O N E Y
```

Each letter of the puzzle stands for a single digit, and different letters must have different values. Also, letters at the start of a word can’t be 0.

A brute force solution to this puzzle work like this:

Create a vector

`v`of 10 integers, initialized to 0, 1, 2, ..., 9. Since there are eight different letters in the puzzle, we only care about the first 8 elements of this vector,`v[0]`to`v[7]`.Associate letters with elements in the vector, e.g.:

S is v[0]

E is v[1]

N is v[2]

D is v[3]

M is v[4]

O is v[5]

R is v[6]

Y is v[7]

Generate

*all*permutations of`v`, and after each permutation has been generated check if it solves the puzzle. Since`v`has 10 elements, only different permutations are checked. This can be done quite quickly on modern computers.

Here’s a program that solves the puzzle:

```
#include "std_lib_cmpt125.h"
// 0 1 2 3 4 5 6 7
// Variables: S, E, N, D, M, O, R, Y
// S and M not 0
void check(const vector<int>& v) {
int send = 1000 * v[0] + 100 * v[1] + 10 * v[2] + v[3];
int more = 1000 * v[4] + 100 * v[5] + 10 * v[6] + v[1];
int money = 10000 * v[4] + 1000 * v[5] + 100 * v[2] + 10 * v[1] + v[7];
if (send + more == money && v[0] != 0 && v[4] != 0) {
cout << "Solution found: ";
for(int i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
cout << endl;
}
}
int main() {
cout << "The SEND + MORE = MONEY Puzzle\n\n";
vector<int> vars(10); // initialize to 0, 1, 2, ..., 9
for(int i = 0; i < 10; ++i) {
vars[i] = i;
}
int count = 0;
check(vars);
while (next_permutation(vars.begin(), vars.end())) {
check(vars);
++count;
}
cout << "Permutations checked: " << count << endl;
} // main
```

On my computer, this program takes 0.08 seconds to find two solutions:

```
Solution found: 9 5 6 7 1 0 8 2 3 4
Solution found: 9 5 6 7 1 0 8 2 4 3
```

These are actually the same solution since we only care about the first 8 digits; the last 2 are not used in this puzzle:

```
9 5 6 7
+ 1 0 8 5
---------
1 0 6 5 2
```