patternMinor
Why do we use DAG rather than trees to represent search space of a search problem?
Viewed 0 times
problemwhyspacerepresentsearchthanrathertreesusedag
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#136062, answer score: 4
Revisions (0)
No revisions yet.