Skip to content

Traveling Salesman

Every algorithm in this unit has had an exact answer waiting at the end. This lab is the exception — a problem so expensive to solve exactly that with just 30 cities, checking every route would outlast the universe. Time to meet the workaround the real world runs on.

Overview

You'll play the Traveling Salesman Game: visit every city once and return home by the shortest route you can find. Along the way you'll discover why "just check every path" stops being an option almost immediately, and you'll design your own heuristics — rules of thumb that trade a guaranteed-best answer for one that's good enough, fast enough.

Builds on: Merge Sort — the end of the unit's tour of exact algorithms, and the reason this lab needs a different tool entirely.

Play the Traveling Salesman Game

You've got it when…

  • You've tied or beaten the computer's distance on a 5-city game.
  • You can say how many possible paths 5 cities and 30 cities each have — and what that means for solving by brute force.
  • You've written two different heuristics and played a 30-city game with each.
  • You can argue whether your heuristics were "good enough," and for what.

Collaboration & AI

Work: On your own. Comparing routes and heuristics with your neighbors afterward is encouraged — that's the point of the Consider questions.

AI — AIAS Level 1, No AI: Your rule of thumb, your routes. What the levels mean.

Recording your answers

Answers and screenshots for the numbered questions below go in your notebook.

Starting Small

  1. Set the number of cities to 5.

    The number of cities selector set to 5.

  2. Click on a city of your choice to start with (any dot).

  3. Click a second dot, then a third, and so on to create a path between the cities.

  4. Visit each city only once.

  5. Complete the path by returning to the first city.

  6. Play until you tie or beat the distance to beat shown at the bottom of the screen.

    Note: it is unlikely that you will find a shorter path than the computer with only 5 cities…just try to tie!

    Your screen should look like this.

    A completed 5-city path with the total distance matching the distance to beat.

  7. Question: how many possible paths are there to explore between 5 cities?

  8. Paste a screenshot of your tie/win in your notebook.

Scaling Up

We have worked with a number of algorithms, which are exact, step-by-step solutions. Some problems cannot be solved with algorithms. For those problems, we use heuristics, a practical shortcut or rule of thumb that:

  • Aims for a good (but not guaranteed optimal) solution
  • Is often used when exact solutions are too slow or complex
  • May sacrifice accuracy for speed or simplicity

  1. Set the number of cities to 30.

    The number of cities selector set to 30.

  2. How many possible paths are there to explore between 30 cities?

    Stuck? Open for a hint.

    From your starting city you can go to any of the 29 others, then any of the remaining 28, and so on. Multiply it out — or look up the factorial function on your calculator — and compare the result to, say, the number of seconds since the universe began.

  3. Write a heuristic — a simple rule that you will use to decide which city you will visit next from any city you are currently at.

    (Bad) example: "I will always visit the farthest unvisited city from my current city."

  4. Follow your heuristic to play one 30-city game and paste a screenshot in your notebook.

  5. Write a second heuristic that tries a different approach.

  6. Follow your heuristic to play one 30-city game and paste a screenshot in your notebook.

Warning

Follow your heuristic literally, even when your eyes can see it's about to make a bad choice. The moment you override it with human judgment, you're no longer measuring the heuristic — and a computer following your rule wouldn't get to cheat.

Consider:

  • Did either of your heuristics beat the computer?
  • Is the computer guaranteed to have the shortest possible path?
  • Is your heuristic "good enough"? Would you be happy with it if you were paying for gas to drive between these cities or the airline tickets to fly between them?

Turn It In

  • Your answers to questions 7, 10, 11, and 13, in your notebook.
  • Your three game screenshots (steps 8, 12, and 14), in your project notebook.
  • Your thoughts on the three Consider questions, in your project notebook.

How It's Graded

This lab is worth up to 4 points. One score covers everything you turn in.

Score What it looks like
4 — Excellent Path counts for 5 and 30 cities computed with visible reasoning (not guessed), two genuinely different heuristics written as rules a computer could follow, all three screenshots in the notebook, and Consider answers that argue "good enough" using your own routes as the evidence.
3 — Above Average Everything present; the two heuristics are near-duplicates, or a path count is right without the reasoning.
2 — Average One heuristic played instead of two, or screenshots missing — the games happened but the evidence didn't.
1 — Below Average Screenshots with no written answers, or answers with no games played.
0 — Failing Nothing in the notebook.