Why do we use DAG rather than trees to represent search space of a search problem?
A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm trying to solve the eight queens puzzle. The search is initiated with an empty board. On any given position, the search algorithm attempts to place one more queen, in all possible ways. The search halts when a solution is reached.
We can describe the working of the algorithm as a tree. The root is &quot;empty board&quot;. An internal node corresponds to a position with several non-attacking queens, and its children are positions with one more queen added. Leaves are solutions to the puzzle.
Consider a node at depth 2, consisting of queens at positions $x$ and $y$. This position can be reached in two ways: adding $x$ then $y$, or adding $y$ then $x$. This means that there are actually two identical subtrees at depth 2 describing the same board position. The second time we reach this position, there is no need to explore it any more. This can be implemented using memoization, a technique in which we remember that we have already explored this position, and now what the outcome is (memoization can be used more generally to compute functions). This corresponds to folding the search tree into a DAG by identifying nodes corresponding to identical positions.
Memoization is closely related to dynamic programming, which is one way to implement memoization. Roughly speaking, dynamic programming is a way of scanning the DAG in reverse topological order, so that whenever we get to an internal node, all of its children have already been explored.