Algorithm Optimization With Dynamic Programming
May 17th, 2019 - written by Kimserey with .
Dynamic programming (DP), is an algorithm design technique used to turn exponential complexity problems into polynomial complexity problems. Described as careful brute force (Erik Demaine - MIT course 6.006), problems are deconstructed into overlaping subproblems, solved indepedently with brute force, subproblems solutions are then cached and reused. The reusability aspect being a major contributor to the optimization due to the overlapping nature of the subproblems. Today we look at what DP is by defining the different steps used in the technique and applying those on a concrete example.
Dynamic Programming
Dynamic programming can be decomposed in five steps:
- Defining subproblems,
- Guessin the possible solutions,
- Relating subproblems solutions,
- Recursing and memoizing,
- Solving the original problem.
We start by looking at the given problem and figure out smaller subproblems (1). We then guess the possible solutions, but instead of guessing a single solution like what a greedy algorithm would do, we guess all possible outcomes (2). Once we have guessed all possible outcomes of subproblems, we relate all solutions and pick the best outcome out of the subproblems solutions (3). We then recurse to apply the subproblem guessing algorithm to higher problems (4) while memoizing the results of subproblems to reuse them for overlapping subproblems. Lastly having the solutions for all subproblems, we solve the overall problem (5).
Memoization and Iteration
Memoization is the concept of caching already calculated computations results and when the same input are provided, return the cached result. For example if the operation complexity is O(n), and we call it n time, the resulting complexity would be O(n^2), but with memoization, the computation would run only one time and subsequent calls will be of constant time therefore the overal complexity remains O(n). Memoization is like remembering results by writing them on a memopad.
Fibonacci is a typical example where memoization can be appreciated. In our previous post, we explored the different ways to compute Fibonacci numbers using recursion. The most understandable and friendly to read was the simple recursion demonstrated as followed:
1
2
3
4
fib(n):
if n == 0: 0
if n == 1: 1
else: fib(n - 1) + fib(n - 2)
Fibonacci is straight forward to solve and the recursion algorithm is easily identifiable. Subproblems can be identified as each Fibonacci numbers and computing a higher number can be done by computing smaller numbers and combining results.
The memoization step can be accomplished with a simple change reducing the algorithm to a linear complexity.
1
2
3
4
5
6
7
8
9
10
fib(n):
memo={}
loop(x):
if x == 0: 0
if x == 1: 1
else:
if !memo[x]:
memo[x] = loop(x - 1) + loop(x - 2)
memo[x]
loop(n)
We define an inner loop allowing the introduction of a memo used to cache the result of the Fibonacci number already computed. This enhancement reduces the complexity by enforcing that each Fibonacci number is only computed once and reused for computation of other Fibonacci numbers.
Memoization is described as a top to bottom approach, where we memoize larger subproblems and expand while memoizing deeper subproblems. With our example, we computed Fibonacci in a recursion starting from n and decreasing until 1 or 0, hence top to bottom.
Another method described as bottom up approach is the iterative approach, also called tabulation. Continuing on our example of Fibonacci, we can achieve an iterative approach by computing numbers from 0 till n.
1
2
3
4
5
6
7
fib(n):
memo={ [0]: 0, [1]: 1 }
if n < 2: memo[n]
else:
for x in 2..n:
memo[x] = memo[x - 1] + memo[x - 2]
memo[n]
We no longer have recursion but instead we build the memo as a table containing results of subproblems iteratively.
Optimal Binary Search Trees
Consider the problem of finding the minimal possible cost from a binary search tree composed of a given set of weighted nodes. We compute the cost of the binary tree by summing all weights multiply by their depths in the tree.
\[cost = \sum weight * (depth + 1)\]To minimize the cost, we minimize the weigth * depth multiplication. We want nodes of high weights to be low in depth, closer to the root. And we want nodes light in weights to be deeper in the tree.
For a set $S$ of nodes $s1$, $s2$, $s3$ to simplify the example, we assume that nodes weigh the same as their index, s1 weighs one, s2 weighs two, and s3 weighs three.
For $S$, we have in total five possible tree combinations:
1
2
3
s1
s2
s3
- Selecting $s1$, then $s2$, then $s3$, with a cost of
1 + (2 * 2) + (3 * 3) = 14.
1
2
3
s1
s3
s2
- Selecting $s1$, then $s3$, then $s2$, with a cost of
1 + (3 * 2) + (2 * 3) = 13.
1
2
s2
s1 s3
- Selecting $s2$, then $s1$, then $s3$, with a cost of
(2 * 1) + (1 * 2) + (3 * 2) = 10.
1
2
3
s3
s1
s2
- Selecting $s3$, then $s1$, then $s2$, with a cost of
(3 * 1) + (1 * 2) + (2 * 3) = 11.
1
2
3
s3
s2
s1
- Selecting $s3$, then $s2$, then $s1$, with a cost of
(3 * 1) + (2 * 2) + (1 * 3) = 10.
The lowest cost here is 10 from the combinations $s2-s1-s3$ and $s3-s2-s1$.
We used brute force to find all possible combinations, choosing one by one every nodes as root while reduced all results to the minimum cost.
1
2
3
4
cost(i, j)
if i = j: xs[i]
else:
min (for all r in i < r, r < j) (cost(i, r-1) + cost(r+1, j)) + Sum weights(i to j)
As we choose a root $r$, we partition the sequence into two sequences, respectively containing all elements before $r$ and all elements after $r$. Each partition yields a binary search tree $K$, which cost function can be computed. Therefore we try all possible $r$ and keep the $r$ yielding the lowest cost from $K_{(i, r-1)}$ and $K_{(r+1, j)}$.
1
2
r
K(i, r-1) K(r+1, j)
At each recursion, we add all the weights from $(i, j)$ which then constructs the depth multiplier. We can see that the first execution of cost will try all r from 1 to n which will yield many overlaping subtrees where memoization will reduce those computation to constant time.
1
2
3
4
5
6
cost(i, j)
if memo[i,j]: memo[i,j]
if i = j: xs[i]
else:
memo[i,j] = min (for all r in i < r, r < j) (cost(i, r-1) + cost(r+1, j)) + Sum weights(i to j)
memo[i,j]
In this example we have applied the principales of dynamic programming. We have broken down a problem to a subset of problems. And for each recursion we tried every possibilities and save the best solution, while memoizing and reusing previous results - careful brute force. The heart of the problem lying in the recursion, we crafted a function which was able to solve the subproblems at their own levels and solve a problem which did not have any obvious solution.
And that concludes today post!
Conclusion
Today we saw a powerful algorithm technique called Dynamic programming. We looked into the main aspects of it and how it could be used to find solution for problems with no obvious solutions. We also saw optimization techniques used in Dynamic programming like memoization and tabulation which can be used in different context to reduce complexity of algorithms. Finally we looked into the example of finding the minimal possible cost of a binary tree given a set of weighted nodes where we demonstrated all steps of Dynamic programming. I hope you liked this post and I see you on the next one!