Heuristic (computer science)
In computer science and optimization a heuristic is a rule of thumb learned from experience but not always justified by an underlying theory. Heuristics are often used to improve efficiency of effectiveness of optimization algorithms, either by finding an approximate answer when the optimal answer would be prohibitively difficult or to make an algorithm faster. Usually, heuristics do not guarantee that an optimal solution is ever found. On the other hand, results about NP-hardness in theoretical computer science make heuristics the only viable alternative for many complex optimization problems which are significant in the real world.
An example of an approximation is one Jon Bentley described for solving the travelling salesman problem (TSP) where it was selecting the order to draw using a pen plotter. TSP is known to be NP-hard so an optimal solution for even moderate size problem is intractable. Instead the greedy algorithm can be used to to give a good but not optimal (it is an approximation to the optimal answer) in a short amount of time. The greedy algorithm heuristic says to pick whatever is currently the best next step regardless of whether that precludes good steps later. It is a heuristic in that practice says it is a good enough solution, theory says there are better solutions (and even can tell how much better in some cases).[1]
An example of making an algorithm faster occurs in certain search methods where it tries every possibility at each step but can stop the search if the current possibility is already worst then the best solution already found; in this sort of algorithm a heuristic can be used to try good choices first so that later it can eliminate bad paths early. (See alpha-beta pruning).
[edit] See also
- Metaheuristic: methods for controlling and tuning basic heuristic algorithms, usually with usage of memory and learning.
- Reactive search optimization: methods using online machine learning principles for self-tuning of heuristics.
- Genetic algorithms: heuristics using genetic principles.
[edit] References
- ^ Writing Efficient Programs, Jon Louis Bentley, Prentice-Hall Software Series, 1982, Page 11-
