Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading the Wikipedia article of Dynamic programming, however, I'm having a hard time understanding the explanation given in the example for a type of balanced 0-1 matrix.

The problem is stated as:

Consider the problem of assigning values, either zero or one, to the positions of an n × n matrix, n even, so that each row and each column contains exactly n / 2 zeros and n / 2 ones.

I don't quote the whole text because I suppose there is no need to do that. However, I don't really understand the explanation after " The process of subproblem creation involves iterating..." in the third paragraph of the subsection.

Anyone can explain better that procedure? Of course, an example of this at work would be great.

Thanks

share|improve this question
    
It's going to be difficult to make an example better than the example given in Wikipedia. Have you tried looking through the code examples it links? Would the most useful thing to do be to adapt one of them to show intermediate state? –  Peter Taylor Jan 29 '11 at 21:26
    
@Peter: I'm more than satisfied with the answer given by @chandok. I think I needed to read a differently phrased explanation. Thanks for your interest, though. –  Robert Smith Jan 29 '11 at 22:05

1 Answer 1

up vote 4 down vote accepted

The dynamic programming algoritm uses a memoized recursive function that solves a more flexible subproblem :

The function takes a number k of rows to fill, and for each column, the number of 1s it has to place in those k rows. It has to return the number of possible assignments of 1s in the block of k rows such that each row contains n/2 1s, and each column contains the proper number of 1s stated in the argument.

The principle is that :

  • if a column has to contain a negative number of 1s, there is 0 solution.

  • if k=0 (and all the columns have to be empty), then there is 1 solution.

  • otherwise, an assignment of a block of k rows is an assignment of the 1st row + an assignment of a block (k-1) rows.

So it iterates over the possible assignments of the 1st row. For each candidate assignment, it recursively asks itself for the number of ways of completing the remaining (k-1) rows with the updated information about the number of 1s that have to be in each column.

If you don't memoise the function, it is exactly what the backtracking algorithm does, essentially it is n nested extremely big loops.

If you memoise the function, you will find that it is called for the same k and for the same constraints on the column a great number of times.

For example, while doing the backtracking algorithm, at some point you chose the assignment A1 for row 1 and A2 for row 2, and proceed to count every solution starting with (A1,A2) with (n-2) nested loops. Then later in the execution, you choose the assignment A2 for row 1 and A1 for row 2, and proceed to count every solution starting with (A2,A1), again with (n-2) nested loops.

But if you look carefully at the subproblem you have to solve, it has the same constraints in both case. A solution in the first case is the same as a solution in the 2nd case, only with the first two rows switched. So you are counting the same number twice.

If you memoize your recursive function, then it will recognize that these two subproblems are equivalent because they ask for the same constraints, and only compute its result once. In all the later calls it will directly return with that same result, and avoid a very expensive recomputation.

share|improve this answer
    
Wonderful explanation. Thank you very much! –  Robert Smith Jan 29 '11 at 22:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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