{ "cells": [ { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Populating the interactive namespace from numpy and matplotlib\n" ] } ], "source": [ "%pylab inline\n", "import pandas as pd\n", "\n", "import numpy as np\n", "from __future__ import division\n", "import itertools\n", "\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "\n", "import logging\n", "logger = logging.getLogger()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "15 Dynamic Programming\n", "============\n", "\n", "for optimization problems: \n", "\n", "1. divide-and-conquer \n", " partition into **disjoint** subproblems, solve recursively, and then combine. \n", " \n", "2. dynamic programming \n", " subploems **overlap** \n", " developing by four steps: \n", " 1. Characterize the **structure** of an optimal solution. \n", " 2. **Recursively** define the value of an optimal solution. \n", " 3. Compute the value of an optimal solution, typically in a **bottom-up** fashion. \n", " 4. [opt] Construct an optimal solution from computed information.\n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 15.1 Rod cutting\n", "\n", "##### rod-cutting problem\n", "Given: \n", "1. a rod of length $n$ inches. \n", "2. a table of prices $p_i$ for $i = 1, 2, \\cdots, n$ \n", "\n", "Problem: \n", "determine the __maximum revenue__ $r_n$ obtainable by cutting up the rod and selling the pieces.\n", "\n", "Solution: \n", "$$r_n = max_{1 \\leq i \\leq n} (p_i + r_{n-i})$$\n", "\n", "Implementation: \n", "1. recursive top-down \n", "2. dynamic programming \n", " + **optimal substructure**: optimal solutions to a problem incorporate optimal solutions to related subproblems. \n", " + uses additional memory to save computation time \n", " + two ways:\n", " 1. top-down with memorization \n", " + it “remembers” what results it has computed previously. \n", " 2. bottom-up method. \n", " + We sort the subproblems by size and solve them in size order, smallest first. \n", " + The bottom-up approach often has much better constant factors, since it has less overhead for procedure calls.\n", " + **subproblems graphs**, as shown in Fig (15.4). \n", " - A dynamic-programming approach runs in **polynomial** time when **the number of distinct subproblems** involved is **polynomial** in the input size and we can solve each such subproblem in **polynomial** time. \n", " - namely, the running time of dynamic programming is **linear** in the number of vertices and edges.\n", " + **Reconstructing a solution**: \n", " We can extend the dynamic-programming approach to record not only the optimal value computed for each subproblem, but also a choice that led to the optimal value. With this information, we can readily print an optimal solution.\n", "" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "length i: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n", "price p_i: [ 1 5 8 9 10 17 17 20 24 30]\n", "max price: [1.0, 5.0, 8.0, 10.0, 13.0, 17.0, 18.0, 22.0, 25.0, 30.0]\n" ] } ], "source": [ "price = np.array([1, 5, 8, 9, 10, 17, 17, 20, 24, 30])\n", "\n", "print('length i: {}'.format(range(len(price))))\n", "print('price p_i: {}'.format(price))\n", "\n", "def bottom_up_cut_rod(p_, n):\n", " \"\"\"Solve cut_rod problem by bottom-up dynamic programming.\n", " \n", " \"\"\"\n", " assert (len(p_) >= n), 'n should be less than the max length {}'.format(len(p))\n", " \n", " p = np.insert(p_, 0, 0) #set price_0 = 0 \n", " \n", " r = np.zeros(n+1)\n", " \n", " for k in range(1, n+1):\n", " q = -np.inf\n", " for m in range(1, k+1):\n", " q = max(q, p[m]+r[k-m])\n", " r[k] = q\n", " \n", " return r[-1]\n", "\n", "\n", "print('max price: {}'.format([bottom_up_cut_rod(price, n) for n in range(1, len(price)+1)]))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "### 15.2 Martrix-chain multiplication\n", "\n", "##### matrix-chain multiplication problem\n", "**given** a chain $$ of $n$ matrices, where for $i = 1, 2, \\cdots, n$, matrix $A_i$ has dimension $p_{i-1} \\times p_i$, \n", "**problem**: fully parenthesize the product $A_1 A_2 \\cdots A_n$ in a way that minimizes the number of scalar multiplicatons.\n", "\n", "**solutions**: \n", "\n", "1. exhaustively checking all possible parenthesizations. $\\Omega(2^n)$ \n", " \\begin{equation}\n", " P(n) = \\begin{cases}\n", " 1 & \\quad \\text{if } n = 1 \\\\\n", " \\sum_{k=1}^{n-1} P(k) P(n-k) & \\quad \\text{if } n \\geq 2 \\\\\n", " \\end{cases}\n", " \\end{equation}\n", "\n", "2. Applying dynamic programming. $\\Omega (n^3)$ \n", " define $A_{i \\dotso j} = A_i A_{i+1} \\dotsm A_j$ \n", " \n", " 1. The structure of an optimal parenthesization. \n", " suppose $A_{i \\dotso k} A_{k \\dotso j}$ is the optimal solution of $$, where $i \\leq k < j$. \n", " then $A_{i \\dotso k}$ must be the optimal solution of $$, as well as $A_{k \\dots j}$.\n", " \n", " Proof: \n", " if existing $Cost(\\hat{A}_{i \\dotso k}) < Cost(A_{i \\dotso k})$, \n", " then $\\hat{A}_{i \\dotso k} A_{k \\dotso j}$ should be the optimal solution ==> contradiction. \n", " \n", " 2. A recursive solution. \n", " Let $m[i,j]$ be the minimum number of scalar multiplications needed to compute the matrix $A_{i \\dotso j}$. \n", " \n", " \\begin{equation}\n", " m[i,j] = \\begin{cases}\n", " 0 & \\quad \\text{if } i = j \\\\\n", " min_{i \\leq k < j} {m[i,k] + m[k+1,j] + p_{i-1} p_k p_j} & \\quad \\text{if } i < j\n", " \\end{cases}\n", " \\end{equation} \n", " \n", " 3. Computing the optimal costs. \n", " $m[i,j]$ depends on all $m[i,k], m[k+1,j]$. \n", " hence, the algorithm should fill in the talbe $m$ in a manner that corresponds to solving the parenthesizaiton problem on matrix chains of incresing lenghth. \n", " \n", " 4. Constructing an optimal solution. \n", " construct table $s$ whose rows is $1, \\dotsm, n-1$ and columns is $2, \\dotsm, n$. \n", " Each entry $s[i,j]$ records the optimal solution $k$ for $A_{i \\dotso j}$." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#todo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 15.3 Elements of dynamic programming\n", "\n", "Two keys: optimal substructure and overlapping subproblems.\n", "\n", "#### Optimal substructure\n", "##### common pattern\n", "1. A solution to the problem consists of making a choice.\n", "\n", "2. Suppose: for a given problem, you are given the choice \n", "\n", "3. Given the choice, you determine which subproblems ensue and how to best characterize the resulting space of subproblems.\n", "\n", "4. By using \"cut-and-paste\" technique, you show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal.\n", "\n", "To characterize the space of subproblems, a good rule of thumb says to try to keep the space **as simple as possible** and then **expand it as necessary**.\n", "\n", "\n", "Optimal substructure **varies** across problem domains in two ways:\n", "\n", "1. how many subproblems an optimal solution to the original problem use.\n", "\n", "2. how many choices we have in detering which subproblem(s) to use in an optimal solution.\n", "\n", "\n", "the **running time** of a dynamic-programming algorithm depends on the product of two factors: \n", "\n", "1. the number of subproblems overall.\n", "\n", "2. how many choices we look at for each subproblem.\n", "\n", "Dynamic programming often uses optimal substructure in a **bottom-up fashion**.\n", "\n", "The **cost** of the problem solution is usually the subproblem costs plus a cost that is directly attributable to the choice itself.\n", "\n", "\n", "##### subtleites\n", "Be careful NOT to assume that the optimal substructure applies when it does not. \n", "eg: Unweighted shortest path VS Unweighted longest simple path.\n", "\n", "subproblems are **independent**: \n", "The solution to one subproblem does not affect the solution to another subproblem of the same problem. \n", "in another word, **the subproblems do not share resources**.\n", "\n", "\n", "#### Overlapping subproblems\n", "\n", "\n", "#### Reconstructing an optimal solution\n", "store which choice we made in each subproblem in a table.\n", "\n", "#### Memoization\n", "maintains an entry in a table for the solution to each subproblem.\n", "\n", "In general practice, we prefer to use bottom-up rather than top-down memoized algorithm. While if some subproblems need not be solved at all, the memoized solution has the advantage." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 15.4 Longest common subsequence\n", "\n", "Steps:\n", "\n", "1. Characterizing the optimal substructure: \n", " Let $X = $ and $Y = $ be sequences, and let $Z = $ be any LCS of $X$ and $Y$. \n", " \n", " 1. If $x_m = y_n$, then $z_k = x_m = y_n$, and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.\n", " \n", " 2. If $X_m \\neq y_n$, then $z_k \\neq x_m$ implies that $Z$ is an LCS of $X_{m-1}$ and $Y$.\n", " \n", " 3. If $x_m \\neq y_n$, then $z_k \\neq y_n$ implies that $Z$ is an LCS of $X$ and $Y_{n-1}$.\n", " \n", "2. A recursive solution. \n", "\n", " \\begin{equation}\n", " c[i,j] = \\begin{cases}\n", " 0 \\quad & \\text{if } i = 0 \\text{ or } j = 0 \\\\\n", " c[i-1,j-1] + 1 \\quad & \\text{if } i, j > 0 \\text{ and } x_i = y_j \\\\\n", " max(c[i,j-1], c[i-1,j]) \\quad & \\text{if } i, j > 0 \\text{ and } x_i \\neq y_j\n", " \\end{cases}\n", " \\end{equation}\n", " \n", "3. Computing the length of an LCS. \n", " code.\n", " \n", "4. Constructing. \n", " $b[i,j]$ points to the table entry corresponding to the optimal subproblem solution chosen when computing $c[i,j]$.\n", " \n", " \n", "##### improving the code\n", "1. eliminate the $b$ table.\n", "\n", "2. leave only two rows of table $c$ at a time." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#todo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 15.5 Optimal binary search trees\n", "\n", "**Given**: \n", "a sequence $K = $ of $n$ distinct keys in sorted order. For each $k_i$, we have a probability $p_i$ that a serch will be for $k_i$. And we also have $n+1$ \"dummy keys\" $$ representing values not in $K$, and the probability $q_i$ for each $d_i$.\n", "\n", "$$\\sum_{i=1}^{n} p_i + \\sum_{i=0}^{n} q_i = 1 $$\n", "\n", "We want to build a search trees $T$ for $K$, and define the expected cost of a search in $T$ is: \n", "\\begin{align}\n", " E[cost] &= \\sum_{i=1}^n (depth_T(k_i) + 1) p_i + \\sum_{i=0}^n (depth_T(d_i) + 1) q_i \\\\\n", " &= 1 + \\sum_{i=1}^n depth_T(k_i) p_i + \\sum_{i=0}^n depth_T(d_i) q_i\n", "\\end{align}\n", "\n", "**Problem**: \n", "We wish the expected cost of $T$ is the smallest.\n", "\n", "\n", "#### steps\n", "1. Optimal substructure \n", " If an optimal binary search tree $T$ has a subtree $T'$ containing keys $k_i, \\dotsc, k_j$, then this subtree $T'$ must be optimal as well for the subproblem with keys $k_i, \\dotsc, k_j$ and dummy keys $d_{i-1}, \\dotsc, d_j$.\n", " \n", "2. A recursive solution \n", " \n", " define: $w[i,j] = \\sum_{l=i}^{j} p_l + \\sum_{l=i-1}^{j} q_l$\n", " \n", " \\begin{equation}\n", " e[i,j] = \\begin{cases}\n", " q_{i-1} \\quad & \\text{if } j = i - 1 \\\\\n", " min_{i \\leq r \\leq j} \\{e[i,r-1] + e[r+1,j] + w[i,j]\\} \\quad & \\text{if } i \\leq j\n", " \\end{cases}\n", " \\end{equation}\n", " \n", "3. Computing \n", " $$w[i,j] = w[i,j-1] + p_j + q_j$$" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#todo" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 0 }