A heuristic is a problem-specific rule of thumb for judging a state or possible solution. It is an educated guess, not a guarantee of what is best. Heuristics are useful when there is no clear way to find an optimal solution directly: they give a search algorithm a reason to try one option before another. section 3.1
Choosing a pizza
Suppose you like extra sauce, cheese, mushrooms, pineapple, and a thick, crunchy base. You could score pizzas by how many of those features they have. A higher score points toward a pizza you may prefer, but the rule reflects your preferences rather than a universal measure of quality. section 3.1
The rule must fit the problem. For road directions, minimizing travel time or tolls may be useful; minimizing straight-line distance alone can be misleading because roads seldom run directly to the destination. Informed search uses such problem knowledge instead of exploring blindly as breadth-first or depth-first search does. section 3.1 section 3.2
A heuristic can guide different kinds of decisions:
- In A* search, estimate the remaining cost to a goal. Add that estimate to the cost already incurred, then explore the lowest estimated total cost next using a priority queue. In a grid maze, Manhattan distance counts the horizontal and vertical steps toward the goal. section 3.3 section 3.4
- In minimax search, score simulated game states so an agent can favor moves that help it while accounting for an opponent’s replies. The scoring rule is crafted rather than learned automatically. section 3.7
- In ant colony optimization, combine a distance heuristic with pheromone strength when choosing the next unvisited destination. A probabilistic choice can still explore a less-promising immediate path. section 6.7
def determine_cost(origin, target, goal_point):
g_cost = mp.get_path_length(target) #A
move_cost = mp.get_move_cost(origin, target) #B
h_cost = abs(target.x - goal_point.x)
➥+ abs(target.y - goal_point.y) #C
return g_cost + move_cost + h_cost
The maze cost function shows the estimate in code: coordinate differences supply the Manhattan-distance heuristic, which is combined with travel costs to rank a candidate move. section 3.4
A better-informed heuristic can improve which options search explores first, but its design also affects guarantees. A*’s shortest-path guarantee requires an estimate that never exceeds the actual remaining cost; when searching a graph with loops, the estimate must also be consistent rather than dropping erratically. A useful practical question is therefore not just “Does this score seem sensible?” but “Does it measure what matters for this search?” section 3.3 section 3.1
