Summary_Algo_Backup.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm\n",
    "\n",
    "## DP\n",
    "\n",
    "* 装配线调度问题\n",
    "    - m个装配线，n个工序，装配线之间切换需要时间，装配线上的每个站完成工序需要不同的时间，在n个装配线下，最短需要多少时间完成\n",
    "    - A[i,j]为在第i调装配线上完成第j个工序的最短时间\n",
    "* 乘法链问题\n",
    "    - 矩阵乘法通过不同的括号组合可以减小其中标量乘法计算次数，求矩阵乘法计算顺序\n",
    "    - A[i,j]为从第i个到第j个矩阵做乘法的最小标量乘法次数\n",
    "* 最长公共子列\n",
    "    - A[i,j]表示序列X[:i]和Y[:j]的最长公共子列长度\n",
    "* 最优二叉查找树\n",
    "    - 大致描述：一堆叶子节点从小到大排序，每个叶子对应一定的查找概率；叶子的分割点也从小到大排序，每个分割点也对应一定的查找概率。期望代价为（叶子和分割点）的（查找概率乘以深度之和）。目标是期望代价最小。\n",
    "    - A[i,j]表示叶子i到叶子j之间构造最优查找树的期望代价。\n",
    "* 其他适用问题：\n",
    "    - Viterbi算法，编辑距离等    \n",
    "* 证明方法：最优子结构\n",
    "    - cut-and-paste：最优解使用的子问题的解必须是最优的，否则，可以导出矛盾\n",
    "    \n",
    "## Greedy\n",
    "\n",
    "* minimum spanning tree: subset of edges to connect all vertices with minimum weight sum\n",
    "    - Kruskal algorithm greedily pick smallest weight\n",
    "* interval scheduling: given start time, end time, find maximum compatible intervals\n",
    "    - greedily pick the task with earliest finish time that is compatible with the previous\n",
    "    - optimality proved by exchange argument\n",
    "* interval partitioning: given start time, end time, find maximum of m/c to finish all the tasks\n",
    "    - greedily pick the task in order of increasing start time, if the task cannot be allocated, open a new m/c\n",
    "    - property: #m/c can never be less than maximum depth, depth is number of overlapping tasks at a given time\n",
    "* schedule to minimize maximum lateness: earliest ddl first\n",
    "    - inversion: two adjacent jobs - latter one has earlier ddl\n",
    "    - swap on inversion does not increase lateness \n",
    "    - optimal has no idle time; there's optimal strategy with no inversion\n",
    "    - earliest-ddl-first greedy is optimal\n",
    "* optimal offline caching: farthest-in-future\n",
    "    - reduced schedule: only insert an item to cache when it is requested\n",
    "    - every strategy can transform to reduced version with no more eviction\n",
    "* Huffman coding: merge from least frequent node\n",
    "    - 合并叶子节点为一个节点，节点的频率为叶子节点频率之和，这样做新树和旧树的代价只相差一个常数，因此具有意义的最优结构\n",
    "    - 通过把频率最小换到最深的位置，可以证明不增加总体代价，由此证明最优解中最小频率的两个节点一定是最深的兄弟\n",
    "    \n",
    "Methods used to prove optimal:\n",
    "1. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm's.\n",
    "1. Discover a simple \"structural\" bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound. \n",
    "1. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.\n",
    "1. Show it is a matroid\n",
    "\n",
    "Matroid is a tuple $(S, I)$, where $S$ is a finite ground set, and $I$ is a family of *independent* subset of $S$, which has following properties\n",
    "\n",
    "1. Hereditary property: $B\\in I, A\\subset B \\Rightarrow A\\in I$\n",
    "2. Exchange property: $A\\in I, B\\in I, |A|<|B| \\Rightarrow \\exists x \\in B-A, s.t. A\\cup \\{ x \\} \\in I$\n",
    "\n",
    "A **Weighted Matriod Problem** is a matroid where each element in $S$ assigned by a weight $w_i$ and the total weight of a independent subset of $S$ is maximized. This problem can be solved greedy algorithm.\n",
    "\n",
    "```\n",
    "Greedy(S, I, w):\n",
    "A = {}\n",
    "sort S decreasingly by w\n",
    "for x in S:\n",
    "    if A + {x} in I:\n",
    "        A = A + {x}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Divide and conquer\n",
    "\n",
    "### Quick sort\n",
    "\n",
    "```\n",
    "def quicksort(A, p, r):\n",
    "    if p<r:\n",
    "        q = partition(A, p, r)\n",
    "        quicksort(A, p, q-1)\n",
    "        quicksort(A, q+1, r)\n",
    "```\n",
    "\n",
    "* 最坏情况是每次找到的划分元素要么是最大的要么是最小的，即划分总是不对称，这是运行时间为$O(n^2)$。\n",
    "* 最好情况是每次都能找到比较对称的划分，运行时间为$O(n \\log n)$\n",
    "* 平均每次划分有的好有的坏，最后也能达到$O(n \\log n)$的运行时间（!证明）\n",
    "\n",
    "### Merge sort\n",
    "\n",
    "```\n",
    "def mergesort(A, p, r):\n",
    "    if p<r:\n",
    "        q = floor((p+r)/2)\n",
    "        mergesort(A, p, q)\n",
    "        mergesort(A, q+1, r)\n",
    "        merge(A, p, q, r)\n",
    "```\n",
    "\n",
    "* 证明正确性：子问题有序，通过合并$O(n)$也能够使得父问题有序\n",
    "* 最好、最坏和平均情况都有$O(n\\log n)$次的比较\n",
    "* 最坏和平均都有$O(n\\log n)$次交换，最好情况可以不交换\n",
    "\n",
    "### Maximum subarray\n",
    "\n",
    "* 描述：一个串有正有负的数字，找一个连续的子串，使其和最大\n",
    "* 解法：分治法和动态规划都可以解决\n",
    "* 分治法：拆成两半，不仅返回两半各自最大子串和，也返回该串内cumsum最小值和cunsum最大值，如果最大子串落在两半中间，可以通过``maxPrefixRight - minPrefixLeft``得到中间的最大子串和。递归$T(n) = 2 T(n/2) + O(1) \\, \\Rightarrow O(n)$。\n",
    "\n",
    "```\n",
    "def loop(l,r):\n",
    "    if l == r: return (A[l], sumsum[l], cumsum[l+1])\n",
    "    else: \n",
    "        # If I have more than one element, split the array and loop over left and right part.\n",
    "        c = (l + r - 1) // 2\n",
    "        resLeft, minPrefixLeft, maxPrefixLeft = loop(l, c)\n",
    "        resRight, minPrefixRight, maxPrefixRight = loop(c + 1, r)\n",
    "        minPrefix = min(minPrefixLeft, minPrefixRight)\n",
    "        maxPrefix = max(maxPrefixLeft, maxPrefixRight)\n",
    "        # Solution overlapping both the left and the right part can be computed as follows.\n",
    "        resCenter = maxPrefixRight - minPrefixLeft\n",
    "        # Overall solution is maximum of solutions on the left, on the right and overlapping.\n",
    "        res = max(resLeft, resCenter, resRight)\n",
    "        return (res, minPrefix, maxPrefix)\n",
    "```\n",
    "\n",
    "* 动态规划：截止某个位置的最大子串和要么是包含该位置的最大子串和``max_ending_here``要么是不包含这个位置的``max_so_far``。只过一遍，$O(n)$。\n",
    "\n",
    "```\n",
    "def max_subarray(A):\n",
    "    max_ending_here = max_so_far = A[0]\n",
    "    for x in A[1:]:\n",
    "        max_ending_here = max(x, max_ending_here + x)\n",
    "        max_so_far = max(max_so_far, max_ending_here)\n",
    "    return max_so_far\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve recurrence\n",
    "\n",
    "Methods to solve recurrences are \n",
    "\n",
    "1. Guess and confirm (can be used in all cases): guess and replace to prove it's true; unrolling to find the rule\n",
    "2. Recurrence tree (solve $T(n) = aT(\\frac{n}{b}) + f(n)$ like recurrences): $T(n) = \\sum_{k=0}^L a^k f(\\dfrac{n}{b^k})$\n",
    "3. Master therem\n",
    "\n",
    "![](figures/fig20180320_master_theorem.png)\n",
    "\n",
    "Something useful:\n",
    "* $\\sum_{i=1}^n \\dfrac{1}{i} = \\Theta(\\log n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest path\n",
    "\n",
    "### Dijkstra\n",
    "\n",
    "单源最短路径问题，边权重为正数。贪心法\n",
    "\n",
    "```\n",
    "Dijkstra (G, w):\n",
    "    let S be the set of explored nodes\n",
    "        for each u in S, we store a distance d[u]\n",
    "    initially S={s}, d[s] = 0\n",
    "    while S != V:\n",
    "        all edges connect S and V-S, e=(u,v)\n",
    "        d[v] = min(d[u] + l[e]) for all e\n",
    "        S += {v}\n",
    "```\n",
    "\n",
    "最优性证明：归纳法，考虑不从s~>u->v，而是从s~>x(x in S)->y(y not in S)~>v，注意到每次先扩展最小的，所以到v的肯定比到y短，因此不可能从别的点绕一圈回到v更短。\n",
    "\n",
    "### Bellman-Ford Algorithm\n",
    "\n",
    "单源最短路径问题，权重可以为负数，但是不能有负环。动态规划，定义$opt[i,v]$为从v到t最多用i条边的最短路径，有状态转移方程\n",
    "\n",
    "$$\n",
    "opt[i,v] = \\min(opt[i-1, v], \\min_{w\\in V} (opt[i-1, w] + c[v, w])) \n",
    "$$\n",
    "\n",
    "计算的时候按照i递增的顺序计算即可。\n",
    "\n",
    "应用：用于网络路由，每个节点可以维护当前节点到其他节点的数值$M[t]=\\min_{w\\in V} (opt[i-1, w] + c[v, w])$，这样一个包在每次都只用选择相连的$M[t]$最小的节点即可。维护的方法是对于每个节点都去基于$M[v] = \\min(M[v], \\min_u M[u]+c[v,u])$去更新，如果更新了，该节点激活，用于提示相邻节点也看看要不要更新。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Floyd-Warshall算法\n",
    "\n",
    "多源最短路径问题，权重可以为负数，但是不能有负环。动态规划，定义$d_{ij}^{(k)}$表示从顶点i到顶点j，并且中间路径中顶点属于[k]的最短路径。最开始$d_{ij}^{(0)}=w_{ij}$，如果顶点i和顶点j直接相连。有状态转移方程\n",
    "\n",
    "$$\n",
    "d_{ij}^{(k)} = \\min(d_{ij}^{(k-1)}. d_{ik}^{(k-1)} + d_{kj}^{(k-1)})\n",
    "$$\n",
    "\n",
    "三层循环，从外到内分别是k,i,j，运行时间$O(|V|^3)$。要想追踪具体的路径，可以利用一个前驱矩阵来每次记录选用的哪个k。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimum spanning tree\n",
    "\n",
    "### Kruskal's algorithm\n",
    "\n",
    "* 方法：每次选取一条最短的边，并且这条边不和现有的边构成环\n",
    "* 性质：如果一条边$e=(u,v)$是从S到V-S最小的边，那么所以的最小生成树必须包含这条边。证明：如果不选e，那么最小生成树P中从u到v一定有一条路径，这条路径肯定横跨S和V-S，横跨的边为$e'$，把边从$e'$换成$e$可以使得代价更小。\n",
    "\n",
    "### Prim's algorithm\n",
    "\n",
    "* 方法：每次加入一条边到S中，每次加入最短的连接到V-S的边\n",
    "* 证明方法与上面类似"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sort\n",
    "\n",
    "### Bubble Sort\n",
    "\n",
    "```\n",
    "for i = 1 to N-1:\n",
    "    for j = 1 to N-i:\n",
    "        if A[j] < A[j-1]:\n",
    "            swap(A[j], A[j-1])\n",
    "```\n",
    "\n",
    "* 证明正确性：每个j循环之后，A[N-i:N]都变为有序的\n",
    "* 复杂度：不管什么情况都需要$O(n^2)$次判断，最好情况可以不做交换，平均和最坏需要$O(n^2)$次交换\n",
    "\n",
    "###  Insertion Sort\n",
    "\n",
    "```\n",
    "for i = 2 to N:\n",
    "    tmp = A[i]\n",
    "    for j = i downto 2:\n",
    "        if tmp >= A[j-1]:\n",
    "            break\n",
    "        A[j] = A[j-1]\n",
    "    A[j] = tmp\n",
    "```\n",
    "\n",
    "* 证明正确性：每次j循环之后A[1:i]都变为有序的\n",
    "* 运行时间：$O(n^2)$\n",
    "\n",
    "### Heap Sort\n",
    "\n",
    "* 最大堆：一颗二叉树，每个父节点都比自己的子节点大\n",
    "* 一个最大堆，根节点i被修改了，通过max_heapify可以使得其在$O(\\log n)$时间内维护成最大堆\n",
    "\n",
    "```\n",
    "def max_heapify(A, i):\n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l <= heapsize and A[l] > A[i]:\n",
    "        largest = l\n",
    "    else:\n",
    "        largest = i\n",
    "    if r <= heapsize and A[r] > A[largest]\n",
    "        largest = r\n",
    "    if largest != i\n",
    "        swap(A[i], A[largest])\n",
    "        max_heapify(A, largest)\n",
    "```\n",
    "\n",
    "* 思路：先建立一个堆，由最大堆的性质可以知道，堆的根是最大的元素，把根和最后一个叶子互换，然后把那个叶子从堆中取走，再维护成一个最大堆。如此重复，可以得到排序\n",
    "\n",
    "```\n",
    "def build_heap(A):\n",
    "    headsize(A) = len(A)\n",
    "    for i = floor(len(A) / 2) downto 1:\n",
    "        max_heapify(A, i)\n",
    "```\n",
    "\n",
    "```\n",
    "def heap_sort(A)\n",
    "    build_heap(A)\n",
    "    for i = N downto 2:\n",
    "        swap(A[1], A[i])\n",
    "        heapsize(A) -= 1\n",
    "        max_heapify(A, 1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Data Structure\n",
    "\n",
    "### Binary Search Tree\n",
    "\n",
    "* 每个节点左子树上面元素的数值都比该节点小，右子树上面元素的数值都比该节点大。\n",
    "* 查询：递归判断大小觉得往左还是往右，运行时间为树的平均深度\n",
    "* 找最大和最小：一直往左或者往右，运行时间为树的深度\n",
    "* 给定一个节点找后继（比该节点数值大的节点中最小的）：如果有右子树就找右子树中最大的，如果没有就找祖先中第一个把自己这一支当做左子树的节点\n",
    "* 插入：和查找类似，找到能找到的最近的叶子，在该叶子上开一个节点来放自己\n",
    "* 删除：如果是一个单节点，直接删除；如果有一个子节点，把子节点接到父节点上面；如果有两个子节点，找出自己的后继，用后继替代自己的位置\n",
    "\n",
    "### B-tree\n",
    "\n",
    "* 性质：\n",
    "    - 每个节点有多个子节点，节点中顺序存放子节点的分割数值\n",
    "    - 除了根节点之外，每个节点的子节点数目$[t-1, 2t-1]$，如果子节点数目达到$2t-1$就说这个节点是满的\n",
    "* 查询：显而易见\n",
    "* 插入：如果要插入的节点从上到下都不满，就直接插入；如果满了就需要把满的节点分裂。分裂的方式就是把节点中第t个元素提到父节点中，然后把[1:t-1]和[t+1:2t-1]元素分别分裂成两个分支\n",
    "* 删除：情况比较复杂，总体思想就是不能违反B树的性质\n",
    "\n",
    "### Union-Find Set\n",
    "\n",
    "* 作用：反映元素和集合之间的关系\n",
    "* 主要功能：\n",
    "    - MAKE_SET(x)：建立一个只包含元素x的集合\n",
    "    - UNION(x,y)：把x所在的集合和y所在的集合合并\n",
    "    - FIND_SET(x)：找出x所对应的集合\n",
    "* 实现：\n",
    "    * 链表\n",
    "    * 带路径压缩的树结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Graph\n",
    "\n",
    "### BFS\n",
    "\n",
    "```\n",
    "def BSF(G, s):\n",
    "    for each u in G:\n",
    "        color[u] = WHITE\n",
    "    color[s] = GRAY\n",
    "    Q = [s]\n",
    "    while Q:\n",
    "        u = Q.pop()\n",
    "        for each v adj to u:\n",
    "            if color[v] = WHITE:\n",
    "                color[v] = GRAY\n",
    "                Q.append(v)\n",
    "        color[u] = BLACK\n",
    "```\n",
    "\n",
    "### DFS\n",
    "\n",
    "```\n",
    "def DFS(G):\n",
    "    for each u in G:\n",
    "        color[u] = WHITE\n",
    "    for each u in G:\n",
    "        if color[u] == WHITE:\n",
    "            DFS_visit(u)\n",
    "            \n",
    "def DFS_visit(u):\n",
    "    color[u] = GRAY\n",
    "    for each v adj to u:\n",
    "        if color[v] == WHITE:\n",
    "            DFS_visit(v)\n",
    "    color[u] = BLACK\n",
    "```\n",
    "\n",
    "### Topological Order\n",
    "\n",
    "* 性质：在有向无环图中，存在一种排序使得每条边都往后指\n",
    "* 运行DFS，并且按照每个节点被标记为黑色的时间先后顺序排序就是拓扑排序；只有某个节点的后继都标黑了它才可能标黑，所以标黑时间靠后的排在前面。\n",
    "\n",
    "### Strongly Connected Components\n",
    "\n",
    "* 定义：一个图中的一个节点集合，任意两个节点都可以互通，就叫做强连通分支；问题是给定一个图，找出其强连通分支的分解\n",
    "* 图的转置：就是把边都翻过来 $G^T=(V, E^T)$，$E^T = \\{(u,v) | (v, u)\\in E\\}$\n",
    "\n",
    "```\n",
    "def strongly_connected_components(G):\n",
    "    DFS(G) record turn-black time f(u) for all u\n",
    "    DFS(G^T) in decreasing order of f(u) and record the forest\n",
    "        each tree in the forest is a strongly connected component\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing Table\n",
    "\n",
    "* 关键字域U很大，但是实际的关键字集合K很小。这时如果要用**直接寻址法**储存每个关键字对应的数值，需要的内存开销为$|U|$。如果能够使用一个hash function $h: U \\rightarrow [m]$就可以把所需要的内存降低到m。\n",
    "* 坏处是可能发生不同的关键字被映射到同一个槽位上，即碰撞（collision）。解决方法有chaining和open addressing。\n",
    "\n",
    "### Chaining \n",
    "\n",
    "* 做法：每个槽位后面跟一个链表，插入和删除就直接对链表操作时间为$O(1)$\n",
    "* 查找的时间：通过计算期望得到$O(1+\\alpha)$，其中$\\alpha = n/m$，$m$为槽位数目，$n$为要储存的元素个数。即如果$m$和$n$成正比，就能在$O(1)$时间内完成查找。\n",
    "\n",
    "### Open Addressing\n",
    "\n",
    "* 思路：与chaining不同的是，开放寻址中所有的元素都存在槽位里面，如果发生冲突，就找散列函数对应的下一个槽位。因此其装载因子$\\alpha\\le 1$。\n",
    "* 做法：把之前的散列函数的输入加入一个探查号i，$h:U\\times [m] \\rightarrow [m]$，并且希望探查号$i=1,\\cdots,m$对应的槽位是所有槽位的一个排列，不同散列函数尽量对应不同的排列。\n",
    "* 具体散列函数：\n",
    "    - 线性探查：$h(k,i)=(h'(k) + i) \\mod m$\n",
    "    - 二次探查：$h(k,i)=(h'(k) + c_1i+c_2i^2) \\mod m$\n",
    "    - 双重探查：$h(k,i)=(h_1(k) + i h_2(k)) \\mod m$\n",
    "\n",
    "### Univeral Hashing\n",
    "\n",
    "* 思路：如果固定一个散列函数，对手都可以选择全部散列到同一个槽位的n个元素给你作对，使得算法的检索时间为$\\Theta(n)$。我们希望设计一组散列函数，每次随机选择一个散列函数，这样就有较好的平均性能。\n",
    "* 定义：对于任意的不同关键字$k,l\\in U$，满足$h(k) = h(l)$的散列函数$h\\in \\mathcal{H}$的个数至多为$|\\mathcal{H}|/m$。\n",
    "* 设计一个universal hashing：$\\mathcal{H}_{p,m} = \\{ h_{a,b} : a\\in[1:p-1], b\\in[0:p-1]\\}$，其中$h_{a,b}(k) =((ak+b) \\mod p) \\mod m$\n",
    "\n",
    "### Perfect Hasing\n",
    "\n",
    "* 定义：如果某一种散列技术在进行查找时，最坏情况的性能也是$O(1)$的话，称其为perfect mathing。仅在关键字是静态时，才有完全散列。\n",
    "* 做法：采用两级散列表，第一级散列表照常进行，第二级散列表选择的槽位数目$m_j=n_j^2$，可以证明大于$1/2$的概率可以一次选的一个没有碰撞的二级散列表（注意到关键字是静态的），通过几次尝试可以选择一个没有碰撞的散列函数。由于第二级散列表没有冲突，因此最坏查询时间也是$O(1)$。同时可以证明，总体存储空间也是$O(n)$，即$\\mathbb{E}[\\sum_{j=1}^{m-1}n_j^2] < 2n$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Flow\n",
    "\n",
    "* 流网络：$G(V,E)$每条边关联一个非负容量c；存在单一源点$s\\in V$；存在单一汇点$t\\in V$。\n",
    "* 流函数：$f:E\\rightarrow\\mathbb{R}^+$，并且满足\n",
    "    - 容量条件：对于每条边$e\\in E$，$0\\le f(e)\\le c[e]$\n",
    "    - 守恒条件：$\\forall e\\in E \\setminus \\{s, t\\}$，$\\sum_{e\\text{ towards }v} f(e) = \\sum_{e\\text{ from }v} f(e)$\n",
    "* 最大流：使得$v(f) = f^{out}(s)$最大，其中$f^{out}(v) = \\sum_{e\\text{ from }v} f(e)$\n",
    "\n",
    "### Ford-Fulkerson\n",
    "\n",
    "* 剩余图：$G_f$的点集和$G$的点集相同，每条边$e=(u,v)$，如果$f(e)<c[e]$，则在$G_f$中构建一条容量为$c[e]-f(e)$的前向边$(u,v)$；如果$f(e)>0$，则在$G_f$中构建一条容量为$f(e)$的前向边$(v,u)$\n",
    "\n",
    "* 对于一条简单路径P、现在已经存在的流f，去增加f的流量。其中``bottleneck(P,f)``是P上任何边关于f的最小剩余容量（还可以增大多少容量）。\n",
    "\n",
    "```\n",
    "def augment(f, P):\n",
    "    b = bottleneck(P, f)\n",
    "    for e in P:\n",
    "        if e is forward edge in G_f:\n",
    "            f(e) += b\n",
    "        elif e is backward edge in G_f:\n",
    "            f(e) -= b\n",
    "    return f\n",
    "```\n",
    "\n",
    "```\n",
    "def max_flow:\n",
    "    f(e) = 0 for all e in G\n",
    "    while exist s-t path in G_f:\n",
    "        P = the exist s-t path\n",
    "        f' = augment(f, P)\n",
    "        f = f'\n",
    "        G_f = G_f'\n",
    "    return f\n",
    "```\n",
    "\n",
    "* 分析：如果容量都是整数。每次产生的新的流，由于bottleneck>0，$v(f') = v(f) + bottleneck(P,f)$，所以每次循环都变好。假设最大流为C，因此算法肯定能够在$O(C(|V|+|E|))$内找到答案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Max Flow and Minimum Cut\n",
    "\n",
    "* s-t割：是对于结点集合V的一个划分(A,B)，使得$s\\in A$，$t\\in B$。一个割的容量记为$c(A,B)=\\sum_{e from A} c[e]$\n",
    "* 性质：\n",
    "    - f是任意s-t流，(A,B)是任意s-t割，那么$v(f) = f^{out}(A)-f^{in}(A) = f^{in}(B)-f^{out}(B)$，$v(f) \\le c(A,B)$\n",
    "    - Ford-Fulkerson返回最大流：f是剩余图中没有s-t路径的一个s-t流，那么G中存在一个s-t割$(A^*,B^*)$使得$v(f) = c(A^*,B^*)$\n",
    "    - 最大流-最小割定理：每个流网络中，存在一个流f和一个割(A,B)使得$v(f) = c(A,B)$；每个流网络中，s-t流的最大值等于s-t割的最小容量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiple Sources/Sinks\n",
    "\n",
    "* 每个节点都有供给或者需求，守恒条件变为需求条件$f^{in}(v) - f^{out}(v) = d_v$，求解的问题变为判断是否存在一个可行的解满足所有点的需求。\n",
    "* 解决方法：引入一个超源点$s^*$它向每个$d>0$的节点有一条容量$d$的边，引入一个超汇聚点$t^*$每个$d<0$的节点都有一条容量为$-d$的边进入它。解决新问题的最大流问题，如果最大流v满足$v = \\sum_{d>0} d = \\sum_{d<0} -d$则存在可行解。\n",
    "\n",
    "### With Capacity Lower Bound\n",
    "\n",
    "* 描述：在前面的基础上，如果修改容量条件为$l[e]\\le f(e) \\le c_e$，再判断是否存在可行解\n",
    "* 解法：固定最小的容量，并且修改相关节点的需求值，转化为上面等价的问题\n",
    "\n",
    "### Other Problems\n",
    "\n",
    "* 调查设计：X产品，Y顾客；X-Y连边：顾客i购买过产品j，容量1；s-X连边容量有上下界，表示每个产品需要的问卷数；Y-t连边容量有上下界，表示每个顾客问卷涉及的产品数目；存在可行的流等价于存在可行方案\n",
    "* 航线调度：用k个飞机执飞若干个航班；节点为出发地或者目的地；如果有一趟航班，则添加一条边具有下界1和容量1；如果有足够时间从一个目的地到下一个出发地，则添加一条边具有下界0和容量1；s到每一个出发地都有一条边下界0和容量1（可以从任何出发地开始这一天）；相应的有t；源点-k的需求，汇点k的需求；是否存在可行解\n",
    "* 图像分割：问题描述是对于像素进行一个前景-后景的划分，$\\max \\sum_{i\\in A}a_i + \\sum_{i\\in B}b_i - \\sum_{(i,j)\\in E}p_{ij}$，其中$a_i,b_i$是前后景的概率，$p$是分割惩罚，$E$表示分割不同的相邻像素边。每个像素都是一个节点，节点之间的连边容量表示分割惩罚；s和所有节点相连，容量为$a_i$；所有节点和t相连，容量为$b_i$。找最大流对应的就是最小割，最小割刚好就是上面的优化目标。\n",
    "* 棒球排除：判断某个队z在当前情况下小组积分能否排第一。X：除z之外剩余比赛；Y：除z外的队伍；X-Y连边表示在比赛x中队伍y获胜，容量无限；连边s-X的容量表示还剩多少场比赛；连边Y-t容量表示要想z排第一其他队伍在剩下的比赛中不能获得超过此分数。如果存在最大流把s-X路径填满，则z可能获胜，否则不可能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matching\n",
    "\n",
    "* 定义：图$G(V,E)$中的一个边集$M\\subseteq E$，每个结点都至多出现在M的一条边上。称M为匹配。如果每个结点恰好出现在M的一条边上，成为完全匹配。\n",
    "    * matching: 不共点的边集M\n",
    "    * matching number: 不共点边集的边的数量\n",
    "    * maximum matching: matching number最大的\n",
    "    * perfect matching: 能够覆盖所有点的\n",
    "    * M-alternating path: $G=(V, E)$中一条交替出现在$M$和$E\\setminus M$中的路径\n",
    "    * M-augmenting path: 路径中两端没有被覆盖\n",
    "    \n",
    "### Hungarian Algorithm\n",
    "\n",
    "```\n",
    "start from any matching M\n",
    "if M is a perfect matching:\n",
    "    return M\n",
    "x0 = a exposed vertex in X\n",
    "A = {x0} \n",
    "B = {}\n",
    "if N(A) == B:\n",
    "    return NO_PERFECT_MATCHING\n",
    "    # because |N(A)|=|B|=|A|-1<|A|, violate Hall's theorem\n",
    "else:\n",
    "    y1 = a vertex in N(A) but not in B\n",
    "    if y1 is covered by M:\n",
    "        B += {y1}\n",
    "        A += {x1: (y1,x1) in M}\n",
    "        goto 'if N(A) == B'\n",
    "    else:\n",
    "        P = path from x0 to y is an alternating path\n",
    "        replace M by new M'\n",
    "        goto 'if M is a perfect matching'\n",
    "```\n",
    "\n",
    "### Hall's Theorem\n",
    "\n",
    "* 动机：如何在不求出最大流的情况下，找出一个证据说某二分图不存在完美匹配，即最大流小于n。根据最大流最小割定理，如果能够找到一个割容量小于n，即可说明。ps. 当然如果直接求出最大流，也能知道是否存在完美匹配。\n",
    "* 描述：对于一个子集$A\\subseteq X$，用$\\Gamma(A)\\subseteq Y$表示邻接A中节点的集合，如果二部图$(X,Y)$有完美匹配，那么对于所有的$A\\subseteq X$，都有$|\\Gamma(A)|\\ge |A|$。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Programming\n",
    "\n",
    "线性规划标准型表示：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max\\  {\\bf C}^T {\\bf x} \\\\\n",
    "& s.t. {\\bf Ax} \\le {\\bf b} \\\\\n",
    "& \\quad \\quad {\\bf x} \\ge 0\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "LP都可以转化为标准型。特别地，如果某元素$x_j$不满足$x_j \\ge 0$，可令$x'_j,x''_j \\ge 0$，代换$x_j = x'_j - x''_j$\n",
    "\n",
    "线性规划松弛型表示，相关的不等式约束都变成等式约束，只剩下关于单个元素的不等式约束：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max\\  z = v + \\sum_{j\\in N}c_j x_j \\\\\n",
    "& s.t. x_i = b_i - \\sum_{j \\in N} a_{ij}x_j, \\, \\forall i \\in B \\\\\n",
    "& \\quad \\quad x_i \\ge 0, \\, \\forall i \\in B\\cup N\n",
    "\\end{aligned}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simplex\n",
    "\n",
    "* 基本解：考虑松弛型表示，令第一个约束右边变量（非基本变量）都为0，得到的一组解\n",
    "* 基本可行解：如果基本解也满足第二个约束，则是基本可行解\n",
    "* 单纯形法思路：先找一个基本可行解，然后每次都考虑变化一个最优化表达式中的非基本变量，使其刚好不违反约束而使得目标最优，然后把这个非基本变量$x_e$代换成一个基本变量$x_l$（pivot），然后重复进行\n",
    "\n",
    "```\n",
    "def pivot(N, B, A, b, c, v, l, e):\n",
    "    b_new[e] = b[l] / a[l,e]\n",
    "    for each j in N-{e}:\n",
    "        a_new[e,j] = a[l,j] / a[l,e]\n",
    "    a_new[e,l] = 1/a[l,e]\n",
    "    \n",
    "    for each i in B-{l}:\n",
    "        b_new[i] = b[i] - a[i,e] * b_new[e]\n",
    "    for each j in N-{e}:\n",
    "        a_new[i,j] = a[i,j] - a[i,e] * a_new[e,j]\n",
    "    a_new[i,l] = - a[i,e] a_new[e,l]\n",
    "    \n",
    "    v_new = v + c[e] * b_new[e]\n",
    "    for each j in N-{e}:\n",
    "        c_new[j] = c[j] - c[e] * a_new[e,j]\n",
    "    c_new[l] = - c[e] * a_new[e,l]\n",
    "    \n",
    "    N_new = N - {e, l}\n",
    "    B_new = B - {e, l}\n",
    "    \n",
    "    return N_new, B_new, A_new, b_new, c_new, v_new\n",
    "```\n",
    "\n",
    "其中需要一个程序initialize_simplex来找到第一个基本可行解。\n",
    "\n",
    "```\n",
    "def simplex(A, b, c):\n",
    "    N, B, A, b, c, v = initialize_simplex(A, b, c)\n",
    "    while some index e in N that c[e] > 0:\n",
    "    for each i in B:\n",
    "        if a[i, e] > 0:\n",
    "            delta[i] = b[i] / a[i, e]\n",
    "        else:\n",
    "            delta[i] = inf\n",
    "        choose l in B that minimize delta[i]\n",
    "        if delta[l] == inf:\n",
    "            return UNBOUNDED\n",
    "        else:\n",
    "            N, B, A, b, c, v = pivot(N, B, A, b, c, v, l, e)\n",
    "            \n",
    "    for i = 1 to n:\n",
    "        if i in B:\n",
    "            x[i] = b[i]\n",
    "        else:\n",
    "            x[i] = 0\n",
    "    return x\n",
    "```\n",
    "\n",
    "### Duality\n",
    "\n",
    "LP\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max\\  {\\bf C}^T {\\bf x} \\\\\n",
    "& s.t. {\\bf Ax} \\le {\\bf b} \\\\\n",
    "& \\quad \\quad {\\bf x} \\ge 0\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "DP\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\min\\  {\\bf b}^T {\\bf y} \\\\\n",
    "& s.t. {\\bf A}^T y \\ge {\\bf C} \\\\\n",
    "& \\quad \\quad {\\bf y} \\ge 0\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "弱对偶：对偶问题的可行解$\\bf b^Ty$是原问题可行解$\\bf C^T x$的上界。在LP中，两者的最优解相等。"
   ]
  }
 ],
 "metadata": {
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}