3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Are you familiar with memoization? $\endgroup$ – Yuval Filmus Mar 2 at 10:15
  • $\begingroup$ @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? $\endgroup$ – EvaMGG Mar 2 at 10:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Dmitry Mar 2 at 11:04
4
$\begingroup$

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 "empty board". 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.