In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover"[1]) is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space.
This is achieved by trading optimality, completeness, accuracy, or precision for speed.
A heuristic function, also simply called a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow.
[2] The objective of a heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand.
But it is still valuable because finding it does not require a prohibitively long time.
Heuristics may produce results by themselves, or they may be used in conjunction with optimization algorithms to improve their efficiency (e.g., they may be used to generate good seed values).
Results about NP-hardness in theoretical computer science make heuristics the only viable option for a variety of complex optimization problems that need to be routinely solved in real-world applications.
Heuristics underlie the whole field of Artificial Intelligence and the computer simulation of thinking, as they may be used in situations where there are no known algorithms.
One way of achieving the computational performance gain expected of a heuristic consists of solving a simpler problem whose solution is also a solution to the initial problem.
An example of approximation is described by Jon Bentley for solving the travelling salesman problem (TSP): so as to select the order to draw using a pen plotter.
TSP is known to be NP-hard so an optimal solution for even a moderate size problem is difficult to solve.
[4] Another example of heuristic making an algorithm faster occurs in certain search problems.
Initially, the heuristic tries every possibility at each step, like the full-space search algorithm.
But it can stop the search at any time if the current possibility is already worse than the best solution already found.
In such search problems, a heuristic can be used to try good choices first so that bad paths can be eliminated early (see alpha–beta pruning).
In the case of best-first search algorithms, such as A* search, the heuristic improves the algorithm's convergence while maintaining its correctness as long as the heuristic is admissible.
In their Turing Award acceptance speech, Allen Newell and Herbert A. Simon discuss the heuristic search hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure.
A heuristic method can accomplish its task by using search trees.
It is selective at each decision point, picking branches that are more likely to produce solutions.
[5] Antivirus software often uses heuristic rules for detecting viruses and other forms of malware.
The most advanced part of behavior-based heuristic scanning is that it can work against highly randomized self-modifying/mutating (polymorphic) viruses that cannot be easily detected by simpler string scanning methods.
Others are just rules of thumb based on real-world observation or experience without even a glimpse of theory.
When a heuristic is reused in various contexts because it has been seen to "work" in one context, without having been mathematically proven to meet a given set of requirements, it is possible that the current data set does not necessarily represent future data sets (see: overfitting) and that purported "solutions" turn out to be akin to noise.
Statistical analysis can be conducted when employing heuristics to estimate the probability of incorrect outcomes.
, "admissible" means roughly that the heuristic underestimates the cost to the goal or formally that
It is formed irregularly from the Greek word heuriskein, meaning "to find".