A lower bound is a limit that a quantity does not asymptotically fall below. In algorithm analysis, it can describe a best-case bound; Big Omega notation expresses it. section 1.3
For linear search, finding the target first takes the fewest steps; finding it last is the worst case. A* search also uses a lower bound: an admissible heuristic estimates the remaining cost without ever overestimating it. section 1.3 section 12.1
Table 12.1 Common admissible heuristics
|
Problem Domain
|
Heuristic h(n)
|
Why it never overestimates
|
|
Road network routing
|
Euclidean Distance (Straight Line)
|
A road can only be longer than a straight line between two
points, never shorter
|
|
Grid-based movement (4 directions)
|
Manhattan Distance
|
No sequence of horizontal/vertical moves can cover the
required displacement in fewer steps
|
|
Grid-based movement (8 directions, diagonals allowed)
|
Chebyshev Distance
|
A diagonal move covers one unit of both axes at once, so
this is the true minimum move count on an open grid.
|
|
Sliding-tile puzzle
|
Sum of each tile Manhattan distance from its goal position
|
Every tile must travel at least that many rows and
columns, even if no tile were in the way.
|
Compare admissible lower-bound heuristics for road routes, grids, and sliding-tile puzzles. section 12.1

