Traveling Band
Problem: Need to schedule concerts for the year
- Visit each city exactly once
- Want to minimize travel time riding the bus
- How do you calculate the best path?
- Try all paths, from every starting point, how long does this take?
- atlanta, boston, dallas, durham, new york, raleigh, ...
- boston, atlanta, dallas, durham, new york, raleigh, ...
- and so on ...
- For N cities?
- Other useful questions: Is there a tour for under 4000 miles? 6000 miles?
- Is close good enough?
- This problem is famously known as "traveling salesman" problem
| Number of Cities
| All paths - N!
| time to solve
10^9 instruct/sec
|
| 10
| 3 million
| < sec
|
| 15
| 10^12
| 16 min
|
| 18
| 10^15
| 11 days
|
| 20
| 10^18
| 31 years
|
| 25
| 10^25
| 10^8 years
|
Are Hard Problems easy?
- P = easy problem, NP ="hard" problem
- P means solvable in polynomial time
- Difference between N, N^2, N^10
- Example: selection sort - N^2
- NP means non-deterministic, polynomial time
- guess a solution and verify it efficiently
- Example: traveling band, traveling salesman
- Question: Does P = NP?
- If yes, a whole class of difficult problems can be solved efficiently -
one problem is reducible to another
- if no, none of the hard problems can be solved efficiently
