A heuristic is a rule of thumb that steers a search toward an acceptable solution in practical time. It can be much faster than brute force, but it does not guarantee feasibility or optimality. The useful question is not just “Is this rule fast?” but “What does it favor, and what might it miss?” section 2.3
Packing by a simple rule
Suppose five rectangular objects must fit in a container. A largest-first rule sorts them by area before placement; in the illustrated run, one object is excluded. A smallest-width-first rule sorts by width and then area; in its run, all five fit. Neither result proves that one ordering always wins. It shows why a quick rule should be tested against the constraints and examples that matter. section 2.3
Figure 2.19 Bin packing using the largest-first heuristic—one object has been excluded, as it does not fit in the remaining space.
The largest-first packing result makes the cost of an unfortunate ordering visible: one object no longer fits. section 2.3
In informed search, a heuristic can estimate how promising a state is. The number of misplaced tiles can estimate progress in an 8-puzzle. For routing, A* ranks a node using f(n) = g(n) + h(n): the cost already incurred plus an estimate of the remaining cost. Straight-line distance is one possible estimate. If h(n) is zero everywhere, A* behaves like uniform-cost search; weighting h(n) more heavily changes its influence on which node is explored next. section 4.1 section 4.3.3
Choose and check a heuristic in three steps:
- Identify what the rule measures: area or width for packing, estimated distance for routing, or inverse edge length for an ant-colony path choice. section 2.3 section 10.3.1
- Apply it to decide what to place or explore next. In ant colony optimization, edge desirability and pheromone concentration jointly influence a probabilistic move. section 10.3.1
- Inspect the result for excluded items, unmet constraints, or a poor route. In A*, also examine whether the remaining-cost estimate overestimates the true cost when admissibility matters. section 2.3 section 4.3.3
A metaheuristic operates at a higher level: it guides or modifies heuristics to explore the search space more effectively, balancing exploration of new regions with exploitation of promising ones. That distinction matters when a single fixed rule repeatedly settles for poor solutions. section 2.3
