# Why do we use DAG rather than trees to represent search space of a search problem?

I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on the computer or can it reduce the computation time in some way?

I googled but I didn't find an answer, it would be great to have a simple explanation and a reference I can read as I would like to have a good understanding about why DAG approach is a better option.

• Are you familiar with memoization? – Yuval Filmus Mar 2 at 10:15
• @YuvalFilmus I have recently been introduced to this topic, I did not know what "memoization" is but I just read a bit on Wikipedia about it. Do you mean that the reason for using graphs is to avoid repeating calculations? – EvaMGG Mar 2 at 10:46
• Yes, the whole idea is to avoid recomputations. I suggest you to look at dynamic programming. E.g. if you want to compute $n$-th Fibonacci number $F(n)$, then computing it using recursive function takes exponential time (namely $\Theta(F(n))$. However, you can simply compute $F(k)$ only once for each $k \le n$, and then you can compute $F(n)$ in $\Theta(n)$ time. The first representation corresponds to a tree, the second one - to a DAG. – Dmitry Mar 2 at 11:04

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.