What do we do now? TSP is NP-hard. So, we'd be real surprised if
we could actually solve this both optimally and efficiently in the
worst case.
But, we still need to solve the problem. People are depending on
us! What can we do? Lower our standards!
- Find an approximation quickly.
- Find an optimal solution as quickly as you can (given that we'll
get worst-case exponential-time performance).
- Try to find a solution quickly that isn't too awful (``empirical
miracle'').
Next: APPROXIMATION
Up: TRAVELING SALESPERSON PROBLEM
Previous: Linking HAM and TSP