Heuristic (computer science)

In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω eurísko "I find, discover") 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. In a way, it can be considered a shortcut.

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. For example, it may approximate the exact solution.

Some heuristics have a strong underlying theory; they are either derived in a top-down manner from the theory or are arrived at based on either experimental or real world data. Others are just rules of thumb based on real-world observation or experience without even a glimpse of theory. The latter are exposed to a larger number of pitfalls.

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. To use a heuristic for solving a search problem or a knapsack problem, it is necessary to check that the heuristic is admissible. Given a heuristic function vg in a directed graph v0,v1,⋯,vn, "admissible" means roughly that the heuristic underestimates the cost to the goal or formally that i,g∈[0,1,...,n].

If a heuristic is not admissible, it may never find the goal, either by ending up in a dead end of graph vj where Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. OSTI 5127296.

↑ Allen Newell and Herbert A. Simon (1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID 5581562.

↑