Node pruning is a broad set of technique used in searching algorithms to prevent unnecessary re-computation. The core idea in these techniques is that we keep all or some of the visited states in a set, and expand a node only if its state is not in the set.
The two main approaches are:
- Path checking, which remembers visited states on a single branch.
- Cycle checking, which remembers all visited states.
Then, our core decision is whether any of the nodes we’re expanding in the frontier have been visited before in our data structure. If not, then we expand it into the frontier. If yes, then we ignore the node.
Path checking
This is best suited for use with DFS. The benefit is that it does not increase the time and space complexity, because the time complexity associated with ancestors is since our path is at most nodes. This is asymptotically dominated by the usual time complexity of DFS: . The additional space is for the current path. This is again asymptotically dominated by the usual space complexity .
However, it doesn’t prune all the nodes with redundant states. Only those among the path. So we could still revisit nodes that have already been visited.
Note that this still doesn’t make DFS complete, because we may have a branch of infinite length.
Cycle checking
This is best suited for use with BFS and UCS. It keeps track of all states previously visited during the search using a closed list. In practice, we use a hash table with time, so there’s very little additional time overhead.
This is very effective in terms of pruning nodes with redundant states. However, it’s fairly expensive in terms of space, since we may need to store all nodes in the tree, for .
UCS with cycle checking preserves its optimality, because it finds the cheapest path anyways.