Generic Data Structures and Algorithms in Go: An Applied Approach Using Concurrency, Genericity and Heuristics

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022

R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_18

18. Branch-and-Bound Solution to TSP

Richard Wiener¹  

(1)

Colorado Springs, CO, USA

 

The previous chapter introduced the famed Travelling Salesperson Problem (TSP). A brute-force solution was presented. Like all exact solutions to this problem, it is computationally intractable. A third-party package was presented along with code for graphically displaying a TSP tour.

This chapter presents another exact solution to TSP using a powerful technique, branch and bound. It too is computationally intractable.

In the next section, we introduce the technique of branch and ...