Sophomores meet the traveling salesperson problem
David Carlson · Journal of computing sciences in colleges · 2018
When students in computer science first encounter the traveling salesperson problem (TSP), often in their first two years, there are many interesting things that they can learn. This encounter might well occur in a discrete mathematics class, where they can easily use the counting techniques of discrete mathematics to show that the brute-force solution method has factorial running time. Textbooks and instructors are likely to say that this is why methods that quickly find good approximate solutions are used instead. Students might wonder, however, if there are faster methods of obtaining exact solutions. One that might come to mind is to use backtrack search to avoid recomputing partial sums of costs for the traveling salesperson. This paper presents an analysis of this method, finds its running time, and shows that this is not a substantial improvement. This paper also investigates if an exact formula can be found for the number of additions used by this method and succeeds in doing so. Better yet, students in a discrete mathematics course likely have the background to follow the proofs for these two results and can thus convince themselves that what they might think should be a big improvement is not. In the process they learn that mathematics can help them to discover important aspects of a computer science problem. Strong students might be able to create the proofs themselves if they are given the theorems and perhaps some hints.