The map of all paths within a state-space is a graph of nodes which are connected by links. Now if we trace out all possible paths through the graph, and terminate paths before they return to nodes already visited on that path, we produce a search tree. Like graphs, trees have nodes, but they are linked by branches. The start node is called the root and nodes at the other ends are leaves. Nodes have generations of descendents. The first generation are children. These children have a single parent node, and the list of nodes back to the root is their ancestry. A node and its descendents form a subtree of the node's parent. If a node's subtrees are unexplored or only partially explored, the node is open, otherwise it is closed. If all nodes have the same number of children, this number is the branching factor.
The aim of search is not to produce complete physical trees in memory, but rather explore as little of the virtual tree looking for root-goal paths.
Which node to expand?
Checking for optimum: branch and bound, dynamic programming
Comparisons need for: