Searching for solutions

The cheapest route: Dijkstra's algorithm

Breadth-first search, from the trees and graphs lesson, finds the route with the fewest steps. On a trail map the steps have different lengths, and the fewest steps can be the longest walk. Dijkstra's algorithm finds the route with the smallest total cost. It always grows outward from the cheapest place it hasn't finished yet, and a priority queue hands it that place each time.

Python's priority queue is the heapq module, working on a plain list. heappush adds an item and heappop always removes the smallest, whatever order things went in. Tuples compare by their first value, then their second, so pushing (cost, place) pairs makes the cheapest place come out first:

import heapq

queue = []
for item in [(7, "ford"), (2, "bridge"), (5, "falls"), (2, "alder")]:
    heapq.heappush(queue, item)
while queue:
    print(heapq.heappop(queue))

The two 2s tie on cost, so the names decide: "alder" before "bridge". Now Dijkstra. Once a place comes off the queue, its distance is final: anything reached later costs at least as much. (This map lists each trail one way, from the trailhead up, which keeps it short; a real map would list both directions.)

import heapq

trails = {   # km between junctions
    "trailhead": {"bridge": 2, "ford": 7},
    "bridge": {"falls": 3, "ridge": 9},
    "ford": {"ridge": 3},
    "falls": {"ridge": 4, "summit": 10},
    "ridge": {"summit": 3},
    "summit": {},
}

def dijkstra(graph, start, goal):
    queue = [(0, start, [start])]
    done = set()
    while queue:
        dist, place, path = heapq.heappop(queue)
        if place == goal:
            return dist, path
        if place in done:
            continue
        done.add(place)
        for nxt, km in graph[place].items():
            if nxt not in done:
                heapq.heappush(queue, (dist + km, nxt, path + [nxt]))
    return None

print(dijkstra(trails, "trailhead", "summit"))

The answer goes trailhead, bridge, falls, ridge, summit: four trails and 12 km. Every route with only three trails is longer (the best of them, through the ford, is 13 km), so the fewest steps isn't the shortest walk. Dijkstra needs one rule: no negative costs, since it assumes that walking further never makes a route cheaper.

import heapq
graph = {"A": {"B": 4, "C": 1}, "C": {"B": 2}, "B": {}}
queue, done = [(0, "A")], {}
while queue:
    d, place = heapq.heappop(queue)
    if place in done:
        continue
    done[place] = d
    for nxt, cost in graph[place].items():
        heapq.heappush(queue, (d + cost, nxt))
print(done)

A*: searching with a sense of direction

Dijkstra spreads out evenly in every direction, including away from the goal. A star, written A*, adds a guess of the remaining cost, the heuristic, and always expands the place with the lowest cost so far + guessed cost to go. On a map, the straight-line distance is a good guess; on a grid where you can only move up, down, left and right, the Manhattan distance (rows apart plus columns apart) is.

The one rule: the guess must never overestimate. A heuristic that never overestimates is admissible, and with one, A* still finds the cheapest answer, usually after expanding far fewer places (taking a place off the queue and looking at its neighbors). Here's a field with one wall in the way:

import heapq

grid = [
    "............",
    "..S.........",
    "............",
    "......#.....",
    "......#.....",
    "......#..G..",
    "......#.....",
    "............",
]
rows, cols = len(grid), len(grid[0])
start = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "S")
goal = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "G")

def search(guess):
    queue, best, expanded = [(guess(start), 0, start)], {start: 0}, 0
    while queue:
        _, cost, (r, c) = heapq.heappop(queue)
        if (r, c) == goal:
            return cost, expanded
        if cost > best[(r, c)]:
            continue           # a stale entry: this square was reached more cheaply since
        expanded += 1
        for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and cost + 1 < best.get((nr, nc), 1e9):
                best[(nr, nc)] = cost + 1
                heapq.heappush(queue, (cost + 1 + guess((nr, nc)), cost + 1, (nr, nc)))

manhattan = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
print("Dijkstra (no guess): steps, places expanded =", search(lambda p: 0))
print("A* with Manhattan:   steps, places expanded =", search(manhattan))

Both find the same 11 steps, but Dijkstra expands 79 squares and A* 36, since A* barely looks at the squares behind the start. The saving depends on the map: in a twisty maze, where the straight-line guess keeps being wrong, it shrinks. A guess of zero turns A* back into Dijkstra, and a guess that overestimates can make it settle for a worse route, because it never looks at the branch that seemed too far.

def neighbors(state):
    return []


print(neighbors((1, 2, 3, 4, 0, 5, 6, 7, 8)))

Choosing a search

The searches in this lesson and the trees and graphs lesson form a family, and choosing between them comes down to two questions: do the steps have different costs, and do you have a sense of direction?

• Breadth-first search when every step costs the same: the fewest moves in a puzzle, the fewest hops between two people in a network. It's simple and it's optimal for counting steps.
• Dijkstra's algorithm when steps have different, non-negative costs and you know nothing about where the goal is: delivery routes, the quickest train journey including transfer times, network routing.
• **A star (A*)** when you also have a cheap, honest estimate of the distance left: maps (straight-line distance), grids (Manhattan distance), puzzles (tiles out of place). It's Dijkstra that stops wasting time going the wrong way.
• Backtracking when you're not looking for a path at all but for a combination that satisfies rules: packing, timetables, puzzles like Sudoku. Its speed comes almost entirely from how early it can prune.
• Greedy choices (always take the move that looks best right now) are fast but can be wrong. With coins of 1, 3 and 4 cents, greedy pays 6 cents as 4 + 1 + 1, three coins, when 3 + 3 is two. Use greedy only when you can show the shortcut is safe.

In interviews, saying which one fits, and why, before writing any code is often worth as much as the code itself. And at work, check the library first: networkx has breadth-first search, Dijkstra and A* (nx.shortest_path, nx.astar_path), and for combination puzzles a constraint solver such as Google's OR-Tools does the backtracking and pruning for you.

def inversions(state):
    tiles = [t for t in state if t != 0]
    return sum(1 for i in range(len(tiles)) for j in range(i + 1, len(tiles)) if tiles[i] > tiles[j])

def solvable(state):
    return inversions(state) % 2 == 0

goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
swapped = (2, 1, 3, 4, 5, 6, 7, 8, 0)     # two tiles pried out and swapped
print(solvable(goal), solvable((1, 2, 3, 4, 5, 6, 0, 7, 8)), solvable(swapped))