heuristic
In plain wordsA rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- 1
Search
A function h(n) that guesses, for a state n, the least cost still needed to reach a goal, used to steer informed searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next. toward promising states — for example, straight-line distance on a road map, or the number of misplaced tiles in a sliding puzzle. A heuristic is admissibleadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route. if it never overestimates the true cost and consistent if its estimates never drop by more than the cost of an action; these properties make A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first. optimal. Good heuristics are often derived by solving a relaxed version of the problem that ignores some constraints, or from pattern databases storing exact costs of subproblems; they can also be learned from solved examples.
Our heuristic counts unsatisfied goals, which ignores interactions between them but is cheap to compute.
- 2
General
Any rule of thumb, approximation or problem-specific strategy that usually yields good solutions quickly but without a guarantee of optimality or correctness, such as 'try the most constrained variable first' in constraint solvingconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes. or a greedy rule in scheduling. In this sense whole methods such as genetic algorithmsgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve. and simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops. are called heuristic or metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one..
- 3
Psychology
A mental shortcut that people use to judge or decide under uncertainty, such as judging frequency by how easily examples come to mind. Amos Tversky and Daniel Kahneman's 1974 work showed that such shortcuts produce systematic biases, a theme now echoed in studies of language-modellarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code. errors.
Origin
From Greek heuriskein, 'to find' (as in 'eureka'). George Pólya's How to Solve It (1945) revived heuristic as the study of problem-solving methods; Allen Newell, Cliff Shaw and Herbert Simon's Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program. (1956) made 'heuristic programming' a founding idea of AI, and the 1968 A* paper fixed the estimate-function sense.
Usage note
As an adjective it also means plausible but not rigorous ('a heuristic argument'). In machine learning, calling a method 'a heuristic' often implies it was hand-designed rather than learned or derived from principles.
Related
- admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route.
- A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
- best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
- hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.
Sources
- Pólya, G. (1945). How to Solve It. Princeton University Press.
- Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
Mentioned in
A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first., algorithmalgorithm, n.: A precise, step-by-step procedure for solving a problem or doing a task, like a recipe a computer can follow. In the news, 'the algorithm' often means software that ranks what you see online., automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility., Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., bounded rationalitybounded rationality, n.: The idea that real decision-makers, whether people or machines, cannot consider every option or compute the perfect choice, so they make reasonable decisions within limits of time, information and thinking power., combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., Daniel KahnemanDaniel Kahneman, prop. n.: An Israeli-American psychologist who showed how human judgment systematically errs and popularized the idea of fast, intuitive versus slow, deliberate thinking, now used to describe AI reasoning., Dijkstra's algorithmDijkstra's algorithm, n.: A classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next., General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap., Herbert A. SimonHerbert A. Simon, prop. n.: An American scientist of decision-making who, with Allen Newell, wrote some of the first AI programs and argued that minds and computers both think by manipulating symbols., hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program., Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average., NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., physical symbol system hypothesisphysical symbol system hypothesis, n.: The 1976 claim by two AI pioneers that a machine which stores and rearranges symbols according to rules has everything needed for general intelligence, and that anything generally intelligent must be such a machine., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., System 1 and System 2System 1 and System 2, phr.: A popular way of describing two modes of thinking: fast, automatic and intuitive (System 1) versus slow, effortful and deliberate (System 2). AI researchers borrow it to contrast instant answers with step-by-step reasoning., admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route., ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out., best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next., branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand., DENDRALDENDRAL, prop. n.: A program begun at Stanford in 1965 that worked out the structure of chemical molecules from laboratory measurements using rules taken from expert chemists. It is usually called the first expert system.