Are there problems that no algorithm can ever solve in a reasonable amount of time?
What is the difference between a reasonable and an unreasonable time algorithm?
You live in house 1 and want to visit all three friends, then return home. You can only visit each house once.
Think: What information would you need to figure out which of these paths is the best?
Here are the same three paths, now with distances labeled on each leg.
The algorithm must check every possible path and compare distances to guarantee finding the shortest one.
With 4 houses, there were 6 paths to check. That was manageable.
But what happens as the number of houses grows? How many paths would you need to check if you had 10 friends? 20? 100?
Each time you add one more house, how does the number of possible paths change? As you add more, does the number grow slowly or quickly?
A traveling salesman must visit a set of cities exactly once and return home. The goal is to find the shortest possible route. Unlike our activity, the salesman can start from any city.
With just 10 cities there are over 3.6 million paths to check.
With 20 cities it is over 2.4 quintillion. Checking 1 billion possible paths a second would take over 76 years.
| Cities (n) | Paths to Check |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5,040 |
| 8 | 40,320 |
| 9 | 362,880 |
| 10 | 3,628,800 |
At each step, count how many unvisited cities you can choose from. Multiply all those counts together.
Pick a starting city: n options
Next city (haven't visited it yet): n−1 options
Next city: n−2 options
…continuing until only 1 city remains
n × (n−1) × (n−2) × … × 1 = n!
Example: 4 cities, any start
4 cities → pick start, then 3 unvisited, then 2, then 1:
4 × 3 × 2 × 1 = 24
7 cities → pick start, then 6, 5, 4, 3, 2, 1:
7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040
10 cities:
10 × 9 × 8 × … × 1 = 3,628,800
That is a lot of possible paths for only 10 cities, and the numbers only get more extreme from there.
A problem is any task that may or may not be solved with an algorithm. Sorting a list is a problem. Sorting the specific list (2, 3, 1, 7) is an instance of that problem.
The answer is simply yes or no.
"Is there a path that visits all cities in under 100 km?"
The answer is the best possible value or solution.
"What is the most valuable set of items that fits in a suitcase?"
The Traveling Salesman Problem can be solved with an algorithm that checks every possible option. The problem is not that we lack an algorithm: the problem is that the algorithm runs in unreasonable time.
As the number of nodes (locations to visit) increases, the number of paths grows factorially. Even the most powerful computers cannot finish for large inputs.
The Traveling Salesman Problem is an optimization problem that requires unreasonable time to solve exactly. Most practical instances of the problem cannot be solved with a guaranteed-optimal answer in a useful amount of time.
A heuristic provides a "good enough" solution to a problem when an exact solution is impractical or impossible.
Rather than spending unreasonable time finding the perfect answer, a heuristic finds an answer that is close enough to be useful in a fraction of the time.
Move down to open the Traveling Salesman activity. Start on Level 1 and try to find the best path to visit all nodes and return home. Write down a plan or heuristic for how you choose which node to visit next.
Your heuristic may not always find the absolute best path, but it should consistently find a good one.
Note: A heuristic is a strategy or rule of thumb, not a guaranteed-optimal algorithm. Write yours as a simple rule you can apply at each step.
The Traveling Salesman activity will open here when launched by your instructor.
Open ActivityMove down to open the Traveling Salesman activity. Apply your heuristic on at least three different levels. For each level, record:
The Traveling Salesman activity will open here when launched by your instructor.
Open ActivityHow did you create your heuristic? Did you change it after testing it out on different levels?
What rule did you follow at each step? Did your rule always work, or did it sometimes lead you to a longer path?
A good heuristic can be refined through testing. If you noticed it consistently failing in certain situations, what rule might fix it?
At each node, travel to the next closest unvisited node. Repeat until all nodes are visited, then return home.
This strategy is fast to apply and often produces a short path. It is a classic example of a greedy heuristic: always make the locally best choice.
Limitation: Nearest neighbor can sometimes miss a shorter overall path because a locally close node leads to a very long leg later. It is "good enough" but not guaranteed optimal.
Example: apply nearest neighbor
Start at H. Each step, go to the nearest unvisited node.
The Traveling Salesman activity will open here when launched by your instructor.
Open ActivityThe Traveling Salesman Problem is an optimization problem: we are trying to find the best path, not just any path.
There is no known algorithm that solves the TSP in reasonable time. The exact solution requires checking every possible path, which grows factorially and becomes impractical very quickly.
We use a heuristic to find a solution that is "good enough" for most instances of the problem, in a fraction of the time an exact solution would require.
The answer is yes or no.
"Is there a path shorter than 100 km?"
The answer is the best possible value.
"What is the shortest path?"
No algorithm can ever guarantee a correct yes-or-no answer for all instances.
"Will this program eventually stop running?"
Undecidable problems are not just hard: it has been mathematically proven that no algorithm exists that can solve them correctly in all cases.
Watch for: what makes the Halting Problem provably impossible to solve for all programs.
There are problems we have mathematically proven that no computer will ever be able to solve for all inputs. The Halting Problem is the most famous example.