Skip to content
anythingai.space
AI Foundationsbeginner12 min · 9 steps

Search Algorithms: BFS, DFS, Heuristics and A*

How a program finds a route through a space of possibilities, and why A* finds the cheapest one without looking everywhere.

234246531Which route from S to Gis cheapest?Numbers on edges = actioncostsS · startABCDEG · goal
request
metrics are illustrative
1 / 9
ProblemStep 1 of 9

Many routes, one goal, and no map of which is best

Route planning, puzzle solving and game playing share one shape. There are states (the circles), actions that move between them (the arrows), each action has a cost, and we want to get from S to G.

Even this toy graph has several routes, with costs from 7 to 11. Real problems have millions of states, so the program needs a systematic way to explore them.

Lesson 25 of 34 in AI Foundations