Graphs & finite-state machines for problems

Why graphs are AI's universal data structure

A huge fraction of AI reduces to the same shape: you are *somewhere*, you can *move* to neighbouring situations, and you want to reach a situation with some property. That shape is a graph. A graph is a set of nodes (also called *states*) plus a set of arcs that connect pairs of nodes. An arc is an *ordered* pair $(n_i, n_j)$, so by default it is directed — you may go from $n_i$ to $n_j$ but not necessarily back. If arcs exist in both directions the connection is undirected. Getting comfortable with this vocabulary is the whole point of the lesson, because every search algorithm in the course is just a disciplined way of walking a graph.

The core vocabulary

- A path is an ordered sequence of nodes $[N_1, N_2, \dots, N_k]$ where each consecutive pair is an arc. - A path contains a cycle (loop) if any node appears more than once — the search has returned to a state it already visited. Detecting cycles is the central bookkeeping problem of search; an algorithm that ignores cycles can loop forever. - A tree is a graph with a *unique* path between every pair of nodes (so, no cycles). A rooted tree has one distinguished root with no parent; arcs point away from it and every other node has exactly one parent. A node with no children is a leaf (or *tip*). - A directed acyclic graph (DAG) is a directed graph with no cycles. DAGs matter because if a problem's moves are *irreversible* — you can only go "forward" — its state space is a DAG and you can skip cycle-checking entirely.

Degree and the Königsberg bridges

The degree of a node is how many arcs touch it. Euler used degree to settle the Königsberg bridge puzzle: a walk that crosses every arc exactly once (an Euler path) exists *only if* the graph has exactly zero or two nodes of odd degree — because an odd-degree node can serve only as the start or the end of such a walk. Königsberg's graph has four nodes, all odd degree, so no Euler path exists. This is the historical birth of graph theory and a clean example of a structural property (degree) revealing something a raw description hides.

Finite-state machines

A finite-state machine (FSM) is the same idea made into a computational model: the ordered triple $(S, I, F)$ where $S$ is a finite set of states, $I$ is a finite set of input values, and $F$ is the transition function — for each input $i \in I$, a map $F_i : S \to S$ saying which state each state moves to on that input. The states are graph nodes; the transitions are graph arcs. A finite-state acceptor adds a designated start state $s_0$ and one or more accept states: an input stream is *accepted* if processing it ends in an accept state. That start/accept distinction is exactly the start/goal distinction of state-space search — so the FSM is a concrete instance of the abstract search framework you will formalise in the next lesson.

Worked example — classify three structures

1. Tic-tac-toe played forward. States are board positions; each move places one mark and can never be undone. No move returns you to an earlier board, so the state space is a DAG — no cycle check needed.
2. The 8-puzzle. A tile slide can be *reversed* by sliding it back, so paths can cycle. This is a general directed graph, not a DAG, and search must detect repeated states.
3. A vending machine. States = amount of money inserted; inputs = coins; transitions = adding a coin's value; the accept state = exact price reached. That is a finite-state acceptor — the simplest FSM you meet daily.