November 2024
Intermediate to advanced
416 pages
11h 11m
English
The problem of designing an optimal sightseeing tour lends itself perfectly to a graph formulation. Depending on our travel preferences, we might want to visit each of a set of major landmarks exactly once, minimize the total distance we travel, or visit every shop-lined street in our destination city. Each of these formulations corresponds to a classic graph problem: planning paths through a graph.
In this chapter, we consider several variations of this core problem. Hamiltonian paths visit each node exactly once and can help us plan trips where we want to visit a discrete set of sites. Solving the traveling salesperson ...