• The Traveling Schoolteacher Problem
• The Mathematical Model
• The Pseudocode
• The Java Code
  • TSTP Class Fields and Methods
  • Explore: Base Case
  • Explore: Recursive Case
• Example Graphs
• Results
  • Walltime vs Number of Nodes
• Conclusion
• References

The Traveling Schoolteacher Problem

The Traveling Schoolteacher Problem (TSTP) is a variation on the Traveling Salesperson Problem (TSP).

The Traveling Schoolteacher Problem supposes a schoolteacher that is traveling from school to school in order to give lessons at different schools. Being a poor schoolteacher, they are only able to afford an older car that gets bad mileage and has a small gas tank.

After visiting each school …

• Before We Begin: The Code
• Timing Scripts
• Before You Time: Developing Your Algorithm
• Beginning Your Timing Journey
• Statistical Timing, a.k.a., If You Give A Mouse A Cookie
• Hierarchical Timing Strategy
• Single Problem/Program/Binary
• Multiple Problem/Program/Binary
• Statistical Averaging
• Results
• Summary

Before We Begin: The Code

Note that all of the code discussed/shown in this post is available from the traveling salesperson problem repository on git.charlesreid1.com. The guava/ directory contains the guava solution to the traveling salesperson problem, along with the timing scripts discussed below, and several example output files.

Introduction

Timing a piece …

• Intro
• The Graphs We Are Solving
  • Visualizations of Graphs
• Guava TSP Solution
  • Timing the TSP Solution
• Improving the Guava TSP Solution
  • The Flaw
  • Fixing the Flaw
  • The Pessimist Algorithm
• Timing Results
• Future Work

Intro

In a prior blog post we introduced you to the traveling salesperson problem (TSP), which involves finding the shortest path through every city in a group of cities connected by a network of roads. Using Google Guava, we have implemented a solution to the TSP in Java.

Our philosophy toward timing, profiling, and optimization is that it is always best to work from data - and timing …

Table of Contents

• Background: Traveling Salesperson Problem (TSP)
• Graphs
  • Number of Edges
• Solution: Recursive Backtracking
• Solving the TSP with Java and Guava
  • Basics of Guava
  • Guava Graphs
  • Guava Mutable vs Immutable
  • Importing Guava
  • TSP Class
  • Node Class
  • Edge Class
• TSP Constructor and Building the Graph
  • Constructor
  • Build Graph Method
• Solving and Exploring with Recursive Backtracking
  • Solve Method
  • Explore (Backtrack) Method
• Next Steps: Timing and Profiling
• Sources

Background: Traveling Salesperson Problem (TSP)

The traveling salesperson problem, or TSP, is a classic programming problem and an important one in computer science, and applications in operations research and optimization.

The idea is that …