admissible heuristic

A heuristicheuristic, n.: A 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. function h whose estimate h(n) is, for every state n, at most the true cost h*(n) of the cheapest path from n to a goal — possibly too optimistic, never too pessimistic. With an admissible heuristic, 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. in its tree-search form is guaranteed to return an optimal solution. The stronger property of consistency (or monotonicity) requires that h(n) ≤ c(n, n′) + h(n′) for every action from n to n′ with cost c; consistency implies admissibility and guarantees optimality in graph search without re-expanding nodes. Admissible heuristics are typically obtained by solving a relaxed problem exactly — Manhattan distance for the sliding-tile puzzle relaxes the rule that tiles cannot pass through one another — and the maximum of several admissible heuristics is itself admissible. Among admissible heuristics, larger (better-informed) ones lead A* to expand fewer nodes.