zhengtongdu
Zhengtong's blog
learn&record&share

6.046_notes_01

6.046: Design and Analysis of Algorithms

笔记01：

Lesson 01: Introduction & Overview

  • 课程概览
  • 不同算法的复杂度
  • 问题1：区间调度问题

课程概览

  • Divide and Conquer - FFT and randomization algorithms
  • Optimization: greedy and dynamic programming
  • Network flow
  • Intractability (and dealing with it)
  • Linear programming
  • Sublinear algorithms, approximation algorithms
  • Advanced topics

相似的问题可能有不同的复杂度

定义hard：如果解决问题A可以转化为解决问题B的方法来解决，那么可以认为B的复杂度是比A的复杂度高，我们就说A问题可以约化为B问题，或者说A不比B难。

  • P问题：在多项式时间可以得出答案的问题，即$O(n^k)$存在某个常数$k$
  • NP问题：在多项式时间内能够被验证答案是否正确的问题
  • NP-complete问题：和其他NP问题一样难的NP问题

问题1：区间调度问题

对$n$段单独的区间资源$1, 2, \dots, n$进行请求。记$s(i), f(i)$分别为每个区间资源的开始时间和结束之间，我们约定$s(i) < f(i)$。如果两段区间资源$i, j$的所处区间没有重叠,即满足$f(i) \le s(j)$或$f(j) \le s(i)$，我们就称这两段区间资源是 兼容的(compatible) 。

Definition of Interval Scheduling Problem :

  • Input: $n$ requests with ${s(i), f(i) i = 1 , 2 , \dots , n}$
  • Goal: a compatible subset of ${1,2, \dots, n}$ of maximum size
  • Method: Select a greedy algorithm

贪心法求解区间调度问题

贪心法设计求解步骤

  1. 按一个 规则 选取请求$i$;
  2. 拒绝所有与$i$不兼容的请求；
  3. 对剩下的请求，重复步骤1和2，直到所有请求都被处理。

如何选取合适的规则？

可以选取的规则：

  • 选取开始时间$s(i)$最早的请求 -> 反例：当区间长度最长的请求开始时间最早
  • 选取区间长度$f(i) - s(i)$最短的的请求 -> 反例：两个接续进行的请求和一个与它们都不兼容的更短的请求
  • 选取和其它请求不兼容数量最少的请求 -> 反例：更多开始与结束时间相同的请求，会使得规则同设想情况不同
  • 选取结束时间$f(i)$最早的请求

通过如下两个命题证明最后一种规则是正确的规则：

  1. 命题1（兼容性条件）：满足要求的子集，可以通过重新排列，表示为 \((s(i_1), f(i_1)), (s(i_2), f(i_2)), \dots, (s(i_k), f(i_k))\) 其中 \(s(i_1) < f(i_1) \le s(i_2) < f(i_2) \le \dots \le s(i_k) < f(i_k)\)

  2. 命题2：按命题1的排列，不存在与请求$i_r$和$i_{r+1}$兼容的请求$j$，使得 \(f(i_r) \le s(j), f(j) \le s(i_{r+1})\) 同时满足（对$r = 1$和$r + 1 = k$，则其中有意义的一个不等式不满足）

由上述两个命题，便可以证明“选取最早结束请求”这个规则的正确性。

算法时间复杂度

该方法需要做一步对所有请求的结束时间排序的预处理，所需时间为$O(n\log n)$；接下来便是按序执行步骤，处理所有请求，所需时间为$O(n)$。因此算法的时间复杂度为$O(n \log n)$。

对于贪心法的总结

  • 贪心法是一种非常 “短视” 的策略，它更看重当前情况，实现最近一步可以实现最优结果；
  • 由于贪心法的理念，如何能够通过人为设定的规则，实现当前状况得到最优解是该方法最困难的部分，而且对于很多问题，证明规则的正确性同样是一件很困难的事情；
  • 此外，由于贪心法总是考虑一步最优解的“不回头策略”，因此通过该策略解决问题不一定总能找到最优解；
  • 但是由于贪心法的高效性，这种策略应用于对于最优解要求并不严格的问题时效果比较理想，并可以作为辅助算法，结合其他策略共同解决问题。

加权区间调度问题和更多更改

加权区间调度问题

如果我们将问题改为 加权区间调度 ，即对每段区间资源都添加一个与区间长度无关的权值$w(i)$，并将问题目标改为 求得权值相加最大的兼容请求子集。

此时一种可以求解的方法是 动态规划(Dynamic Programming)：

  • 定义子问题$opt(R^{x})$为请求集$R$中开始时间大于$x$的子集的兼容请求权值相加最大值；
  • 当请求$i$纳入考虑的时候，则此时$x$应为$f(i)$，且$opt(R^x)$应当加上$w(i)$；
  • 子问题的总数为$n$，基本情况$opt(R^{f(n)}) = 0$
  • 由此可以按关系式$opt(R) = \max_{1 \le i \le n}(w(i) + opt(R^{f(i)}))$求解目标问题

通过动态规划，加权区间调度问题的时间复杂度也可以达到$O(n \log n)$，但是按之前规则再次进行贪心策略的结果就会产生错误。

进一步修改问题设定

假设现在有$m$台处理请求的机器$\tau = {T_1, T_2,\dots, T_m}$，对于每个请求$i$，仅有子集$Q(i)\subseteq \tau$包含的机器可以处理该请求。如果每个请求的权值都是1:

  1. 问题 $m$台机器能够处理的请求最大数量 是 NP问题；
  2. 问题 判断$k \le n$个请求能否被兼容执行 是 NP完全问题；
  3. 问题 $m$台机器能够兼容处理的请求最大数量 是 NP难问题。

解决复杂问题(intractability)的方法

  • 采用近似的算法：可以提供多项式时间的优化；
  • 利用启发式算法来减少实际算例的时间；
  • 贪心或者其他实际应用有效的次优化启发式，但是无法保证效果。

Lesson 02: Divide and Conquer

  • 时间复杂度的计算范式
  • 问题2：凸包问题
  • 问题3：确定中位数问题

分治法的算法范式

给定一个规模为$n$的问题，将其分解为$a$个规模为$\frac{n}{b}$的子问题，其中$a\ge 1, b \ge 1$。递归解决每个子问题，将子问题的结果组合在一起，得到原始问题的结果。

时间花费满足如下关系式：

\[T(n) = aT(\frac{n}{b}) + [\mathrm{work\ for\ merge}]\]

问题2：凸包问题

问题描述

给定平面上的$n$个点

\[S = \{(x_i, y_i)|i = 1,2,\dots, n\}\]

并假设不存在两个具有相同$x$坐标或者$y$坐标的点，并且不存在共线的3个点。

凸包 (Convex Hull, CH($S$)): 能够包含$S$中所有点的最小多边形。

易知，CH($S$)的顶点即为$S$中的点，而且我们用顺时针顺序的点列来表示CH($S$)。

  • Input: point set $S = {(x_i, y_i) i = 1,2,\dots, n}$
  • Goal: CH($S$) = ${p_1, p_2, \dots, p_k}$
  • Method: Divide and Conquer

暴力法计算凸包

思路：通过判断$S$中任意两点的连线是否能将其余点分为两部分，来确定这两点的连线是否是凸包的一部分。

时间复杂度：$O(n^2)$条边，每条边进行$O(n)$次检测 -> 故复杂度为$O(n^3)$

利用分治法计算凸包

利用分治的思想计算凸包，首先需要进行预处理：对$S$中的所有点按$x$坐标进行排序：$O(n\log n)$

预处理后，按如下步骤求解CH($S$)：

  • 将$S$按$x$坐标排序，分为左半部分$A$和右半部分$B$；
  • 计算CH($A$)和CH($B$);
  • CH($S$) = merge(CH($A$), CH($B$)).

How to merge?

由于$A$和$B$是$S$的左半部分和右半部分，因此两个子凸包是彼此不相交的，所以通过结合子凸包CH($A$)和CH($B$)的点列，便可以得到CH($S$)。

假设$a_1$是CH($A$) $= (a_1, a_2,\dots, a_p)$中$x$坐标最大的点，$b_1$是CH($B$) $= (b_1, b_2,\dots, b_q)$中$x$坐标最小的点。$L$是$A$和$B$中间的一条垂直于$x$轴的直线，定义$y(i, j)$是$L$与线段$(a_i,b_j)$的交点纵坐标的值。

按如上定义，我们能够得知：CH($S$)与$L$有且只有两个交点，且上交点的值是$Y = {y(i, j) i = 1,2\dots, p;j = 1,2,\dots, q}$的最大值，下交点的值是$Y$的最小值。$L$左侧部分CH($S$)的点是CH($A$)的点，$L$右侧部分CH($S$)的点是CH($B$)的点。只要能够得知对应组成上交点的线段与下交点的线段，便可以完成Merge()操作。

Algorithm(类似于double-finger的操作) for get uppertangent:

    i = 1; 
    j = 1;
    while (y(i, j + 1) > y(i, j) || y(i - 1, j) > y(i, j))
        {
            if(y(i, j + 1) > y(i, j))   
                j = mod(j + 1, q);      // Move right finger clockwise
            if(y(i - 1, j) > y(i, j))
                i = mod(i - 1 + p, p);  // Move left finger anti-clockwise
        }
    return (a_i, b_j);

对于求下交点是同理的。

时间复杂度：

利用主定理，可以简单算出

\[T(n) = 2T(\frac{n}{2}) + \Theta(n) = \Theta(n \log n)\]

再加上预处理的的排序需要$O(n\log n)$的时间，利用分治法计算凸包的总时间复杂度为$\Theta(n\log n)$。

问题3：确定中位数问题

Table of Contents