Search algorithm can use state space graph and path cost but has no other information about which non-goal nodes to prefer
Informed search
Search algorithm can also use a heuristic that estimates the cost of traveling from a non-goal node to a goal
Heuristic
A non-negative estimate of the cost of traveling from a non-goal node to a goal. Notation h(s) for state s. If a proposed score h(s) can take negative values, it is not a valid heuristic.
Path cost
Notation g(s) indicates the path cost of traveling to state s from the initial state.
Best-first greedy search
An informed search algorithm that uses only h(s) as a node’s value in the priority queue, greedily expanding the next node with the lowest estimated cost to the goal. This is not a good strategy.
A search
An informed search algorithm that uses f(s) = g(s) + h(s) as a node’s value in the priority queue.
Admissible heuristic
An optimistic heuristic, meaning the heuristic never over-estimates the true cost to the goal. Mathematically, h(s) <= h*(s), where h*(s) is the true cost from node s to the goal. The heuristic tells us there might exist a path to the goal with cost this low.
Iterative deepening A* is an informed search algorithm that only expands nodes with f(s) < a threshold. If a goal is not found, IDA* restarts with a larger threshold.
Beam search
A variation of A* search that limits the number of nodes in the priority queue. When the limit is exceeded, the node with the worst f(s) is discarded.