算法期末复习

lecture9

布隆过滤器

数组有位(初始化为)，有个哈希函数(映射到~)

对于存储元素，通过固定的独立的个哈希函数得到个哈希值，将这些哈希值对应中的位置改为。

对于查询元素，通过以上个哈希函数得到个哈希值，判断对应的是否都为，若全为，可能之前存储过（可能是其他存储元素的哈希值组合在一起，将的哈希值覆盖了）；但若不全为，则之前一定没有存储过

假阳性概率

经过存储后特定位仍是的概率：

假阳性的概率：

：布隆过滤器的空间长度

：哈希函数的个数

：存储在中的元素个数

优势

允许误报，则会节省哈希空间

数据经过哈希加密

插入和查询都是，不受已存元素个数的影响

局部敏感哈希LSH

LSH函数会将相似的元素映射到相同的散列桶中

LSH哈希族满足：

当距离小于一定阈值（相似），则哈希值相等的概率较大
当距离大于一定阈值（不相似），则哈希值相等的概率较小

SRP角度随机投影

LSH for Jaccard Similarity

复杂度分析

• 查询时间：
• 空间使用：
• 预处理时间：

漏报概率：

lecture10

相似文本查找

Shingling：将文本转化为集合

文本中长度为的字符串的集合

MinHash：将大集合转换成短签名，同时保持相似性

签名:表示集合的短整数向量，并反映它们的相似性

• 将集合编码为向量
• 找到相似的列，计算小签名，并保证签名的相似性==列的相似性
  • 如果很高，
  • 如果很低，

Min-Hashing：表示列中第一个的行索引

随机交换次全部向量的某些维度，对于每个大向量记录第次交换后第一个出现的维度

此后作为短签名替换了原有的大向量。

保证了相似性：

一遍扫描压缩

for r=0:1:m
    h[1:k] = {h1(r), h2(r),…, hk(r)}
    for c =1:1:n
        if (C[r][c] == 0) 
            continue;
        else 
            for i =1:1:k
                if S[i][c] > h[i] 
                    S[i][c] = h[i] 
return S

：所占比例

LSH：关注相似的文本

对于Min-Hash矩阵：

• 将签名矩阵M的列散列到许多桶中
• 哈希到同一桶中的每对文档都是候选对

使用函数f(x,y)来判断x和y是否是候选对

寻找具有Jaccard相似度至少为s的文档

将矩阵M划分为b个带，每带r行

• 对于每个带，将每列的一部分散列到一个有k个桶的哈希表，使k尽可能大
• 候选列对是那些散列到同一桶≥1个带的列对
• 调整b和r以捕获大多数相似对

：所有都相等

：中的某几行不相等

漏检率：

误报率：

拐点：，高于拐点时分配的同一个桶的概率迅速接近，低于拐点时迅速接近

lecture11图

简单路径：所有顶点和边都不同的路径

简单环：除了外，其余所有顶点和边都不同的路径

无环连通无向图图称为树

有向无环图：

DFS

时间复杂度

• 邻接表：
• 邻接矩阵：

括号引理

祖孙关系可由的包含关系来确定

：开始访问的时间戳

：结束访问的时间戳

边的类型

• tree边：DFS树中的边

• forward边：(u, v)，其中v是树中u的后代

• back边：(u, v)，其中v是树中u的祖先。

• cross边:(u, v)其中u和v不是彼此的祖先或后代

DFS可以检测有向图中是否含有圈

强连通分量SCC

有向图G=(V,E)是强连通的，如果对于每个顶点u和v都有一条从u到v的路径和一条从v到u的路径。

DFS检测强连通分量：

• 生成反向图
• 将结束时间排序
• 选择结束时间最大的点开始

DFS森林的每一个子树都是强连通分量

高阶图的连通性

• 桥边：去除后会导致图不连通的边
• 边连通：不包含桥边的图
• 割点：移除会导致图不连通的顶点
• 重连通：不包含割点的图

寻找桥边

定义low[u]=min(d[u],min{d[w]：对于back边(v,w)，其中v是u的后代}）

即u的后代v，v的所有back边连接的祖先w中d[w]最小的，再和d[u]比较大小，较小者为low[u]

先经过DFS标好low值后：

for each (v in V) {
    u = pred[v]
    if (u != null and d[v] == low[v])
        (u, v) is bridge
}

即to点的d值和low值相等的边

寻找割点

先经过DFS标好low值后：

for each (u,v) {
    if (low[v] >= d[u])
        if (u不是树根，或孩子数量大于1):
            u is articulation point
}

BFS

与DFS相同，BFS的时间复杂度也为

BFS应用

• 寻找最短路径

• 检验二部图

  • 用交替的颜色给BFS树的层次上色
  • 如果没有两个相邻节点的颜色相同，那么它就是二分的。
  • 否则，就不是。

• （循环论证）如果有两个相邻节点的颜色相同，则图中存在一个奇长度的圈。但是你永远不能用两种颜色给一个奇圈上色，因此不会有两个相邻节点的颜色相同。

lecture12贪心

背包问题

贪心算法并不奏效，但可以用DP解决

贪心算法适用的前提

• 局部最优解能到导致产生全局最优解

• 每次贪心选择能将所求问题简化为规模更小的子问题

• 是否有贪心选择性质

贪心选择性质：在每一步选择中，都能够选择一个局部最优解，而这个选择不会对剩余的问题产生负面影响。

最优子结构性质：通过解决子问题的最优解，可以构建出原问题的最优解

最优贪心算法设计：

• 分析问题的子结构性质

• 设计一种局部最优的贪心机制

• 给出贪心算法

• 分析算法复杂度

• 证明算法正确性

• 分析证明此贪心机制是否产生全局最优方案

贪心算法最优性证明的通用框架：

• 我们首先考虑任意一个最优解。
• 如果它等于贪心解，那么贪心解是最优的。
• 否则，我们考虑这两个解决方案不同的第一个实例。
• 我们用贪心的选择取代了最优选择后，证明事情只会变得更好。
• 因此，通过归纳应用这个论证，可以得出贪心解和最优解一样好，因此它是最优的。

活动选择调度

已知一个集合R有n个活动。

每个活动都有一个给定的开始时间si和一个给定的结束时间fi。

如果两个请求i和j的开始结束间隔重叠，则它们会冲突

试确定由相互不冲突的请求组成的基数最大的R的子集。

局部最优解：在尽早的时间里完成尽多的活动

greedyIntervalSchedule(s, f) {
    sort by finish time//基于完成时间排序
    S = empty
    prev_finish = -INF
    for (i = 1 to n) {
        if (s[i] > prev_finish) {
            append task i to S
            prev_finish = f[i]
        }
    }
    return S 
}

时间复杂度：排序，其余步骤能在时间内完成，总体

正确性证明：不会出现有冲突的两个活动

最优性证明：

令是最优解的活动顺序

令是贪心解的活动顺序

若，证毕；

否则，由于是最优的，有。

假设第一个二者不同的活动索引为，则有

根据我们的贪心策略，的结束时间一定是的结束时间

所以在中将替换为后不会产生冲突，且与活动数量相同，因此它至少与我们的优化标准一样好。

通过重复这个过程，我们将最终在不减少活动数量的情况下将转化为。因此，是最优的。

迟到惩罚最小化调度

个任务

任务耗时小时

任务完成之前，每过小时需要支付

策略：尽早完成比率较大的任务

证明：

我们已经证明了：当时，比支付的金额少。

还是先考虑一个最优解，考虑贪心解中第一个与最优解所调度的工作不同的为工作

根据我们的贪心策略，当前的比率最大，但它不是最优解中的下一个调度工作

假设最优解中上一个被调度的工作，交换和，其他都不会改变，成本也交换前

我们继续在最优解中向前交换工作，直到是下一个调度的作业。

通过反复修改最优解，最终我们会将其修改成贪心解，且修改过程中不会增加总成本，因此是最优的。

间隔分区

给定活动，我们希望使用最少数量的资源来调度所有活动。

我们得到个活动请求的集合，每个请求都有开始和结束时间。

目标是找到最小的数，将划分为个不相交的子集，使得中的事件相互不冲突，

分析：

我们可以把它看成一个上色问题

我们希望为活动分配颜色，这样两个冲突的活动必须具有不同的颜色。

我们的目标是找到最小数量的颜色，这样就可以用这种方式为每个活动上色。

方法：

着色问题很难有效解决。

由于区间的简单性质，可以通过简单的贪心方法非常有效地解决区间划分问题。

首先，我们按开始时间对请求进行升序排序。

然后我们为每个请求分配最小的颜色(可能是一个新颜色)，这样它就不会与该颜色类的其他请求冲突。

算法：

greedyIntervalPartition(s, f) {
    sort by start times increasingly 
    for (i = 1 to n) {
        E = empty set
        for (j = 1 to i-1) {
        if ([s[j],f[j]]和[s[i],f[i]]有重叠) 
            add color[j] to E
        }
        Let c be the smallest color NOT in E
        color[i] = c
    }
    return color[1...n]
}

时间复杂度

正确性证明:

该算法从不为两个冲突的活动分配相同的颜色。因此，该算法产生一个有效的着色。

最优性证明：

定义depth(t)，为某一时刻，depth(t)表示开始时间到结束时间之间包含的活动的数量。

给定一组R的活动请求，定义depth(R)为对于的可能值中depth(t)最大的。

定理：针对原问题，需要的最小资源数depth(R)。

继续证明：

不失一般性，假设所有的开始和结束时间是不同的。

我们证明的目的是：若贪心分配了种颜色，那么我们就至少需要种。

若颜色被使用，则区间与其他种颜色不相容。

所有这些不相容是由早于开始的活动导致的

因此个区间在时间重叠

由颜色数量，因此至少需要种颜色。

最小化最大延迟

有个任务，其中第i个任务的执行时间为ti，截止时间为di。

同一时间只能执行一个任务，目标是调度任务，使得所有任务中的最大延迟最小。

定义第i个任务的完成时间为fi，第i个任务的延迟时间为

定义最大延迟时间，总体目标即为最小化

贪心策略：Earliest Deadline First (EDF)策略

证明：

设为贪心算法产生的调度，设为任意最优解调度。

如果，证毕。

否则，考虑中第一个不同的调度任务为第个。

即，，

在中，若，则交换二者，之前和之后的延迟时间都不受影响，

若两个任务的ddl都足够，则交换前后的延迟时间都是0，延迟不变。

否则，交换后会减小两个任务的延迟时间。所以交换后最大延迟时间至少不会增加。

不断在中执行交换，即若存在两个相邻的任务，前者的ddl大于后者的ddl，则交换他们。

每次交换，最大延迟时间不会增加，且最终也会变成（类似冒泡排序），因此是最优解。

霍夫曼编码

统计字符的出现频率

选择字符池中频率最低的两个字符合并，新字符的概率为二者频率之和，将新字符扔进字符池。

不断重复上述操作，直到字符池为空。

根据合并过程，我们可以构建出一棵霍夫曼树。

从叶节点向上标注编码长度，同一层的编码长度相等，且由同一层节点个数和下一层的编码长度决定，即。

lecture13动态规划

动态规划

分治和贪心的子问题不重叠，动态规划子问题通常重叠

上讲中的区间调度问题，每个活动的权重都是相同的，若给每个活动赋予不同的权重，就不能简单的通过dll优先进行调度了。

方法：

将所有活动按结束时间排序，使得

定义是满足最大的整数

定义是仅考虑活动的最优调度的权重之和。

如果没有调度活动，则

即为所有活动的最优调度

考虑活动

若不在当前最优调度中，则

若在当前最优调度中，则

令即为局部最优解

空间换时间：

保存一个前导指针，指向的来源，即或

生成调度活动：

get-schedule() {
    j = n;
    sched = empty;
    while (j > 0) {
        if (pred[j] == p[j]) {
            put j to the front of sched
        }
        j = pred[j];
    }
    return sched;
}

时间复杂度

最长公共子序列

序列，表示中前个数组成的序列

定义，，即为所求

若，则

若，则

时间复杂度：填满需要，回溯找到需要，

链式矩阵乘法

给定一个矩阵序列和维度，其中的维数为，确定矩阵乘法的顺序，使数字乘法次数最少。

定义是矩阵到相乘的结果，则是的矩阵。

定义计算所需要的最少的数字乘法次数

有，$m(i,j)={\min}{i\leq k<j}(m(i,k)+m(k+1,j)+p{i-1}p_kp_j)$

由于递归依赖关系，先计算长度为的链（），再长度为的链（），最终得到长度为的链

无限背包问题

所有物品的数量没有上限

一共有种物品，背包容量为

物品占用的空间为，价值为

定义是容量为的背包装载的最大价值（最优解）

则

时间复杂度

创建一个集合数组，在更新后更新对应的集合

最终即为物品的选取方案

lecture14动态规划2

0-1背包问题

所有物品都有只有1个

一共有个物品，背包容量为

物品占用的空间为，价值为

定义为大小为的背包只使用前个物品的最优解

有

若前个物品不用物品，

若前个物品使用物品，

则

Zero-One-Knapsack(W, n, w, v):
    K[x,0] = 0 for all x = 0,…,W
    K[0,i] = 0 for all i = 0,…,n
    for x = 1,…,W:
        for j = 1,…,n:
            K[x,j] = K[x, j-1]
                if wj ≤ x:
                    K[x,j] = max{ K[x,j], K[x – wj, j-1] + vj }
    return K[W,n]

时间复杂度：

最大独立集

独立集：顶点的集合，它们之间没有边

最大独立集：顶点上有权重的图，权重最大的独立集

这是一个NP-complete问题

但我们可以假设这个图是一棵树，我们的问题变为在树中寻找最大独立集。

定义为根为的树中最大独立集的权值，考虑每个子树的树根在不在最大独立集当中。

若当前的树根在最大独立集中，那么他的两个孩子就肯定不在，继续考虑他孩子的孩子。

若当前树根不在最大独立集中，则考虑他的两个孩子。

则$A[u]=\max{$

可以再维护一个

则

如果是叶节点，

Floyd-Warshall算法

任意两顶点之间的最短路径（不同于Dijkstra的固定起点）

是的数组，for

，for all ，for all

，for all ，for all

，for all in

时间复杂度

NP困难问题

• P：有一个多项式时间算法来解决的决策问题

  • 对于X的所有实例s，如果s是一个YES实例, A(s) = YES，则算法A解决了问题X
  • 如果对于每个实例s, A(s)最多以多项式(|s|)步结束，则A以多项式时间运行。

• NP：存在多项式时间的证明的决策问题。

  • 算法C(s,t)证明问题X，如果对于每个YES实例s，存在一个证据t使得C(s,t) = YES，并且|t| = 多项式(|s|)。

• EXP：有指数时间算法的决策问题

• ，

• NP-hard：对于问题Y，任意NP问题X，都满足，则Y是NP-hard问题。

  • 哈密尔顿图是NP-complete问题

• NP-complete(NPC)：在NP中的NP-hard问题。