A topic in the Open Knowledge Graph — a free, open map of 15,495 topics and the order to learn them in.
Many AI problems can be stated as a search problem: an initial state, a set of actions, a transition model giving the result of each action, a goal test and a cost for each action. A solution is a sequence of actions from the initial state to a goal state. Uninformed (blind) search strategies explore this state space using only the problem definition, with no estimate of how close a state is to the goal. They differ in the order in which they expand nodes, which determines whether they are complete, whether they find the cheapest solution, and how much time and memory they need.
Formulate two or three puzzles (route finding on a map, the 8-puzzle, the missionaries and cannibals problem) by writing out states, actions, transition model and goal test before any code. Run breadth-first, uniform-cost, depth-first and iterative deepening search on the same small graph and record the order of expansion. Then fill in a table of completeness, optimality, time and space in terms of branching factor b and solution depth d, as in Russell and Norvig's chapter on solving problems by searching.
A goal-based agent needs to plan a sequence of actions before acting. To let a program do that, we first formulate the problem precisely. A search problem has five parts: the initial state, the actions available in each state, a transition model saying which state each action leads to, a goal test, and an action cost function. For route finding, states are cities, actions are drives along roads, and costs are distances. Choosing what to leave out of the state, a step called abstraction, often decides whether a problem is solvable at all.
Search builds a tree of paths from the initial state. Unexpanded leaves form the frontier. Each step picks one frontier node, checks it, and expands it by generating its successors. Keeping a record of states already reached avoids exploring the same state many times. Strategies differ only in which frontier node they pick next. We judge them on four criteria. Is the strategy complete, always finding a solution if one exists? Is it cost-optimal? What are its time and space requirements? We measure these using the branching factor b, the depth d of the shallowest solution, and the maximum depth m.
Breadth-first search expands the shallowest node first, using a FIFO queue. It is complete when b is finite, and optimal when all actions cost the same. Its weakness is memory: it keeps the whole frontier, O(bd) nodes.
Uniform-cost search, which is Dijkstra's algorithm applied to search, uses a priority queue ordered by path cost g(n). It finds the cheapest solution even when costs vary, provided they are positive.
Depth-first search expands the deepest node first. It needs only O(bm) memory, but it can wander down a very long or infinite branch, so it is not complete in infinite spaces, and it does not guarantee the best solution. Depth-limited search cuts it off at a fixed depth, which prevents endless descent but misses deeper solutions.
Iterative deepening search runs depth-limited search with limits 0, 1, 2, and so on until it finds a goal. It combines the strengths of both. Like breadth-first search, it is complete and finds the shallowest solution. Like depth-first search, it needs only O(bd) memory. Repeating the upper levels costs little, because most nodes are on the bottom level. For large uninformed problems it is usually the preferred method.
All of these strategies are blind: they treat every frontier node as equally promising apart from depth or cost. Adding a heuristic, an estimate of the remaining cost, leads to informed methods such as A*.