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.
request
metrics are illustrativeProblemStep 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.
← Previous lessonKnowledge Representation: Networks, Frames, OntologiesNext lesson →Genetic Algorithms: Selection, Crossover, Mutation
Lesson 25 of 34 in AI Foundations