When the Graph Does Not Fit

Last timeConnecting Everything Cheaply

A graph too large to walk is searched by guessing which direction the destination lies in, and the guess has to satisfy one condition or the answer stops being right.

Graphs that were never written down

Everything so far assumed the graph is sitting in memory. Often it is not, and

often it could not be.

Consider the situations a sliding tile puzzle can be in, with a link between

two situations when one move separates them. That is a perfectly ordinary

graph and it has about ten thousand million million situations for the larger

puzzle. Nobody stores it. The graph is described instead by a rule: given a

situation, here are the situations one move away. The points come into

existence as the search reaches them and are forgotten afterwards.

The same is true of a route planner over a continent, a game considering

sequences of moves, a build system exploring configurations, and a model of

everything a system could do next. In all of them the points are situations

and the links are transitions, and the graph is implied by a rule rather than

held anywhere.

FIG 1Four graphs described by a rule rather than stored

	digits in the number of	links per point	stored anywhere
sliding tile puzzle	13	3	0
rubik cube	20	18	0
chess positions	44	35	0
city street map	6	4	1

The first column is the number of digits in the count of points, because the counts themselves cannot sensibly be written in a cell. The marked entry is a forty four digit number, which is not large in the sense of needing a bigger machine, it is large in the sense that no machine will ever hold it. The last row is the only one anybody stores, and even that is the exception.

Why cheapest first wastes its time

Run the cheapest first walk from a city on one coast to a city on the other,

and watch what it does. It settles points in order of distance from the start,

which means it expands a growing circle in every direction. By the time it

reaches the far coast it has settled most of the points behind it, beside it,

and in the wrong direction entirely.

It cannot do better, because nothing in it knows where the destination is.

The destination enters only as a stopping condition.

FIG 2Points examined as the destination gets further away

cheapest first, a circle in every directionguided search with a good estimate

The unguided search settles everything within the distance it has reached, which grows as the area of a circle. A well guided search settles a corridor along the route, which grows with the distance rather than with its square. At two hundred the gap is between a hundred and twenty five thousand points and sixteen hundred.

Adding a guess

The repair is to order the waiting line not by the cost so far, but by the

cost so far plus an estimate of the cost remaining to the destination.

On a map the estimate is obvious: the straight line distance. It is easy to

compute from the coordinates, it requires no search, and it is always a

sensible lower bound on how far is left to drive, since no road is shorter

than the straight line. With that one addition the search stops spreading in

all directions and pushes towards the destination, because a point in the

wrong direction has a large remaining estimate and sinks down the line.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents