# A* Search and Heuristics — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/s-astar

> Use an estimate of the remaining distance.

## g plus h

**Informed** search uses a **heuristic** h(n): an estimate of the cost from state n to the goal. **A\*** expands the state with the smallest f(n) = g(n) + h(n), where g is the cost so far. If the heuristic never overestimates (it is **admissible**, like straight-line or Manhattan distance on a grid), A* still finds an optimal path, while expanding far fewer states than uninformed search. Better heuristics (closer to the true cost without overestimating) mean less work. A* and its variants power route planning, game pathfinding and robot navigation.

## A* versus uniform-cost search, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. On the same grid, both find the optimal 18-step path, but uniform-cost search (h = 0) expands 91 cells while A* with the Manhattan-distance heuristic expands 19. Ties between equal f-values are broken in favour of deeper nodes, a standard trick.

```python
import heapq
grid = ["S...........",
        "............",
        "......#.....",
        "......#.....",
        "......#.....",
        "......#.....",
        "......#.....",
        "...........G"]
R, C = len(grid), len(grid[0]); start, goal = (0, 0), (7, 11)
def nbrs(r, c):
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#": yield nr, nc
def run(h):
    frontier = [(h(start), 0, 0, start)]; best = {start: 0}; expanded = 0
    while frontier:
        f, _, g, node = heapq.heappop(frontier)
        if g > best.get(node, 1e9): continue
        expanded += 1
        if node == goal: return g, expanded
        for nb in nbrs(*node):
            if g + 1 < best.get(nb, 1e9):
                best[nb] = g + 1; heapq.heappush(frontier, (g + 1 + h(nb), -(g + 1), g + 1, nb))  # ties: prefer deeper nodes
manhattan = lambda n: abs(n[0] - goal[0]) + abs(n[1] - goal[1])
for name, h in [("uniform cost (h = 0)", lambda n: 0), ("A* with Manhattan h", manhattan)]:
    cost, expanded = run(h)
    print(f"{name:<22} path cost {cost} | nodes expanded {expanded}")
```

Output:

```
uniform cost (h = 0)   path cost 18 | nodes expanded 91
A* with Manhattan h    path cost 18 | nodes expanded 19
```

## Check admissibility

A heuristic that overestimates can make A* return a non-optimal path; derive it from a relaxed version of the problem.

**Quiz:** What does A* minimise when choosing the next state?

- [ ] The number of neighbours
- [ ] Only the cost so far
- [ ] Only the heuristic
- [x] g(n) + h(n): cost so far plus estimated cost to go

*Answer:* g(n) + h(n): cost so far plus estimated cost to go. Combining both guides the search efficiently.