Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

You may wonder whether the result offered by the script is really the best one 

achievable. Unfortunately, the only way to be sure is to know the right answer, 

which means running a brute-force algorithm (when feasible in terms of running 

time on your computer). This chapter doesn’t use brute force for the knapsack 

problem but you’ll see a brute-force approach used in the traveling salesman 

problem that follows.

Touring around cities

The traveling salesman problem (TSP for short) is at least as widely known as the 

knapsack problem. You use it mostly in logistics and transportation (such as the 

derivative Vehicle Routing Problem shown at 

http://neo.lcc.uma.es/vrp/ 

vehicle-routing-problem/

), so it doesn’t see as much use as the knapsack prob-

lem. The TSP problem asks a traveling salesperson to visit a certain number of 

cities and then come back to the initial starting city (because it’s circular, it’s 

called a tour) using the shortest path possible.

TSP is similar to graph problems, but without the edges because the cities are all 

interconnected. For this reason, TSP usually relies on a distance matrix as input, 

which is a table listing the cities on both rows and columns. The intersections 

contain the distance from a row city to a column city. TSP problem variants may 

provide a matrix containing time or fuel consumption instead of distances.

TSP is an NP-hard problem, but you can solve the problem using various 

approaches, some approximate (heuristic) and some exact (dynamic programming). 

The problem, as with any other NP-hard problem, is the running time. Although 

you can count on solutions that you presume optimally solve the problem (you 

can’t be certain except when solving short tours), you can’t know for sure with 

problems as complex as touring the world: 

http://www.math.uwaterloo.ca/

tsp/world/

. The following example tests various algorithms, such as brute force, 

greedy, and dynamic programming, on a simple tour of six cities, represented as 

a weighted graph (see Figure 16-1). (You can find this code in the 

A4D; 16; TSP.

ipynb

  file  on  the  Dummies  site  as  part  of  the  downloadable  code;  see  the 

Introduction for details.)

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

D = np.array([[0,20,16,25,24],[20,0,12,12,27],

              [16,12,0,10,14],[25,12,10,0,20],

              [24,27,14,20,0]])

---

CHAPTER 16