Shortest Path Problems
	• Common in real-life problems – e.g. select routes for planes to minimise fuel use • With  “planning and puzzles” we saw that – “finding a plan” or “solving a puzzle” – becomes “find a path” • But the relevant graphs are now – implicit – nodes and edges are only given by rules – exponentially larger than occurs with explicit maps – 15-puzzle has 16!/2 states (approx 1013)