Heuristic function
Encyclopedia
A heuristic function, or simply a heuristic, is a function
that ranks alternatives in various search algorithm
s at each branching step based on the available information (heuristic
ally) in order to make a decision about which branch to follow during a search.
s, a heuristic is a function
,
defined on the nodes of a search tree
, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A* to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A* search will expand nodes that have the lowest value for
, where 
is the (exact) cost of the path from the initial state to the current node. If 
is admissible
—that is, if
never overestimates the costs of reaching the goal—, then A* will always find an optimal
solution.
The classical problem involving heuristics is the n-puzzle
. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible.
choices at each node and a depth of 
at the goal node, a naive searching algorithm would have to potentially search around 
nodes before finding a solution. Heuristics improve the efficiency of search algorithms by reducing the branching factor
from
to a lower constant 
, using a cutoff mechanism. The branching factor can be used for defining a partial order on the heuristics, such that 
if 
has a lower branch factor than 
for a given node 
of the search tree. Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular problem, as they are more computationally efficient.
community.
Several common techniques are used:
Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle
better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube
.
If
is consistent then the value of 
for each node along a path to goal node are non decreasing.
= the number of misplaced tiles. This is also known as the Hamming Distance
. In the pictured example, the start state has
= 8. Clearly, 
is an admissible heuristic because any tile that is out of place will have to be moved at least once.
= the sum of the distances of the tiles from their goal positions. Because tiles cannot be moved diagonally, the distance counted is the sum of horizontal and vertical distances. This is also known as the Manhattan Distance
. In the pictured example, the start state has
= 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18. Clearly, 
is also an admissible heuristic because any move can, at best, move one tile one step closer to the goal.
As expected, neither heuristic overestimates the true number of moves required to solve the puzzle, which is 26. Additionally, it is easy to see from the definitions of the heuristic functions that for any given state,
will always be greater than or equal to 
. Thus, we can say that 
dominates 
.
(example taken from Russell and Norvig)
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
that ranks alternatives in various search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
s at each branching step based on the available information (heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
ally) in order to make a decision about which branch to follow during a search.
Shortest paths
For example, for shortest path problemShortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
s, a heuristic is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
,
defined on the nodes of a search treeSearch tree
In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...
, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A* to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A* search will expand nodes that have the lowest value for
, where is the (exact) cost of the path from the initial state to the current node. If is admissibleAdmissible heuristic
In computer science, specifically in algorithms related to Pathfinding, a heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal...
—that is, if
never overestimates the costs of reaching the goal—, then A* will always find an optimalOptimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
solution.
The classical problem involving heuristics is the n-puzzle
N-puzzle
The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle...
. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible.
Effect of heuristics on computational performance
In any searching problem where there are choices at each node and a depth of at the goal node, a naive searching algorithm would have to potentially search around nodes before finding a solution. Heuristics improve the efficiency of search algorithms by reducing the branching factorBranching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....
from
to a lower constant , using a cutoff mechanism. The branching factor can be used for defining a partial order on the heuristics, such that if has a lower branch factor than for a given node of the search tree. Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular problem, as they are more computationally efficient.Finding heuristics
The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
community.
Several common techniques are used:
- Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.
- The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example, manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position independently of moving the other tiles.
- Given a set of admissible heuristic functions
, the function 
is an admissible heuristic that dominates all of them.
Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle
N-puzzle
The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle...
better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
.
Consistency and Admissibility
If a Heuristic function never over-estimates the cost reaching to goal, then it is called an Admissible heuristic function.If
is consistent then the value of for each node along a path to goal node are non decreasing.Example
One might be interested in finding a heuristic to estimate the number of steps required to solve an 8-puzzle from a given state. Two simple heuristic functions are: = the number of misplaced tiles. This is also known as the Hamming DistanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
. In the pictured example, the start state has
= 8. Clearly, is an admissible heuristic because any tile that is out of place will have to be moved at least once. = the sum of the distances of the tiles from their goal positions. Because tiles cannot be moved diagonally, the distance counted is the sum of horizontal and vertical distances. This is also known as the Manhattan DistanceTaxicab geometry
Taxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their coordinates...
. In the pictured example, the start state has
= 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18. Clearly, is also an admissible heuristic because any move can, at best, move one tile one step closer to the goal.As expected, neither heuristic overestimates the true number of moves required to solve the puzzle, which is 26. Additionally, it is easy to see from the definitions of the heuristic functions that for any given state,
will always be greater than or equal to . Thus, we can say that dominates .(example taken from Russell and Norvig)
See also
- Heuristic algorithm
- Artificial intelligenceArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
- Consistent heuristicConsistent heuristicIn computer science, a consistent heuristic function is a strategy for search that approaches the solution in an incremental way without taking any step back...
- Expert systemExpert systemIn artificial intelligence, an expert system is a computer system that emulates the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of a developer as is the case in...
- Heuristic evaluationHeuristic evaluationA heuristic evaluation is a discount usability inspection method for computer software that helps to identify usability problems in the user interface design. It specifically involves evaluators examining the interface and judging its compliance with recognized usability principles...
- Inference engineInference engineIn computer science, and specifically the branches of knowledge engineering and artificial intelligence, an inference engine is a computer program that tries to derive answers from a knowledge base. It is the "brain" that expert systems use to reason about the information in the knowledge base for...
- InquiryInquiryAn inquiry is any process that has the aim of augmenting knowledge, resolving doubt, or solving a problem. A theory of inquiry is an account of the various types of inquiry and a treatment of the ways that each type of inquiry achieves its aim.-Deduction:...
- Problem solvingProblem solvingProblem solving is a mental process and is part of the larger problem process that includes problem finding and problem shaping. Consideredthe most complex of all intellectual functions, problem solving has been defined as higher-order cognitive process that requires the modulation and control of...
- Admissible heuristicAdmissible heuristicIn computer science, specifically in algorithms related to Pathfinding, a heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal...