Dynamic Programming Question

[tatteredpotato]

What's the best way to compute the "path" to the solution? My initial thought is to use a secondary matrix with a flag indicating the "source" to that node (like 1 = Diagonal, 2 = Vertical, 3 = Horizontal), however my initial shot at this didn't work and I'm not sure if I have a coding bug or a logic error. Is there a better/more accepted way of getting the path to the solution?

 

[uclabachelor]

What's the best way to compute the "path" to the solution? My initial thought is to use a secondary matrix with a flag indicating the "source" to that node (like 1 = Diagonal, 2 = Vertical, 3 = Horizontal), however my initial shot at this didn't work and I'm not sure if I have a coding bug or a logic error. Is there a better/more accepted way of getting the path to the solution?

More details is required if you want any useful help, but I'll suggest reading up on tree data structures. They will allow you to store the results of the computation in a fashion that can be easily traversed later.

 

[Cogman]

It depends, if you just want to store off then information, then you should see if you language supports some sort of enum construct.

 

[tatteredpotato]

More details is required if you want any useful help, but I'll suggest reading up on tree data structures. They will allow you to store the results of the computation in a fashion that can be easily traversed later.

Yea I'm familiar with all the different ADTs, however I'm not sure a tree would be helpful for dynamic programming. Once you've computed the set of all overlapping subproblems it's easy to get the answer, but you need another way to figure out how to arrive at the answer. I was working on a DTW algorithm that is similar to the minimal editing distance problem.

It depends, if you just want to store off then information, then you should see if you language supports some sort of enum construct.

For small projects I would just as soon use named constants (Java). I was more curious if my method for going about deriving the path was right. It turns out I had a bug that mixed up the data[row][col-1] and data[row-1][col] options, and gave an incorrect path.

Anyways I fixed it and it's working good now. It served as a good refresher to dynamic programming... which I'll admit I haven't touched since Algorithms class.

 

[eLiu]

I don't have anything constructive to add here, so here's a story:

When I walked in to my first recitation after dynamic programming was introduced, I sat down and we all watched the TA calmly write:

Today: HARDCORE DP

on the blackboard. It took everything in me to not burst out laughing. Some weaker minds succumbed to the lulz.

And this TA most certainly knew what he was writing on the board. Most definitely intentional.

Man... sometimes class can be hilarious. I had a prof (erik demaine; might've heard of him) shout out "BOOM HEADSHOT" after finishing a proof and reference the double rainbow meme...

 

[tatteredpotato]

I don't have anything constructive to add here, so here's a story:

When I walked in to my first recitation after dynamic programming was introduced, I sat down and we all watched the TA calmly write:

Today: HARDCORE DP

on the blackboard. It took everything in me to not burst out laughing. Some weaker minds succumbed to the lulz.

And this TA most certainly knew what he was writing on the board. Most definitely intentional.

Man... sometimes class can be hilarious. I had a prof (erik demaine; might've heard of him) shout out "BOOM HEADSHOT" after finishing a proof and reference the double rainbow meme...

Continuing on the non-constructive posts, I hadn't heard of your prof, but I thought it was funny that this was on his top 10 google hits:

http://www.boston.com/news/globe/ideas/brainiac/2007/10/erik_demaine_vs.html

 

[dealmaster00]

yooo fellow CMUer. i just had a dynamic programming problem myself. i computed a 2D array of values iteratively. Then I started at the bottom right corner, and worked my way to the upper left corner to get a specific solution. there is more than one way to solve the problem (it was the minimum edit problem) but that is the easiest and took the least amount of code while still solving it in polynomial time.

oh yeah i used a stack to store the specific solution (since i worked backwards through the solution matrix).

 

[tatteredpotato]

yooo fellow CMUer. i just had a dynamic programming problem myself. i computed a 2D array of values iteratively. Then I started at the bottom right corner, and worked my way to the upper left corner to get a specific solution. there is more than one way to solve the problem (it was the minimum edit problem) but that is the easiest and took the least amount of code while still solving it in polynomial time.

oh yeah i used a stack to store the specific solution (since i worked backwards through the solution matrix).

I ended up precomputing the entire matrix myself. Then when I chose the minimal of the 3 sources, I stored a flag in the secondary matrix to signify how I got to that cell (ie FROM_BOTTOM, FROM_LEFT, FROM_DIAG). Then I just worked backwards from the end like you, and the FROM_LEFT and FROM_BOTTOM flags were the insertions and deletions. When I hit the FROM_DIAG I just checked the main matrix to see if the source and destination were the same "cost" to determine if it was a REPLACE or MATCH.

Also I didn't think at first that there are obviously several minimal paths.

EDIT: Also a neat trick to save space is you only have to store 2 rows of the main matrix when computing the values (you would just have to identify match vs replace when you build the graph), Since you only really need 2 rows (current and previous). I didn't need to optimize space so I didn't bother doing that, but it's a cool trick nonetheless.

 

[dealmaster00]

hah nice that is pretty much exactly what i did. what class is this for? i know we aren't in the same class but it sounds exactly like the problem i had, finding the damerau–levenshtein distance. for my problem i also knew about the space optimization (just storing 2 rows since that's all you ever work with). i didnt do it either since there was absolutely no need...its not an algorithms class, hah. and yeah storing additional info in the matrix is fine too.


<<<<< 1337'th post.