Heuristic Function in AI: Types, Properties, and Examples

What Is a Heuristic Function in AI?

A heuristic function in AI is a function, usually written h(n), that estimates the cost of the cheapest path from a state n to the goal. It doesn't calculate the exact cost, which would often take as long as solving the problem itself. Instead, it gives a quick, educated guess that a search algorithm can use to decide which state to explore next.

The number a heuristic function returns for a particular state is called its heuristic value. A lower value means the state looks closer to the goal, and the heuristic value of the goal state itself is always 0. For example, if you're driving to another city, the straight-line distance from your current location to the destination is a heuristic: it's easy to calculate, and it tells you roughly how far you still have to go, even though the real road distance will be longer.

Heuristics trade some certainty for speed. A search that uses a heuristic may still find the best answer, depending on the heuristic's properties, but it reaches that answer by examining far fewer options.

Gain Expertise In Artificial IntelligenceWith the Microsoft AI Engineer ProgramSign Up Today

How Does a Heuristic Function Work?

Most AI search problems are framed as a state space: a set of states (such as puzzle positions or map locations), actions that move between states, a start state, and a goal state. A search algorithm explores this space by repeatedly choosing a state from its list of candidates, called the frontier, and expanding it to generate the next states.

The heuristic function in AI search decides which state to expand next. Each time the algorithm needs to choose, it calculates the heuristic value of every candidate and picks the one that looks closest to the goal. Search algorithms differ in how they combine the heuristic with the cost already traveled:

• Greedy best-first search ranks states by h(n) alone, the estimated cost to the goal.
• A* search ranks states by f(n) = g(n) + h(n), where g(n) is the actual cost from the start to n.

In both cases, the heuristic steers the search toward the goal instead of letting it spread out evenly in every direction.

Heuristic Search vs Uninformed Search in AI

Search algorithms fall into two broad groups, and the difference between them is whether they use a heuristic.

Uninformed search, also called blind search or brute-force search, uses no information about where the goal is. It only knows how to generate the next states and how to recognize the goal when it reaches it. Breadth-First Search (BFS) explores level by level using a queue, while Depth-First Search (DFS) follows one path as deep as possible using a stack, a last-in, first-out data structure. Uniform cost search and bidirectional search are also uninformed.

Heuristic search, also called informed search, uses a heuristic function to estimate how close each state is to the goal, and explores the most promising states first.

Types of Heuristic Search Algorithms in AI

These are the main heuristic search algorithms, all of which use a heuristic function in different ways.

Greedy Best-First Search

Greedy best-first search always expands the state with the lowest heuristic value, so f(n) = h(n). It heads straight for whatever looks closest to the goal, which often makes it very fast. Because it ignores the cost already traveled, though, it can be lured down a path that looks good early but turns out to be expensive. 

A* Search

A* search expands the state with the lowest f(n) = g(n) + h(n):

• g(n) is the actual cost of the path from the start to n.
• h(n) is the estimated cost from n to the goal.
• f(n) is the estimated total cost of the cheapest solution that passes through n.

By balancing the cost so far against the estimated cost remaining, A* finds the cheapest path as long as its heuristic never overestimates. That's why A* is the standard choice for pathfinding in games, maps, and robotics.

Here's the difference on a small road map. Going from S to G, you can travel through A (1 km, then 10 km) or through B (4 km, then 3 km). The heuristic is the straight-line distance to G, which is 3 km from S, 2 km from A, and 3 km from B.

import heapq

# Road map: edge costs are travel distances in km
graph = {
    "S": {"A": 1, "B": 4},
    "A": {"G": 10},
    "B": {"G": 3},
    "G": {},
}
# Heuristic: straight-line distance to the goal G (never more than the real road distance)
h = {"S": 3, "A": 2, "B": 3, "G": 0}

def best_first(start, goal, use_g):
    """use_g=False gives greedy best-first search (f = h); True gives A* (f = g + h)."""
    frontier = [(h[start], 0, start, [start])]
    visited = set()
    while frontier:
        f, g, node, path = heapq.heappop(frontier)
        if node == goal:
            return path, g
        if node in visited:
            continue
        visited.add(node)
        for nxt, cost in graph[node].items():
            new_g = g + cost
            new_f = new_g + h[nxt] if use_g else h[nxt]
            heapq.heappush(frontier, (new_f, new_g, nxt, path + [nxt]))

for name, use_g in [("Greedy best-first", False), ("A*", True)]:
    path, cost = best_first("S", "G", use_g)
    print(f"{name}: path {' -> '.join(path)}, cost {cost} km")

Output:

Greedy best-first: path S -> A -> G, cost 11 km
A*: path S -> B -> G, cost 7 km

Greedy search picks A because its heuristic value (2) is lower than B's (3), and it ends up on an 11 km route. A* sees that f(A) = 1 + 2 = 3 is lowest at first, but once it reaches G through A with a total of 11, B's f-value of 4 + 3 = 7 is lower. So A* explores B and finds the 7 km route.

Hill Climbing and Other Local Search

Hill climbing algorithms start from a particular state and explore its neighbors, searching for a state with a higher heuristic value. The process stops when no neighbors are better. They consume little memory but are prone to getting stuck in local maxima, that is, a state that is better than its neighbors but worse than other states nearby. Various approaches, such as simulated annealing, local beam search, and tabu search, can improve hill climbing performance and overcome local maxima. Local search algorithms are typically applied to optimization problems such as scheduling and constraint satisfaction problems. They focus on finding the best possible state rather than the path taken.

Types of Heuristic Functions in AI

The right heuristic depends on the problem. These are the most widely used types of heuristic functions in AI:

Manhattan distance is the most common choice for grid-based pathfinding, and straight-line distance is the standard heuristic for route planning on real maps.

Advance Your AI Engineering CareerWith Microsoft's Latest AI ProgramSign Up Today

How to Calculate a Heuristic Function: 8-Puzzle Example

The 8-puzzle is a classic example for explaining how to calculate a heuristic function in AI. It's a 3 × 3 board with eight numbered tiles and one blank space. You slide tiles into the blank until the board matches the goal. Here's a start state and the goal:

Start state        Goal state
7 2 4              1 2 3
5 _ 6              4 5 6
8 3 1              7 8 _

Let's calculate two common heuristics for the start state.

h1, misplaced tiles: count the tiles that aren't in their goal position. Tiles 2 and 6 are already in place, and the other six aren't, so h1 = 6.

h2, Manhattan distance: for each tile, count how many rows and columns it is from its goal position, then add these distances together.

So h2 = 14. The blank isn't counted because it isn't a tile. The best solution takes 20 moves, so both heuristics underestimate the real cost, and h2 is a much closer estimate than h1.

Build Expertise With 15+ Modern AI ML ToolsWith the AI and Machine Learning CourseEXPLORE PROGRAM

Properties of Heuristic Functions in AI

AI can judge every heuristic function by a few properties. These properties determine whether the search that uses it is guaranteed to find the best solution and how much work it does.

Admissible Heuristic

A heuristic is admissible if it never overestimates the true cost of reaching the goal. In other words, h(n) ≤ h*(n) for every state n, where h*(n) is the actual cheapest cost. An admissible heuristic is optimistic: it may guess low, but never high.

Admissibility is the property that makes A* optimal. If h(n) never overestimates, A* is guaranteed to find the cheapest path. Straight-line distance is admissible for road travel because no road is shorter than a straight line, and both 8-puzzle heuristics above are admissible because every misplaced tile needs at least one move and every tile needs at least its Manhattan distance in moves.

Consistent (Monotonic) Heuristic

A heuristic is consistent if, for every state n and every next state n′ reached by an action with cost c(n, n′):

h(n) ≤ c(n, n′) + h(n′)

This is a form of the triangle inequality. It states that the estimate never exceeds the true distance by more than the cost of the step just taken. Every consistent heuristic is also admissible, and using a consistent heuristic means that the f-values are non-decreasing along any path, so A* never revisits a state once it has been expanded. Manhattan distance and the number of misplaced tiles are both consistent heuristics for the 8-puzzle.

Dominance

If h1 and h2 are both admissible, and h2(n) ≥ h1(n) for all nodes n, then h2 is said to dominate h1. A dominant heuristic is better informed, and A using h2 will expand no more nodes than A using h1 (except for ties). This is because any node A would have expanded using h1 will also be expanded using h2, but A using h2 may also expand additional nodes because of the higher estimate. In the 8-puzzle, Manhattan distance dominates misplaced tiles, since every misplaced tile is at least one move away from its goal position.

Using a dominant heuristic can have a dramatic effect. On a harder 8-puzzle that requires 31 moves to solve, A with misplaced tiles expanded 143,849 states, while A with Manhattan distance expanded 21,198, about 7 times fewer. Both algorithms found the same 31-move solution.

Completeness and Optimality

These two properties belong to the search algorithm rather than the heuristic. A search algorithm is complete if it's guaranteed to find a solution whenever one exists, and optimal if it finds the cheapest solution. A* is complete and optimal on finite graphs with positive step costs when its heuristic is admissible. Greedy best-first search doesn't guarantee the cheapest solution, and in an infinite state space it may not find a solution at all.

Build real-world AI and Machine Learning skills with our Microsoft AI Engineer Course. Designed to match current industry needs, it helps you learn practical concepts and apply them with confidence. Start your journey today and take a clear step toward a future-ready career.

How to Design a Good Heuristic Function

Unlike ML (machine learning) models, which learn patterns from data, most heuristics are designed by hand from knowledge of the problem. A few reliable techniques help:

• Relax the problem by removing one or more rules, and use the cost of solving the easier problem as your heuristic. If tiles in the 8-puzzle could move to any square in one move, the number of moves needed would equal the number of misplaced tiles. If tiles could slide onto occupied squares, it would equal the Manhattan distance. Because a relaxed problem has fewer constraints, its solution cost never exceeds the real one, so the resulting heuristic is admissible.
• If you have several admissible heuristics, combine them with max(): h(n) = max(h1(n), h2(n), ...) is also admissible and dominates each of them.
• Pattern databases store the exact solution cost for a subset of the pieces, such as four tiles of a sliding puzzle, and use that as the heuristic value.
• Balance accuracy against cost. A more accurate heuristic reduces the number of states searched, but if it takes too long to compute, the total time can still increase.

Heuristic Function in Python: A* on the 8-Puzzle

This program shows a heuristic function in action. It solves the 8-puzzle above with A*, first with no heuristic, then with misplaced tiles, and then with Manhattan distance. It reports the length of the solution and how many states each version expands.

import heapq

GOAL = (1, 2, 3,
        4, 5, 6,
        7, 8, 0)          # 0 is the blank

def misplaced_tiles(state):
    """h1: number of tiles not in their goal position."""
    return sum(1 for i, tile in enumerate(state) if tile and tile != GOAL[i])

def manhattan(state):
    """h2: total grid distance of every tile from its goal position."""
    total = 0
    for i, tile in enumerate(state):
        if tile:
            goal_i = GOAL.index(tile)
            total += abs(i // 3 - goal_i // 3) + abs(i % 3 - goal_i % 3)
    return total

def neighbors(state):
    blank = state.index(0)
    row, col = divmod(blank, 3)
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        r, c = row + dr, col + dc
        if 0 <= r < 3 and 0 <= c < 3:
            swap = r * 3 + c
            board = list(state)
            board[blank], board[swap] = board[swap], board[blank]
            yield tuple(board)

def a_star(start, h):
    """Returns (moves in the optimal solution, nodes expanded)."""
    frontier = [(h(start), 0, start)]      # entries are (f, g, state)
    best_g = {start: 0}
    expanded = 0
    while frontier:
        f, g, state = heapq.heappop(frontier)
        if g > best_g[state]:
            continue                        # stale entry
        expanded += 1
        if state == GOAL:
            return g, expanded
        for nxt in neighbors(state):
            new_g = g + 1                   # every move costs 1
            if new_g < best_g.get(nxt, float("inf")):
                best_g[nxt] = new_g
                heapq.heappush(frontier, (new_g + h(nxt), new_g, nxt))

start = (7, 2, 4,
         5, 0, 6,
         8, 3, 1)

print("h1 (misplaced tiles):", misplaced_tiles(start))
print("h2 (Manhattan distance):", manhattan(start))
for name, h in [("No heuristic, h = 0", lambda s: 0),
                ("Misplaced tiles", misplaced_tiles),
                ("Manhattan distance", manhattan)]:
    moves, expanded = a_star(start, h)
    print(f"{name}: {moves} moves, {expanded:,} nodes expanded")

Output:

h1 (misplaced tiles): 6
h2 (Manhattan distance): 14
No heuristic, h = 0: 20 moves, 48,390 nodes expanded
Misplaced tiles: 20 moves, 3,667 nodes expanded
Manhattan distance: 20 moves, 283 nodes expanded

All three versions find the same 20-move solution because all three heuristics are admissible. The difference is how much work they do. Without a heuristic, A* expands 48,390 states. Misplaced tiles cut that to 3,667, and Manhattan distance cuts it to 283, more than 99% fewer than the search without a heuristic.

Real-World Examples of Heuristic Functions in AI

• Navigation and GPS systems use straight-line distance, or travel-time estimates, to guide A* and related algorithms through road networks with millions of junctions.
• In video games, characters find their way around game maps using A* with Manhattan, Chebyshev, or Euclidean distance, depending on how they can move.
• Robots and drones plan paths around obstacles by combining A* with distance heuristics on grid or graph maps of their surroundings.
• Chess and other board game engines use evaluation functions, a kind of heuristic that scores how good a position is, to decide which moves to explore further.
• For the traveling salesperson problem (TSP), the nearest-neighbor heuristic builds a tour by always visiting the closest unvisited city next. That reduces the work from checking all O(n!) possible tours to O(n²) steps. The trade-off is quality: in tests on random 9-city problems, nearest-neighbor tours averaged about 10% longer than the best tour and were sometimes 28% longer.

Designing and tuning heuristics like these is part of an AI engineer's everyday work.

AI Engineer has been ranked as the fastest-growing role as companies move from experimenting with AI to deploying it at scale. Explore the AI Engineer roadmap that covers everything from foundational skills to senior-level responsibilities in one place.

Advantages and Limitations of Heuristic Functions

Advantages

• They dramatically reduce the number of states a search explores, often by several orders of magnitude.
• They make large problems, such as route planning on real road networks, practical to solve.
• With an admissible heuristic, A* still guarantees the optimal solution while running much faster than uninformed search.
• They let you build expert knowledge about a problem directly into general-purpose algorithms.

Limitations

• A good heuristic requires domain knowledge, and designing one for a new problem can be difficult.
• An overestimating heuristic can lead A* to a solution that isn't the cheapest.
• Greedy search and hill climbing can get stuck on poor paths or local optima, even with a reasonable heuristic.
• A very accurate heuristic can be expensive to calculate, which can cancel out the time it saves.
• A* still keeps every generated state in memory, so even with a good heuristic, it can run out of memory on very large problems.

Key Takeaways

• A heuristic function in AI, h(n), estimates the cost from a state to the goal, and the goal's heuristic value is always 0.
• Uninformed searches such as BFS and DFS use no heuristic, while informed searches such as greedy best-first search and A* use one to explore the most promising states first.
• A* ranks states by f(n) = g(n) + h(n) and is guaranteed to find the cheapest path when its heuristic is admissible, meaning it never overestimates.
• A consistent heuristic satisfies h(n) ≤ c(n, n′) + h(n′), is always admissible, and lets A* avoid revisiting states.
• Better-informed heuristics, such as Manhattan distance over misplaced tiles, can cut search work by orders of magnitude.

Conclusion

Heuristic functions are what turn search from brute force into something practical. A well-chosen heuristic lets an algorithm ignore most of the options it would otherwise check, and when it's admissible, it gains speed without sacrificing optimality. Understanding admissibility, consistency, and dominance gives you the tools to judge any heuristic and to design your own.

With the Professional Certificate in AI and Machine Learning, you can become an expert in the field. The program covers the most recent AI techniques and tools.

You can also explore Simplilearn's AI ML courses to deepen your knowledge of AI algorithms, intelligent systems, and real-world applications. These learning opportunities can help you strengthen your technical skills and apply AI concepts to complex problems.

FAQs

1. Is h(n) = 0 a valid heuristic?

Yes. A heuristic that always returns 0 never overestimates; hence, it is admissible and even consistent. However, it gives the search algorithm no information. Thus, A with h(n) = 0 behaves exactly like uniform cost search (Dijkstra's algorithm) and explores many more states than is necessary.

2. Can a heuristic value be negative?

Path costs are never negative, so we must not estimate a negative value for the remaining distance to be traveled. A negative estimated distance would still be admissible, but it is worse than 0 and never useful.

3. What happens if a heuristic overestimates the cost?

The heuristic is no longer admissible, and A is no longer guaranteed to find the shortest path (but will still often find a solution faster). In one 8-puzzle test, multiplying the Manhattan distance by 3 reduced the number of states expanded from 21,198 to 663. But the solution length increased from the optimal 31 moves to 39. Some applications (games) intentionally accept this trade-off, using what is known as weighted A*.

4. What is the difference between a heuristic function and a cost function?

A cost function, g(n), is the actual cost spent to reach state n from the initial state. A heuristic function, h(n), estimates the remaining cost from n to the goal. A* adds these two together (f(n) = g(n)+h(n)).

5. Does a heuristic always search faster?

Not necessarily. A heuristic reduces the number of states the search algorithm explores, but calculating it can take time. If the heuristic is expensive to calculate and only a little better than another heuristic, the algorithm can run slower overall. Poor heuristics can also cause the greedy search to explore more states than an uninformed search.