Chapter 12, Problem 41CRP

Explanation of Solution

The number of different paths and time required to compute the distances between cities:

Travelling salesman problem deals with the optimization of the path of travel through different cities.

Each pair of city is connected by a unique road. There are $15$ cities. A path will require two cities to be formed. In this situation, the possible combinations of the available path from one city to another will be $C{}_2$.

So, the total number of paths is as follows:

$\begin{array}{c}C{}_2=\frac{15!}{2!\times \left(15-2\right)!}\\ =105\end{array}$

Therefore, there are $105$ unique paths available between cities.

Now, time taken to compute length of a path is one microsecond