{ "cells": [ { "cell_type": "code", "execution_count": 4, "metadata": { "code_folding": [], "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# setup\n", "from IPython.core.display import display,HTML\n", "display(HTML(''))\n", "display(HTML(open('rise.css').read()))\n", "\n", "# imports\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "%matplotlib inline\n", "sns.set(style=\"whitegrid\", font_scale=1.5, rc={'figure.figsize':(12, 6)})\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# CMPS 2200\n", "# Introduction to Algorithms\n", "\n", "## Greedy Algorithms, Unit-Task Scheduling, Knapsack\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Today's agenda:\n", "\n", "- Framework for Greedy algorithms\n", "- Unit-task Scheduling\n", "- The Knapsack problem\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "We previously looked at the Divide and Conquer framework. In this strategy, we used recurrences to give bounds on work/span and induction to prove correctness.\n", "\n", "We will now look at *Greedy* algorithms. The greedy framework is very simple: \n", "\n", "- Let $\\mathcal{X}$ be possible choices for the solution. Initialize solution $S=\\emptyset$. \n", "- Select $x\\in\\mathcal{X}$ according to a greedy criterion $C(x)$ and set $S := S \\cup \\{x\\}, \\mathcal{X} := \\mathcal{X} - \\{x\\}$.\n", "- Repeat until solution is complete.\n", "\n", "Selection Sort was an example of a greedy strategy. What was the greedy criterion? Why was our algorithm correct?\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For selection sort, we can see that swapping minimum element into the current position is a correct choice for the \"optimal\" solution. Moreover, selecting a minimum and sorting the rest of the list recursively is also correct." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "selecting minimum 1\n", "recursively sorting L=[2, 999, 4, 3]\n", "\n", "selecting minimum 2\n", "recursively sorting L=[999, 4, 3]\n", "\n", "selecting minimum 3\n", "recursively sorting L=[4, 999]\n", "\n", "selecting minimum 4\n", "recursively sorting L=[999]\n", "\n" ] }, { "data": { "text/plain": [ "[1, 2, 3, 4, 999]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def selection_sort(L):\n", " if (len(L) == 1):\n", " return(L)\n", " else:\n", " m = L.index(min(L))\n", " print('selecting minimum %s' % L[m]) \n", " L[0], L[m] = L[m], L[0]\n", " print('recursively sorting L=%s\\n' % L[1:])\n", " return [L[0]] + selection_sort(L[1:])\n", " \n", "selection_sort([2, 1, 999, 4, 3])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "When would the greedy strategy yield the correct solution?\n", "\n", "1. **Optimal substructure**: An optimal solution can be constructed from optimal solutions of smaller subproblems.\n", "2. **Greedy choice**: A greedy choice must be in some optimal solution (of a given size).\n", "\n", "Put together, these two properties yield that the iterative strategy above constructs an optimal solution.\n", "\n", "Due to their simplicity greedy algorithms are easy to implement. However proving the optimal substructure and greedy choice properties requires a problem-specific approach and can be tricky. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Unit Task Scheduling\n", "\n", "We already saw how a greedy scheduler could work to schedule concurrent tasks. However our greedy algorithm was not optimal. Let's consider the **unit task scheduling problem** where we are given a set of $n$ tasks $A = \\{a_0, \\ldots, a_{n-1}\\}$. Each task $i$ has start and finish times $(s_i, f_i)$. The goal is to select a subset $S$ of tasks with no overlaps that is as large as possible.\n", "\n", "

\n", "\n", "Example: Let the tasks be $a_0=(0, 2), a_1=(2, 4), a_2=(4, 6), a_3=(2, 8)$. What is the largest set of non-overlapping tasks?\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here, we should choose $S = \\{a_0, a_1, a_2\\}$ since choosing $a_3$ \"blocks\" a large part of the solution.\n", "\n", "Is there a greedy algorithm for the unit task scheduling problem?\n", "\n", "Does this problem have optimal substructure? What should the greedy choice be?\n", "\n", "**Optimal Substructure:** Since the tasks are nonoverlapping, if we identify one task in the optimal solution we can eliminate the tasks overlapping it and recursively solve for the remaining tasks.\n", "\n", "Is there a greedy criterion with the greedy choice property?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What if we chose the shortest task first?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What if we chose the task that started earliest? \n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What if we successively chose the task with fewest overlaps?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "What if we chose the task that finished earliest?\n", "\n", "$a_0=(0, 2), a_1=(2, 4), a_2=(4, 6), a_3=(2, 8)$\n", "\n", "This works on all of our counterexamples.\n", "\n", "What would the greedy choice property say here?\n", "\n", "**Greedy Choice Property**: For any set of tasks, the task with earliest finish time is in some optimal solution.\n", " \n", "**Proof**: Given a set of tasks $A$, let $G$ be the greedy solution and let $O$ be an optimal solution. Now, suppose that $G\\neq O$. Sort the tasks by finish time and let tasks $a\\in G$ and $a'\\in O$ be the first pair of tasks with $a\\neq a'$. So we have that $G =\n", "\\langle G_1, a, G_2\\rangle$ and $O = \\langle O_1, a', O_2\\rangle$. Consider the solution $X = \\langle G_1, a, O_2\\rangle$. Since $G$ and $O$ are both valid solutions and $a$ has earlier finish time than $a'$, all the tasks in $O_2$ are compatible with $\\langle G_1, a\\rangle$. So we now have that $|X| = |O|$, which proves that $a$ is in some optimal solution.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "So we've proven that the earliest finish time first strategy produces the optimal solution. What about work/span?\n", " \n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "Given a set of tasks, we can sort by earliest finish time in $O(n\\log n)$ work and $O(\\log^2 n)$ span. Then, we sequentially step through the tasks, adding a task to the solution if it doesn't overlap with a task that is already chosen. This takes $O(n)$ work/span." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Knapsack Problem\n", "\n", "Let's look another optimization problem. Suppose there are $n$ objects, each with a *value* $v_i$ and *weight* $w_i$. You have a \"knapsack\" of capacity $W$ and want to fill it with a set of objects $X \\subseteq [n]$ so that $w(X) \\leq W$ and $v(X)$ is maximized. \n", "\n", "Example: Suppose you have 3 objects with values/weights $(10, 5), (6, 3), (6, 2)$ and $W=5$. \n", "\n", "|value|weight|\n", "|------|-----|\n", "|10 |5 |\n", "|6 |3 |\n", "|6 | 2 |\n", "\n", "What if we greedily took the most valuable object first?\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What if we greedily took the object with highest per unit value (i.e., maximum value/weight ratio)?\n", "\n", "In the example above, we'd achieve a value of $12$, which is optimal. Does this always work?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Unfortunately no. Consider this counterexample with 2 objects that have weights/values $(10, 5), (9.999, 3)$.\n", "\n", "|value|weight|\n", "|------|-----|\n", "|10 |5 |\n", "|9.999 |3 |\n", "\n", "\n", "Is there another greedy criterion?\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We don't know of one (we'll see more of this problem in the next module). The problem is that a greedy algorithm, regardless of the criterion selects objects one at a time, without factoring in the capacity remaining into future decisions.\n", "\n", "What if we wanted to solve the **fractional** version of the problem, where we could take arbitrary amounts of each item?\n", "\n", "Does our weight/value greedy criterion satisfy the greedy choice property?\n", "\n", "**Greedy Choice Property for Fractional Knapsaack**: The item $j$ with largest $v_j/w_j$ is in an optimal solution to the fractional knapsack problem.\n", "\n", "**Proof**: Suppose we were given $n$ objects and their weights/values. Let $O$ be the optimal solution, and let $G$ be the greedy solution. Let item $j$ have the maximum value/weight ratio. Suppose $j\\not\\in O$, but that some item $i$ had maximum ratio $v_i/w_i$ in $O$ and that $\\alpha ~~(0\\leq \\alpha \\leq 1)$ fraction was present. Now, $v_i/w_i \\leq v_j/w_j$ so we can substitute the $\\alpha$ fraction of item $i$ with item $j$ to obtain a solution $O'$ with $v(O') \\geq v(O)$ that is also optimal. Thus item $j$ is in some optimal solution.\n", "\n", "How would we implement our solution? We sort by value/weight ratios and take successive items until we end with a possibly fractional item. The work is $O(n\\lg n + n) = O(n\\lg n)$ and the span is $O(\\lg^2 n + n) = O(n)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "celltoolbar": "Slideshow", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.5" }, "rise": { "autolaunch": true, "controls": false, "enable_chalkboard": true, "scroll": true, "theme": "simple", "transition": "fade" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": true, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }