Do Admissible Heuristics Ensure Optimal Solutions?

1. Introduction

In the realm of artificial intelligence and search algorithms, the effectiveness of problem-solving often hinges on the judicious use of heuristics. One fundamental criterion that heuristics must meet is admissibility, a property crucial for guiding algorithms toward optimal solutions.

In this tutorial, we’ll comprehensively introduce admissible heuristics and explore how they can ensure optimality.

2. What Are Admissible Heuristics?

Admissible heuristics are a concept in the field of artificial intelligence and search algorithms. A heuristic technique is used to solve problems more quickly, providing a shortcut to find approximate solutions when an exhaustive search is impractical. In the context of heuristics used in search algorithms, “admissible” refers to a specific property.

Formally, a heuristic is admissible if it never overestimates the cost to reach the goal from any given state in a search space. In other words, the estimated cost provided by an admissible heuristic is always less than or equal to the true cost. This property ensures that the heuristic guides the search algorithm in a manner that is guaranteed not to skip over the optimal solution.

In formal terms, if $h(n)$ is the heuristic value for a node $n$ , $h(n)$ is admissible if, for every node $n$ :

$h\left(n\right)\leq h^{\star}\left(n\right),$

where $h^{\star}\left(n\right)$ is the true cost of reaching the goal from node $n$ . For instance, considering the problem of finding the shortest path in a map, the straight-line distance never overestimates the actual road distance and thus can be used as $h\left(n\right)$ .

Admissible heuristics are commonly used in informed search algorithms like A* (A-star) to improve efficiency in finding solutions while ensuring that the solutions found are optimal.

3. Why Is It Called ‘Admissible’?

The term ‘admissible’ originates from the fact that the heuristic must consistently adhere to the rule of never overestimating. Any heuristic that ensures this can ‘admit’ a solution consistently, making it an ‘admissible heuristic’.

Admissible heuristics simplify complex problems by providing a feasible path to the solution while reducing computational resources and execution time. They are pivotal in fields like AI, computer games, logistics, navigation systems, etc.

4. A* Algorithm

A* algorithm is one of the best and most popular admissible heuristics used for path finding and graph traversals. The general idea of A* is to avoid expanding paths that have expensive costs.

Briefly, the operation of A* is as follows:

maintain a tree of paths starting from a start node (called the root)
extend the paths by adding one edge at each iteration
continue until the stopping criterion is satisfied

The extension of a given path is performed so that the following cost function is minimized:

$f\left(n\right)=g\left(n\right)+h\left(n\right),$

where $n$ is the current visiting node on the path, $g\left(n\right)$ is the cost of the path from the root to node $n$ , and $h\left(n\right)$ , as discussed earlier, is a heuristic function that estimates the cost of the cheapest path from $n$ to the destination.

5. Do Admissible Heuristics Ensure Optimal Solutions?

Admissible heuristics guide algorithms to explore feasible paths without getting stuck in unnecessary loops. By accurately underestimating costs, they help find optimal solutions. To understand why, let’s delve into the following proof by contradiction:

Taking A* as example heuristic, suppose that A* concludes on a path $P$ with a true cost $P_{\text{true}}$ exceeding the optimal path $P^{\star}$ with true cost $P_{\text{true}}^{\star}$ (i.e., $P_{\text{true}}>P_{\text{true}}^{\star}$ ). This implies that, before termination, the assessed cost of $P$ was either less than or equal to the assessed cost of $P^{\star}$ (otherwise, $P^{\star}$ would have been chosen). Let’s denote these assessed costs as $P_{\text{eval}}$ and $P_{\text{eval}}^{\star}$ , respectively. The situation can be succinctly expressed as follows:

$\begin{align*} & P_{\text{true}}^{\star}<P_{\text{true}},\\ & P_{\text{eval}}<P_{\text{eval}}^{\star}. \end{align*}$

If the heuristic is admissible, it implies that at the penultimate step, $P_{\text{eval}}=P_{\text{true}}$ because any increase in the true cost by the heuristic on $P$ would be inadmissible, and the heuristic cannot produce negative values. Conversely, an admissible heuristic would necessitate $P_{\text{eval}}^{\star}\leq P_{\text{true}}^{\star}$ .

When combined with the inequalities above, this implies $P_{\text{eval}}<P_{\text{true}}$ and more specifically $P_{\text{eval}}\neq P_{\text{true}}$ . Since $P_{\text{eval}}$ and $P_{\text{true}}$ cannot simultaneously be equal and unequal, our initial assumption must be false, demonstrating the impossibility of terminating on a path more costly than the optimal path.

Consider the example below with six nodes: $S$ is the start node and $D$ is the destination node. The costs at nodes are the expected remaining costs to the destination $D$ (i.e., $h\left(n\right)$ ) given by the heuristic and the costs at edges are the actual costs:

Starting from node $S$ , clearly we would visit $E$ , since the expected total cost is $f(n)=10+0=10$ . With this, the destination node $D$ would be candidate for the next node to be visited. With $D$ , the expected total cost would be $f(n)=10+20+0=30$ . This cost is higher than the cost yield by the below path ( $S$ to $A$ to $B$ to $C$ to $D$ ), with the corresponding total cost are respectively 20, 21, and 22.

Having this, we would clearly pick the below path, since it yields a lower cost $f(n)$ lower than the $f(n)$ of the above path ( $S$ to $E$ to $D$ ). So although $D$ was a candidate, we could not pick it because there were better paths with lower cost $f\left(n\right)$ . With this example, we clearly see how an admissible heuristic can ensure optimality.

6. Some Admissible Algorithms

While A* is a widely used admissible algorithm, other search algorithms also maintain admissibility. Here are some examples:

6.1. Dijkstra’s Algorithm

Introduced by computer scientist Edsger W. Dijkstra in 1956, Dijkstra’s algorithm stands as a foundational and widely employed algorithm in graph theory and network analysis. This is an admissible algorithm commonly used for finding the shortest path in a graph. It guarantees finding the shortest path but may explore more nodes than A* since it doesn’t use heuristics.

There are numerous variants of the algorithm. Dijkstra’s initial version aimed to determine the shortest path between two specified nodes. However, a more prevalent variant designates a single node as the “source” node and identifies the shortest paths from the source to all other nodes in the graph, resulting in the creation of a shortest-path tree.

6.2. Greedy Best-First Search

Greedy Best-First Search is an admissible algorithm that always selects the path that appears to be the most promising based on the heuristic evaluation. It doesn’t consider the actual cost to reach the current node. Introduced as a variant of the more comprehensive A* algorithm, Greedy Best-First Search prioritizes nodes based solely on their heuristic values, favoring those that appear most promising in reaching the goal.

This algorithm, rooted in the principles of informed search, balances computational efficiency with the simplicity of its decision-making process.

6.3. Uniform Cost Search

Uniform Cost Search is admissible and explores the node with the lowest cumulative cost from the start node. It is similar to Dijkstra’s algorithm but may be more efficient in certain scenarios. The fundamental principle of Uniform Cost Search is to always select the node with the lowest cumulative cost from the start node.

The algorithm maintains a priority queue, where nodes are ordered based on path cost. Each iteration expands the node with the lowest cumulative cost, and the search progresses until the goal node is reached.

6.4. IDA* (Iterative-Deepening A*)

Introduced by Richard Korf in 1985, IDA* is an admissible algorithm that combines ideas from depth-first search and A*. It performs an iterative depth-first search, gradually increasing the depth limit until the goal is found. It is designed to find the optimal path in a state space while mitigating the memory constraints associated with traditional A* search. It combines the principles of depth-first search and A* by repeatedly conducting depth-limited searches, incrementing the depth limit in each iteration until the goal is found.

As a depth-first search algorithm, IDA* consumes less memory compared to A*. However, unlike traditional iterative deepening search, this algorithm prioritizes the exploration of highly promising nodes, avoiding uniform depth traversal across the entire search tree. In contrast to A*, IDA* doesn’t employ dynamic programming, leading to repeated exploration of certain nodes.

6.5. IDA-Epsilon

Iterative-Deepening A* with Epsilon (IDA-Epsilon) represents an evolution of the classic Iterative-Deepening A* (IDA*) algorithm, incorporating flexibility in its search for solutions within heuristic search spaces. IDA-Epsilon is designed to balance optimality and computational efficiency by introducing an “epsilon” parameter, allowing the algorithm to accept suboptimal solutions based on a user-defined tolerance.

A variant of IDA* that allows for suboptimal solutions by introducing an epsilon value. This epsilon controls the degree to which the algorithm can deviate from the optimal path. This algorithm finds applications in scenarios where finding an optimal solution is resource-intensive and a slightly suboptimal solution is deemed acceptable.

6.6. Sequential A (SEA*)

SEA* is an admissible algorithm that handles changing costs dynamically. It adapts to modifications in edge costs during the search process. This algorithm falls within the family of heuristic search methods and addresses dynamic environments where the costs of actions or edges in the search graph may change over time.

Introduced as a modification of the A* algorithm, SEA* adapts to such changes by incorporating sequential optimization steps during the search process.

6.7. Bidirectional Search

Bidirectional search is a search algorithm that simultaneously explores the search space from both the initial state (start node) and the goal state (target node) in an attempt to find a common intersection point. By employing two search processes that converge towards each other, bidirectional search seeks to reduce the overall search space and potentially achieve significant computational savings compared to unidirectional approaches. Admissible versions of bidirectional search ensure that the search remains within bounds.

7. Conclusion

Admissible heuristics play a pivotal role in enhancing the efficiency of various algorithms, particularly in domains such as artificial intelligence, computer games, logistics, and navigation systems.

In article, we provided a comprehensive introduction to admissible heuristics, a brief summary of how the well-known admissible heuristic A* works, and discovered some admissible algorithms such as Dijkstra’s algorithm, Uniform Cost Search, or Bidirectional Search.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex