Some algorithmic problems simply don't have good state-of-the-art solutions that could run within a time acceptable to the user. For example, consider a program that deals with complex optimization problems, such as the Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP). Both problems are NP-hard problems in combinatorial optimization. The exact algorithms that have low complexity for such problems are not known; this means that the size of a problem that can be practically solved is greatly limited. For very large inputs, it is unlikely that you'll be able to provide the correct solution in enough time.
Fortunately, it's likely that a user will be interested not in the best possible solution, but one that is good enough and can be obtained in a timely manner. In these cases, it makes sense to use heuristics or approximation algorithms whenever they provide acceptable results:
- Heuristics solve given problems by trading optimality, completeness, accuracy, or precision for speed. They concentrate on speed, but it may be hard to prove the quality of their solutions compared to the result of exact algorithms.
- Approximation algorithms are similar in idea to heuristics, but unlike heuristics have provable solution quality and runtime bounds.
There are many known good heuristics and approximation problems that can solve extremely large TSP problems within a reasonable amount of time. They also have a high probability of producing results—just 2-5% from the optimal solution.
Another good thing about heuristics is that they don't always need to be constructed from scratch for every new problem that arises. Their higher-level versions, called metaheuristics, provide strategies for solving mathematical optimization problems that are not problem-specific and can thus be applied in many situations. Some popular metaheuristic algorithms include the following:
- Simulated annealing
- Genetic algorithms
- Tabu search
- Ant colony optimization
- Evolutionary computation