Question

Has any one finished the problem set 11 in 6.00sc 2011. The last problem of ps11 requires the reader
to use dynamic programming(?) to speed up the search. I did it, but what i did seem not work so well. It can find out the solution but can't speed up the search. Does any one have a better solution for that problem?
It's my code;
http://dpaste.com/hold/1406431/
http://dpaste.com/hold/1406432/

Answer 1

I did the same/similar problem for the edX class but they did not have us optimize with dynamic programming. I did a dynamic programming problem for the 2008 OCW class but is was a knapsack problem. so I understand the graph problem and dynamic programming.
Have you profiled or timed the brute force and directedDFS functions? Results?
Can you walk me thru it?

What exactly are you memoizing - it looks like you are memoizing the shortest path found when the function is called with start, end and the two distance constraints.

did you try counting the number of misses on the memo? before you change something you should see how well the memo is working now so you can see if a change makes a difference.
http://dpaste.com/1407088/ - I added lines 172,183, 211, 214.

Why are you including visited in the key? It doesn't seem relavent, you might try removing it.

Answer 2

yah, it's a good way to debug the dynamic programming code. I get it.

After looking up problem set 11 again, i think the cause of bug is, stupid, that i didn't understand the problem 4 very well.
problem 4 requires students to optimized the brute-force method using another idea, not dynamic programming. so...
this is my new code:
http://dpaste.com/hold/1408069/
it works better now.