Four ways to Florida

I left Claude alone with this site for a couple of hours and told it to make a post. Anything. It read my bio, found the part where I rode freight trains from Oregon to Florida and back, and decided four search algorithms should make the same trip.

Finding a route is what your phone does every time you ask for directions, and the four algorithms below are the classic ways to do it. They all leave Corvallis. They all end up in Jacksonville. They don't agree on how to get there, and they do very different amounts of work to find out.

The map

The lower 48 are cut into a grid of 160 by 104 cells, each about 18 miles across, and about 9,000 of them are land. Every cell has a price for crossing it. Flat ground costs 1: the Great Plains, the Central Valley, the Willamette Valley. Mountains cost more, up to about 10 on a high ridge. Swamps cost extra. Water can't be crossed at all.

The mountain ranges have gaps where the real ones do: the Columbia River Gorge through the Cascades, Donner Pass in the Sierra, South Pass in Wyoming, Raton Pass on the way into New Mexico. West Virginia is expensive. I have my reasons.

Each algorithm moves from cell to cell, diagonals included. The faint rings spreading over each map show how far the algorithm thinks it has come. The bright dots are its frontier: cells it has found but hasn't finished with.

Breadth-first: count the moves

Breadth-first search ignores the terrain. It finds every cell one move from Corvallis, then every cell two moves away, and so on, ring by ring, until a ring touches Jacksonville. That gives you the route with the fewest moves. It doesn't give you the cheapest route, because breadth-first has no idea a mountain costs more than a wheat field.

Watch its rings. They have straight edges and don't bend for anything, because to breadth-first every cell is the same.

Dijkstra: count the cost

Edsger Dijkstra worked this one out in 1956. It grows the same way, but it measures in cost instead of moves: it always grows from the unfinished cell that's cheapest to reach from Corvallis. Its rings bend. They rush across the plains and crawl into the mountains. When a ring reaches Jacksonville, the route behind it is guaranteed to be the cheapest one there is.

The catch is that it searched in every direction to get there. Dijkstra doesn't know where Florida is.

A*: aim

A* (say "A-star") came out of the Stanford Research Institute in 1968, built for a robot called Shakey. It is Dijkstra with a sense of direction. For every cell it adds a guess of the cost still to go: what the rest of the trip would cost if it were all flat ground. That guess can never be more than the real cost, so A* still finds the cheapest route, but it spends its effort on cells that point the right way.

Greedy: only aim

Greedy best-first throws away the cost so far and keeps only the guess. It always steps toward whichever cell looks closest to the goal. It is very fast. It walks straight into mountains because they are in the way, and it never goes back to ask whether there was a cheaper way around.

The scoreboard

On the default trip, Dijkstra searches 8,382 cells, 93 percent of the land, and finds a route that costs 156. A* finds a route that costs exactly the same, 156, after searching 2,024 cells, about a quarter of the work. It isn't always quite the same line: where two routes cost the same, the two of them can pick different ones. Breadth-first pays 203, 30 percent too much. Greedy pays 198, 27 percent too much, but it only looked at 120 cells to get there.

That trade is the whole story. A* and its descendants are behind most of the route-finding you run into: game characters walking around walls, robots, map apps. Its trick is the guess. A better guess means less searching. A guess that sometimes overshoots is faster still, but then the route is no longer guaranteed to be the cheapest.

The Oregon Trail

The cheapest route doesn't head for Florida at first. It goes north through the Willamette Valley to Portland, east through the Columbia River Gorge, then south and east across the high desert to Vale and across Idaho on the Snake River Plain. It crosses the Rockies near South Pass, follows the Sweetwater and the North Platte past Casper to Scottsbluff, and only then turns southeast across Kansas, a corner of Oklahoma, Arkansas and the Deep South.

From Vale, Oregon to Scottsbluff, Nebraska, that's the Oregon Trail, ridden backwards. Nobody told the algorithm where the trail was. The wagons were looking for the cheapest way over the same mountains, and so was it. The desert stretch before Vale is roughly the Meek Cutoff of 1845, a shortcut that got a wagon train lost for weeks. The algorithm had a map.

And back

Press reverse to send them from Jacksonville back to Corvallis. Dijkstra and A* come back for exactly the same price, because a route costs the same in either direction. Breadth-first and greedy come back at a different price, because neither of them is looking at prices.

The surprise is A*. Coming back, it searches 5,394 cells, more than two and a half times as many as on the way out. Its guess prices every cell still to go as flat ground. Heading east, the mountains come first and after that the guess is close to honest. Heading west, the guess can't see the Rockies coming, so a lot of cheap ground in the east looks promising, and A* checks it.

Then click somewhere else on a map and send them there. Try West Virginia.

Build your own

The sandbox below is a smaller grid you can draw on. Walls can't be crossed. Mud costs five times as much as open ground. Drag the start and the finish around and the search redraws as you go. Pick an algorithm to watch, or press play to see it work one cell at a time.

The Trap preset is the classic way to fool greedy: a wall shaped like a cup, open toward the start. Greedy runs straight in, hits the back wall, and the route it settles for goes into the pocket and back out. Swamp is where breadth-first comes apart.

How it was built

Claude built this in one sitting while I was out, about 4,500 lines counting the tests. It says it split the work between helpers. One wrote the four searches and checked them against slower versions written separately. One drew the map from about 800 hand-placed coordinates and kept rendering it to images until the coastline looked right. Two more were told to try to break the first two, and found things to fix in both.

The mountains and the coastline are placed by hand, not taken from survey data, so don't plan a real trip with it.