AP® Computer Science Principles · Big Idea 3 · Topic 3.17
The Traveling Salesman and Combinatorial Explosion
Watch it explained
- How it worksHow does the count of possible routes through n cities grow as a factorial?
- Worked exampleFind the number of distinct routes through 10 cities and set it beside the number for 5 cities.
- Worked exampleFind how many years a computer checking a billion routes every second would need to check all routes through 15 cities.
- Going furtherWhat happens to a brute force route finder when the city count climbs from 12 to 20?
- Ties togetherHow does the route explosion connect to problems that have no efficient algorithm at all?
Check yourself
Your turn1 of 2
A brute-force route finder must check 3,628,800 distinct routes to solve a delivery problem across 10 cities. At 696447 routes checked per second, how many seconds would it take to check every route?End of topic.