Algorithms For Dummies

 Challenging Difficult Problems

    start, distance = (0,0)

    for next_one in solution:

        distance 

+= D[start, next_one]

        start = next_one

    distance 

+= D[start,0]

    if distance <= best_solution[1]:

        best_solution = [[0]

+list(solution)+[0], distance]

        print ('Best solution so far: %s kms' %

               str(best_solution)[1:-1])

Best solution so far: [0, 1, 2, 3, 4, 0], 86 kms

Best solution so far: [0, 1, 3, 2, 4, 0], 80 kms

Best solution so far: [0, 4, 2, 3, 1, 0], 80 kms

The brute-force algorithm quickly determines the best solution and its symmetric 

path. However, as a result of the small problem size, you obtain a prompt answer 

because, given four cities, just 24 possible solutions exist. As the number of cities 

increases, the number of permutations to test becomes intractable, even after 

removing the symmetric paths (which halves the permutations) and using a fast 

computer. For example, consider the number of computations when working with 

13 cities plus the starting/ending point:

from scipy.special import perm

print (perm(13,13)/2)

3113510400.0

Dynamic programming can simplify the running time. The Held–Karp algorithm 

(also known as the Bellman–Held–Karp algorithm because Bellman published it 

in 1962, the same year as Michael Held and Richard Karp) can cut time complexity 

to 

O(2

n

n

2

)

. It’s still exponential complexity, yet it requires less time than applying 

the exhaustive enumeration of all tours by brute force.

Approximate and heuristic algorithms can provide fast and useful results (even 

though the result may not always reflect the optimal solution, it’s usually good 

enough). You see TSP again later in the book (see Chapters 18 and 20), when deal-

ing with local search and heuristics.

To  find  the  best  TSP  solution  for  n cities, starting and ending from city 0, the 

algorithm proceeds from city 0 and keeps records of the shortest path possible, 

considering different settings. It always uses a different ending city and touches 

only a city subset. As the subsets become larger, the algorithm learns how to solve 

---

CHAPTER 16