Programming Forums - View Single Post - Techniques For Overcoming Stack Overflow In DP

Sane · Mar 27th, 2008, 10:01 PM

How do I increase stack size?

The problem isn't duplicated states. If I were traversing duplicated states, the depth would be infinite (because the graph is cyclical). And besides, the whole point of DP is it handles these repeated subproblems implicitely.

There are 20,000 distinct states. The problem is as I traverse these distinct states, they are all reachable from each other through cross edges, so a branch of depth 20,000 immediately unfolds when DFS'd. If it were BFS'd, the depth is only about 15. I need a technique to somehow BFS the graph while DPing it through post-traversal.

Mar 27th, 2008, 10:01 PM	#4
Sane Programming Guru Join Date: Apr 2005 Posts: 1,823 Rep Power: 5	Re: Techniques For Overcoming Stack Overflow In DP How do I increase stack size? The problem isn't duplicated states. If I were traversing duplicated states, the depth would be infinite (because the graph is cyclical). And besides, the whole point of DP is it handles these repeated subproblems implicitely. There are 20,000 distinct states. The problem is as I traverse these distinct states, they are all reachable from each other through cross edges, so a branch of depth 20,000 immediately unfolds when DFS'd. If it were BFS'd, the depth is only about 15. I need a technique to somehow BFS the graph while DPing it through post-traversal. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data