{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%matplotlib 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": [ "16 Greedy Algorithms\n", "===========\n", "\n", "**intent**: it makes a locally optimal choice in the hope that the choice will lead to a globally optimal solution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 16.1 An activity-selection problem\n", "\n", "**Given**: \n", "an activity $a_i$ has a start and finish time $[s_i, f_i)$. \n", "activities set $S = \\{a_1, a_2, \\dotsc, a_n\\}$, ordered by $f_i$. \n", "\n", "$a_i$ and $a_j$ are compatible if their intervals don't overlap.\n", "\n", "**Problem**: \n", "We wish to select a maximum-size subsets of mutually compatible activities. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
1234567891011
s130535688212
f4567991011121416
\n", "
" ], "text/plain": [ " 1 2 3 4 5 6 7 8 9 10 11\n", "s 1 3 0 5 3 5 6 8 8 2 12\n", "f 4 5 6 7 9 9 10 11 12 14 16" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# eg\n", "raw_data = [\n", " [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12],\n", " [4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]\n", "]\n", "\n", "df = pd.DataFrame(raw_data, index=['s', 'f'], columns=xrange(1,12,1))\n", "df" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Dynamic Programming\n", "denote: $S_{ij} = \\{a_{i+1}, \\dotsc, a_{j-1}\\}$.\n", "\n", "Suppose $a_k$ in an optimal solution, then the left two subproblems: $S_{ik}$ and $S_{kj}$, whose optimal solution should be within the optimal solution of $S_{ij}$.\n", "\n", "\\begin{equation}\n", " c[i,j] = \\begin{cases}\n", " 0 & \\quad \\text{ if } S_{ij} = \\emptyset \\\\\n", " max_{a_k \\in S_{ij}} c[i,k] + c[k,j] + 1 & \\quad \\text{ otherwise}\n", " \\end{cases}\n", "\\end{equation}" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#todo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Making the greedy choice\n", "Intuition: \n", "we should choose an activity that leaves the resource available for as many other activities as possible. \n", "Hence, the first one should be the activity in $S$ with the earliest finish time.\n", "\n", "##### Is the greedy choice always part of some optimal solution?\n", "\n", "**Theorem 16.1**: \n", "Let $S_k = \\{a_i \\in S: s_i \\geq f_k\\}$. \n", "We have $a_m$ s.t. $f_m = min(f_i : a_i \\in S)$ \n", "Then $a_m$ must be included in some maximum-size subset of mutually compatible activities of $S_k$.\n", "\n", "Proof: (构造法） \n", "\n", "Let $A_k$ be a maximum-size subset, and $a_j$ s.t. $f_j = min(f_i: a_i in A_k)$. \n", "Because $f_m \\leq f_j$, \n", "hence we could replace $a_j$ with $a_m$, namely, $A'_k = (A_k - a_j) \\cup a_m$. \n", "then we get a new maximum-size subset $A'_k$ which includs $a_m$. \n", "\n", "##### An recursive greedy algorithm\n", "tail recursive\n", "\n", "##### An iterative greedy algorithm" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
1234567891011
s130535688212
f4567991011121416
\n", "
" ], "text/plain": [ " 1 2 3 4 5 6 7 8 9 10 11\n", "s 1 3 0 5 3 5 6 8 8 2 12\n", "f 4 5 6 7 9 9 10 11 12 14 16" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1, 4, 8, 11]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def greedy_activity_selector(df):\n", " n = df.shape[1] + 1\n", " k = 1\n", " A = [k] \n", "\n", " for m in xrange(2, n):\n", " if df.loc['s', m] >= df.loc['f', k]:\n", " A.append(m)\n", " k = m\n", " return A\n", "\n", "greedy_activity_selector(df)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 16.2 Elements of the greedy strategy\n", "###### design\n", "1. Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.\n", "\n", "2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.\n", "\n", "3. Demonstrate optimal substructure, and combine solutions.\n", "\n", "Beneath every greedy algorithm, there is almost always a more cumbersome dynamic-programming solution.\n", "\n", "**Two key ingredients**: greedy-choice property and optimal substructure.\n", "\n", "\n", "##### Greedy -choice property\n", "idea: we can assemble a globally optimal solution by making locally optimal (greedy) choices.\n", "\n", "Dynamic programming: solves the subproblems before making the first choice. $\\to$ bottom-up, iteration \n", "Greedy algorithm: makes its first choice before solving any subproblems. $\\to$ top-down, recursive \n", "\n", "+ usually more efficient without considering a wider set of choices.\n", " \n", " \n", "##### Optimal substruture\n", "A problem exhibits optimal substruture if an optimal solution to the problem contains whithin it optimal solutions to subproblems.\n", "\n", "namely, an optimal solution to the subproblem, combined with the greedy choice already made, yields an optimal solution to the original problem.\n", "\n", "\n", "##### Greedy versus Dynamic programming\n", "1. 0-1 knapscak problem: \n", " Given: A thief robbing a store finds $n$ items. The $i$th item is worth $v_i$ dollars and weighs $w_i$ pounds. \n", " The thife can carry at most $W$ pounds in his knapsack. \n", " For a item, the thife must either take it or leave it behind.\n", " \n", " Problem: Which combination of itmes the thief choose to take as valuable a load as possible? \n", "\n", "2. fractional knapsack problem: \n", " diff: For a item, the thife can take fraction of items." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 16.3 Huffman codes\n", "##### Prefix codes\n", "**prefix codes**: codes in which no codeword is also a prefix of some other codeword. \n", "$implies$ unambiguous.\n", "\n", "+ A prefix code can always achieve the **optimal data compression** among any character code.\n", "\n", "+ An optimal code is always represented by a **full** binary tree. \n", " The number of bits required to encode a file is thus: $$B(T) = \\displaystyle\\sum_{c \\in C} c.\\text{freq} \\cdot d_T(c)$$ which we define as the cose the **cost** of the tree $T$.\n", "\n", "\n", "#### Constructing a Hunffman code\n", "The algorithm uses a min-priority queue $Q$, keyed on the _freq_ attribute, to identify the two least-frequent object to merge together.\n", "\n", "running time: $O(n \\lg n)$\n", "\n", "\n", "##### Correctness of Huffman's algorithm\n", "###### 1. greedy-choice property\n", "构造法：任意最优解，转变成希望形式的最优解\n", "###### 2. optimal-substructure property\n", "反证法\n", "\n", "详见书和 penultimate 笔记" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "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 }