Algorithm Review


本科的时候上过《数据结构与算法》课,但彼时天真的以为搞安全不需要懂太多算法,也就糊弄过去了,没想到读研还是没能逃过,此时也已经意识到算法的重要性,于是作了此文,一来是复习本科阶段学了但又遗忘的知识,二来是以此做为研一《高级算法设计与分析》课程的期末复习笔记。三是希望能给正在看此文的你一点点帮助吧。

算法引论

什么是算法

  • 算法是求解问题的一系列计算步骤,用来将输入数据转换成输出结果 从蛮力到策略
  • 数据结构是数据的组织与存储:从杂乱无章到井然有序
  • 算法 + 数据结构 = 程序

算法的特征

  • 输入性:必须有0个或多个输入(待处理信息)

  • 输出性:应有一个或多个输出(已处理信息)

  • 确定性:组成算法的每条指令是清晰的、无歧义

  • 有穷性:算法必须总能在执行有限步之后终止

什么是好算法

  • 正确性:符合语法、编译通过;

  • 健壮性:能辨别不合法的输入并做适当的处理,不至于异常退出(崩溃)

  • 可读性:结构化 + 准确的命名 + 注释

  • 效率性:速度尽可能快;存储空间尽可能少

算法和程序的差别

  • 程序是算法用某种程序语言的一个具体实现
  • 程序是用来给计算机读的,算法是给人来读的
  • 程序可以不满足算法的有穷性。

判断问题和优化问题

经典算法分析

贪心算法:逐步建立一个解决方案,具体地优化一些局部准则。

分治:将一个问题分解成独立的子问题,求解每个子问题,并将子问题的解组合起来形成原问题的解。

动态规划:把一个问题分解成一系列相互重叠的子问题,并为越来越大的子问题建立解决方案。

算法复杂度

渐近符号

Θ,O,Ω的图像表示

Θ(渐近紧确界):

  • 存在正常数 c1 , c2和 n0 使得对所有n ≥ n0有:c2 g(n) ≤ f(n) ≤ c1g(n),记为f(n) ∈Θ(g(n))

  • 例如:n2+3n+2∈Θ(n2)、n(n-1)/2∈Θ (n2)、4n2+5 ∈Θ (n2)

O(渐近上界):

  • 存在正常数 c 和 n0 使得对所有n ≥ n0有:f(n) ≤ cg(n),记为f(n) ∈O(g(n))

  • 例如:n ∈O(n2)、100n+5 ∈O(n2)、n(n-1)/2 ∈O(n2)

Ω(渐近上界):

  • 存在正常数 c 和 n0 使得对所有n ≥ n0有:f(n) ≥ cg(n),记为f(n) ∈Ω(g(n))
  • 例如:n3∈Ω (n2)、n(n+1)∈Ω (n2)、4n2+5 ∈Ω (n2)

复杂度

时间复杂度具有「最差」、「平均」、「最佳」三种情况,分别使用 O , Θ , Ω 三种符号表示。

根据从小到大排列,常见的算法时间复杂度主要有:

O(1) < O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

最常用的关系式

  • 多项式. a0 + a1n + … + adnd = Θ(nd) 其中 ad > 0.

  • 对数. log a n = Θ(log b n) 其中 a, b > 0为常数.

  • 对数. 对任意 a, b > 0, (log n)a = O(nb).

  • 指数. 对任意 r > 1 和 d > 0, nd = O(rn).

渐进增长率比较

方法1:定义法

找到正常数 c 和 n0 使得对所有n ≥ n0 有 f(n) ≤ cg(n),则f(n) = O(g(n))

方法2:极限法

比较两个函数f(n)和g(n)的渐近增长率时,可以对两个函数相除,然后令变量 n 趋向于无穷,看这个极限值是无穷大还是一个大于零的常数还是趋向于0.

  • 前两种情况意味着f(n) ∈ O(g(n))
  • 后两种情况意味着f(n) ∈ Ω(g(n))
  • 第二种情况意味着f(n) ∈ Θ(g(n))

方法2:取对数法

对于比较难的比较的两个函数,我们可以对它们同时取对数后再进行比较

常见对数公式:

logam*n = logam + logan

loga(m/n) = logam - logan

logamn = nlogam

logan√m = (1/n)logam

真题练习

题目1

判断 f(n) = 32n2 + 17n + 32 属于哪些渐近增长阶
O(n), Ω(n), Θ(n), O(n2), Θ(n2), Ω(n2),O(n3), Ω(n3), Θ(n3).

f(n) 属于 Ω(n),O(n2), Ω(n2), Θ(n2) ,O(n3) .
f(n) 不属于 O(n), Θ(n), Ω(n3), Θ(n3).

题目2

f1(n) = √n +100logn = O(√n)

f2(n) = 2logn*2loglogn = nlogn

f3(n) = 100logn +nlog3 = O(n)

f4(n) = O(3n)、f5(n) = 100log2n、f6(n) = O(n!)

因此 f5(n) < f1(n)< f3(n) < f2(n) < f4(n)<f6(n)

题目3

f1(n) = n(lognn)

f2(n) = logn

f3(n) = log5n

f4(n) = n1/5、f5(n) = n1/10log50n

f2(n)< f3(n)、f3(n) < f1(n)、f4(n)< f5(n) 、f4(n) < f2(n)、f3(n) < f5(n)

因此 f4(n)< f2(n)< f3(n) < f5(n) < f1(n)

题目4

贪心算法

算法分析

贪心算法就是用计算机模拟一个「贪心的人」来做出决策。这个贪心的人是目光短浅的,他每次总是:

  • 只做出当前看来最好的选择
  • 只看眼前的利益,而不考虑做出选择后对未来造成的影响
  • 并且他一旦做出了选择,就没有办法反悔(不可回溯)

总结:在对问题求解时,总是做出在当前最好的选择。也就是说并不从整体最优考虑,他所做出的是在某种意义上的局部最优解。 因此贪心算法不是对所有问题都能得到整体最优解。

应用场景

解决一个问题需要多个步骤,每一个步骤有多种选择。想清楚局部最优,想清楚全局最优,感觉局部最优是可以推出全局最优,并想不出反例,那么就试一试贪心

解题步骤

贪心算法一般分为如下三步:

  • 1.分解:将问题分解为若干个子问题
  • 2.解决:找出适合的贪心策略,求解每一个子问题的最优解
  • 3.合并:将局部最优解堆叠成全局最优解

正确性证明

贪心算法最难的部分不在于问题的求解,而在于正确性的证明,常用的证明方法有归纳法反证法

经典应用

区间调度(活动安排)

问题描述:设有 n 个活动的集合 E={1, 2, …, n},其中任意活动 i 都有一个起始时间 si 和一个结束时间 fi 。如果选择了活动 i,则它在半开时间区间 [si , fi) 内占用资源。若区间 [si , fi) 与区间 [sj , fj) 不相交,则称活动 i 与活动 j 是相容的。每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

理论分析

例如有如下 8 个活动,s[i] 代表第 i 个活动开始时间,f[i] 代表第 i 个活动的结束时间,选出最大的相容活动子集合

1、分析问题

本问题为选择尽可能多的相容活动

约束条件是下一个活动开始时间大于或等于上一个活动结束时间 s[i] >= f[j]

2、选择适合的贪心策略

可能的贪心选择策略:

  • ①每次选择开始时间最早的活动
  • ②每次选择持续时间最短的活动
  • ③每次选择结束时间最早的活动

依次证明上面哪种思路可以应用于本题,为了方便,我们用不同颜色的线条代表每个活动,线条的长度就是活动所占据的时间段,蓝色的线条表示我们已经选择的活动;红色的线条表示我们没有选择的活动。

每次选择开始时间最早的活动(不是最优解

  • 证明(反证法):
    • 先来看开始最早,很容易找到反例,如图贪开始最早,那么选择蓝色的活动,显然不是最优解,因为选择红色的活动,可以参加2次,而蓝色活动只能参加一次
    • 例如我们选择了10号活动(开始时间2点,结束时间13点);2号活动待选择(开始时间3点,结束时间5点);
      则会出现上图所示的情况,这显然违背了约束条件。

每次选择持续时间最短的活动(不是最优解

  • 证明(反证法):
    • 贪持续时间最短,显然也不对,特殊情况发生在最短时间的活动,位置刚好和其他活动冲突,如果选择时间最短的活动,也不是最优解。
    • 例如我们选择了2号活动(开始时间3点,结束时间5点);1号活动待选择(开始时间1点,结束时间4点);
      则会出现上图所示的情况,这显然也违背了约束条件。

每次选择结束时间最早的活动(最优解

要证明一个算法是错的非常简单,要证明是对的却非常难。对于贪心算法的证明,一是使用归纳法,二是采用反证法。像上面两种策略,我们实际上就用到了反证法。那么怎么证明贪心算法是对的呢?

3、计算最优解

求解思路:将活动按照结束时间进行从小到大排序。挑选出结束时间尽量早的活动,并且满足后一个活动的起始时间晚于前一个活动的结束时间,全部找出这些活动就是最大的相容活动子集合。首先检查活动 i 是否与当前已选择的所有活动相容。若相容,活动 i 加入已选择活动的集合中,否则不选择活动 i,而继续检查下一活动与集合中活动的相容性。若活动 i 与之相容,则 i 成为最近加入集合 的活动,并取代活动 j 的位置。

图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。

因此最大的相容活动子集合为{1,4,8,11}

代码实现
#include <iostream>
using namespace std;

void GreedyChoose(int len,int *s,int *f,bool *flag) {
  flag[0] = true;
  int j = 1;
  for(int i=2;i<len;++i)
    if (s[i] >= f[j]) {
      flag[i] = true;
      j = i;
    }
    else flag[i] = false;
}

int main(int argc, char* argv[]) {
  int s[11] ={1,3,0,5,3,5,6,8,8,2,12};
  int f[11] ={4,5,6,7,8,9,10,11,12,13,14};

  bool mark[11] = {0};

  GreedyChoose(11,s,f,mark);
  for(int i=0;i<11;i++)
    if (mark[i])
      cout<<i+1<<" ";
  //system("pause");
  return 0;
}

找零钱的问题

单源最短路径中的Dijkstra算法

最小生成树的Prim算法

最小生成树的Kruskal算法

Huffman编码


真题练习

LeetCode5.分发饼干

题目

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.    

提示:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

思路

为了了满足更多的小孩,就不要造成饼干尺寸的浪费。

这里的局部最优就是小饼干喂给胃口小的或者大饼干喂给胃口大的,充分利用饼干尺寸喂饱小孩,全局最优就是喂饱尽可能多的小孩

可以尝试使用贪心策略,先将饼干数组和小孩数组排序。

然后从前向后或者从后向前遍历小孩数组,用小饼干满足胃口小的或者大饼干优先满足胃口大的,并统计满足小孩数量。

解答

// 优先考虑饼干,小饼干先喂饱小胃口
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        for(int i = 0, j = 0; i < g.length && j < s.length; j++){
            if(g[i] <= s[j]){
                count++;
                i++;
            }
        }
        return count;
    }
}
// 优先考虑胃口,先喂饱大胃口
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int j = s.length - 1;
        // 遍历胃口
        for (int i = g.length - 1; i >= 0; i--) {
            if(j >= 0 && g[i] <= s[j]) {
                count++;
                j--;
            }
        }
        return count;
    }
}

分治算法

算法分析

主定理

主定理适用于求解右边递归式算法的时间复杂度:T(n) = aT(n/b) + f(n)

其中:

  • n:问题的规模大小
  • a:原问题的子问题个数
  • n/b:每个子问题的大小
  • f(n):将原问题分解成子问题和将子问题的解合并成原问题的解的时间。

定理:设 a >= 1,b >=1 为常数,设 f(n) 为一函数,T(n) 由以下递归式给出 T(n) = aT(n/b) + f(n),则T(n)可能有如下渐近界:

  • ①若 f(n) < nlogba 时,存在 ε > 0,有 f(n) = O(nlogba-ε),则 T(n) = Θ(nlogba)

  • ②若 f(n) = nlogba 时,有 f(n) = Θ(nlogba),则 T(n) = Θ(nlogbalogn)

  • ③若 f(n) > nlogba 时,存在 ε > 0,有 f(n) = Ω(nlogba+ε),且满足 af(n/b) ≤ cf(n), c<1,则 T(n) = Θ(f(n))

来几道例题:

例一:求解递推方程 T(n) = 9T(n/3) + n

​ a = 9,b = 3 ,f(n)=n,nlogba = nlog39 =n2

​ n < n2 ,即f(n) < nlogba 存在 f(n) = O(nlogba-ε)=O(n2-1),ε=1。

​ 满足主定理的条件1,因此 T(n)=Θ(nlogba)=Θ(n2)

例二:求解递推方程 T(n) = T(2n/3) + 1

​ a = 1,b = 3/2,f(n)=1,nlogba = nlog3/21 = n0 = 1

​ f(n) = nlogba ,满足主定理的条件2,所以T(n)=Θ(nlogbalogn)=Θ(logn)

例三:求解递推方程 T(n) = 3T(n/4) + nlogn

​ a = 3,b = 4,f(n) = nlogn,nlogba = nlog34

​ nlogn > nlog43 ,再判断是否满足不等式:af(n/b) ≤ cf(n),代入f(n)=nlogn

​ (3n)/4log(n/4)和cnlogn,当 c ≥ 3/4 即可满足 af(n/b) ≤ cf(n) 的关系

​ 即满足主定理的条件3,所以T(n) = Θ(f(n)) = Θ(nlogn)

计数逆序

真题练习

题目1

(1) a = 9 , b = 6 , f(n) = Θ(nlogn), nlogba = nlog69

Θ(nlogn) < Θ(nlog69),即f(n) < Θ( nlogba),适用于主定理第一条

因此 f(n) = Θ(nlogba) = Θ(nlog69 )

(2)。。。

(3) a =4 ,b = 2 ,f(n) = Θ(n2),nlogba = nlog24 = 2

f(n) = Θ( nlogba ),适用于主定理第二条

因此 f(n) = Θ(nlogbalogn) = Θ(n2logn)

动态规划

算法分析

动态规划问题分析是自顶而下的思路,但是算法实现却是自底而上的策略。

经典应用

带权区间调度

问题描述:给定若干个工作 job 的开始时间 sj、结束时间 fj 和权重 vj(可以理解成重要程度),求出能完成的最大的工作权重(尽可能地完成更重要的工作),且必须满足各个工作相容(工作安排的时间没有重叠)。

例如有如下三个工作:

job s f v
工作1 0 3 4
工作2 5 6 5
工作3 2 8 10
由不带权重的区间调度方法(贪心),按最早结束时间且相容选择工作,这里就选出{工作1, 工作2},能实现的最大权重是4+5=9。但是,选择{工作3}权重可达到10,因此最早结束时间的贪心策略在带权区间调度问题里已不适用。那么如何求相互兼容工作的最大权值子集呢?

理论分析

1、分析最优子结构

  • 工作 job 按照完成时间升序排列:f1≤f2≤…≤ fn
  • 定义两个参数:p(j)OPT(j)

p(j) = 与工作 j 相容的最大的工作 i 且 i < j,也就是说 i 是 j 左边的在 j 开始之前结束的区间。

如下图:

p(1) = 0,p(2) = 0,p(3) = 0,p(4) = 1

p(5) = 0,p(6) = 2,p(7) = 3,p(8) = 1

OPT(j)表示前 j 个工作 ( 1,2,3,…,j )的最大的工作权重。

OPT(j) 显然有两种方案:

  • ①选择 j 工作
    • 如果选择工作 j,原问题退化成 vj+OPT(P(j)),选择了 j 活动,则下一个活动为不能和 j 活动冲突的最大活动 P(j)
  • ②不选择 j 工作
    • 如果不选择工作 j,原问题退化成 OPT(j-1),即从(1,2,3…j-1)中找最优解

2、建立递推公式

递推如下:

3、计算最优值、构造最优解

例如:给定如下8个候选活动的开始时间、结束时间和权重

依据递推公式,计算出 p(j)OPT(j)

j 1 2 3 4 5 6 7 8
p(j) 0 0 0 1 0 2 3 5
OPT(j) 12 20 23 25 26 40 40 42

p(8) = 5,与 活动8 相容的最大活动为 5

p(5) = 0,与 活动5 相容最大活动没有

因此选择活动 8 和 5

OPT(2) = max{ OPT(1) ,v2 + OPT(p(2)) } = max{12,20} = 20

OPT(4) = max{ OPT(3) ,v4 + OPT(p(4)) } = v4 + OPT(1) = 13 + 12 = 25

OPT(7) = max{ OPT(6) ,v7 + OPT(p(7)) } = max{40,34} = 40

OPT(8) = max{ OPT(7) ,v8 + OPT(p(8)) } = max{40,42} = 42

因此最大权重之和为42

代码实现
#include <iostream>
using namespace std;

typedef struct {
    int iStartT;
    int iFinshT;
    int iWight;
}TASK_INFO;

void CreatWeightedScheduling(TASK_INFO *, int);                    //创建每个任务
void PrintWeightedScheduling(TASK_INFO *, int);
void DynamicScheduling(TASK_INFO *, int **, int);                //用动态算法求解最大权重问题
void FindSolution(TASK_INFO *, int **, int, int *);                //寻求最大权重任务的集合    



void CreatWeightedScheduling(TASK_INFO *schedule, int taskNum)
{
    cout << "请逐个输入任务的开始时间s、结束时间f、权重v\n";
    for (unsigned int i = 0; i < taskNum; i++)
    {
        cout << "Task " << i + 1 << " information: ";
        cin >> schedule[i].iStartT >> schedule[i].iFinshT >> schedule[i].iWight;
    }
}

void PrintWeightedScheduling(TASK_INFO *schedule, int taskNum)
{
    for (unsigned int i = 0; i < taskNum; i++)
    {
        cout << "Task" << i + 1 << ":\t" << schedule[i].iStartT << "\t" << schedule[i].iFinshT << "\t" << schedule[i].iWight << endl;
    }
}


/*****************************************************************************************************
** key: j号task的开始时间,即startArray[j]
** finsh[] && currentIndex: 查找“j号task的开始时间”在j-1号之前的任务的结束时间finishArray[1...j-1]
*****************************************************************************************************/
int binarySereach(int key, int finsh[], int currentIndex)
{
    int low = 1, high = currentIndex;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == finsh[mid])                                    //找到即返回Index
            return mid;
        else if (key < finsh[mid]) {                            //key小于所有的finshTime,即没有一个任务相容
            high = mid - 1;
            if (high < low)
                return 0;
        }
        else {                                                    //key大于所有的finshTime,最大的相容的,即high
            low = mid + 1;
            if (low > high)
                return high;
        }
    }
    return 0;
}

void DynamicScheduling(TASK_INFO *schedule, int **compute, int taskNum)
{
    int* startArray = new int[taskNum + 1];                                                //将每个任务的开始、结束时间转存下,方便计算P(j)
    int* finishArray = new int[taskNum + 1];
    for (unsigned int i = 1; i < taskNum + 1; i++)
    {
        startArray[i] = schedule[i - 1].iStartT;
        finishArray[i] = schedule[i - 1].iFinshT;
    }

    //compute P(j) & OPT(j)
    for (unsigned int j = 1; j < taskNum + 1; j++) {
        //P(j)
        compute[0][j] = binarySereach(startArray[j], finishArray, j - 1);

        //OPT(j):OPT(j) ? Wj+OPT(P(j))
        if (compute[1][j - 1] > schedule[j - 1].iWight + compute[1][compute[0][j]])            //第一个任务信息在0号内存单元的,所以是j-1
            compute[1][j] = compute[1][j - 1];
        else
            compute[1][j] = schedule[j - 1].iWight + compute[1][compute[0][j]];
    }
    delete[] startArray;                        //从理论上讲,new的内存必需要delete才能释放,不知道编译器有优化没?,还是显示的释放下
    delete[] finishArray;
}

int g_i = 0;
void FindSolution(TASK_INFO *schedule, int **compute, int j, int* path)
{
    if (j == 0)
        return;
    else if (schedule[j - 1].iWight + compute[1][compute[0][j]] > compute[1][j - 1])    //后面值大于前面的,则加入;否则j-1
    {
        path[g_i++] = j;
        return FindSolution(schedule, compute, compute[0][j], path);
    }
    else
        return FindSolution(schedule, compute, j - 1, path);
}


int main()
{
    int taskNum = 0;
    cout << "请输入你要分配总任务数: ";
    cin >> taskNum;

    TASK_INFO *schedule = new TASK_INFO[taskNum];
    CreatWeightedScheduling(schedule, taskNum);


    //////////////////////////////////////////////////////////////////////////////////////////////////////
     //用动态算法求解最大权重问题
    //compute[2][]:first clow means P(j); second clow means OPT(j)
    int **compute = new int*[taskNum + 1];
    for (unsigned int i = 0; i < 2; i++)                                            //分配内存及置0
        compute[i] = new int[taskNum + 1];
    for (unsigned int i = 0; i < 2; i++)
        for (unsigned int j = 0; j < taskNum + 1; j++)
            compute[i][j] = 0;

    DynamicScheduling(schedule, compute, taskNum);

    cout << "\n";
    for (unsigned int i = 0; i < 2; i++) {                                            //输出P(j)、OPT(j)
        if (i == 0)
            cout << "  P(j):  ";
        else
            cout << "OPT(j):  ";
        for (unsigned int j = 1; j < taskNum + 1; j++)
            cout << compute[i][j] << "\t";
        cout << "\n";
    }
    cout << "\n最大权重之和:" << compute[1][taskNum] << endl;

    //////////////////////////////////////////////////////////////////////////////////////////////////////
    //输出任务
    int* path = new int[taskNum];                                                    //存储任务的数组
    for (int i = 0; i < taskNum; ++i)
        path[i] = 0;
    FindSolution(schedule, compute, taskNum, path);
    cout << "最优活动子集:";
    for (unsigned int i = 0; i < taskNum && path[i] != 0; i++)
        cout << path[i] << "  ";

    cout << "\n";
    //PrintWeightedScheduling(schedule, taskNum);

    for (unsigned int i = 0; i < 2; i++)
    {
        delete[] compute[i];
    }
    delete[] compute;
    delete[] schedule;
    delete[] path;
}

真题练习
理论题目1

p(j) 为与工作 j 相容的最大的工作 i 且 i < j 。OPT(j)表示前 j 个工作 ( 1,2,3,…,j )的最大的工作权重。则递归关系式为:

依据递推公式,计算出 p(j)OPT(j)

因为 OPT(17) = 50 ,因此最大权重之和为 50

OPT(17) = OPT(16) = OPT(15) = 50 ,选择活动 15,p(15) =13;

OPT(13) = OPT(12) = 45 ,选择活动 12,p(12) = 7;

OPT(7) = OPT(6) = 25 ,选择活动 6,p(6) = 3;

OPT(3) = 18 ,p(3) = 0,选择活动 3,且选择完毕。

因此最优活动子集为 3、6、12、15

0-1背包问题

更新中。。。

算法之动态规划,问题三:0 1 背包问题_我爱加菲猫-CSDN博客

最长公共子序列

问题描述︰给定两个字符串,求解这两个字符串的最长公共子序列(LCS)。如: X={1,5,2,8,9,3,6},Y={5,6,8,9,3,7},其最长公共子序列为{5,8,9,3},最长公共子序列长度为4。那么如何求解呢?

理论分析

1、分析最优子结构

设序列 X={x1, x2, …, xi}Y={y1, y2, …, yj} 的最长公共子序列为 Z={z1, z2, …, zk},则

  • ①若 xi=yj ,则 zk=xi=yjZk-1 是 Xi-1 和 Yj-1 的最长公共子序列;

  • ②若 xi≠yjzk≠xi ,则 Zk 是 Xi-1 和 Yj 的最长公共子序列;.

  • ③若 xi≠yjzk≠yj ,则 Zk 是 Xi 和 Yj-1 的最长公共子序列。

2、建立递推公式

c[i][j]表示 Xi={x1, x2, …, xi}Yj={y1, y2, …, yj} 的最长公共子序列的长度,那么得到以下的递推公式:

递推公式代码版

for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            c[i][0] = 0;
            c[0][j] = 0;
        }
    }
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        if(X[i] == Y[j]){
            c[i][j] = c[i-1][j-1] + 1;
        }
        else{
            c[i][j] = max(c[i - 1][j], c[i][j - 1]);
        }     
    }

3、计算最优值

假设 X={A,B,C,E} 和 Y={B,D,C,E}

根据上方递推公式得到下表:

c[i][j] 0 1B 2D 3C 4E
0 0 0 0 0 0
1A 0 0 0 0 0
2B 0 1 1 1 1
3C 0 1 1 2 2
4E 0 1 1 2 3

C[2][0] 处,j = 0 ,此时根据公式C[2][0]= 0

C[2][1] 处,B = B,即 xi=yj ,此时根据公式C[2][1]=C[1][0]+1=0+1=1

C[2][2] 处,B ≠ C,即 xi≠yj ,此时根据公式C[2][2]=max{C[2][1],C[1][2]}=1

根据最右下角的值(c[][]),我们可以知道最长公共子序列长度为3

最优值代码版:

int LCSLength(char *X,char *Y)
{
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            c[i][0] = 0;
            c[0][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(X[i] == Y[j]){
                c[i][j] = c[i-1][j-1] + 1;
            }
            else{
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }     
        }
     return c[n][m];
}

4、构造最优解

b[i][j]记录c[i][j]的值是由哪个子问题的解得到的

  • if(X[i]==Y[j]) 用b=1代表

  • if(X[i]!=Y[j]) 用b=2代表

b[i][j] 0 1B 2D 3C 4E
0 0 0 0 0 0
1A 0 2 2 2 2
2B 0 1 2 2 2
3C 0 2 2 1 2
4E 0 2 2 2 1
c[i][j] 0 1B 2D 3C 4E
0 0 0 0 0 0
1A 0 0 0 0 0
2B 0 1 1 1 1
3C 0 1 1 2 2
4E 0 1 1 2 3

处则为最长公共子序列{B,C,E}

代码实现
//自底向上计算最优值,并记录相关信息
void LCSLength(){
    int i,j;
    for(i=1; i<=m; i++){
        c[i][0] = 0;
    }
    for(i=1; i<=n;i++){
        c[0][i] = 0;
    }
    for(i=1; i<=m; i++){
        for(j=1; j<=n; j++){
            if(x[i] == y[j]){
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            }else if(){
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }else{
                c[i][j] = c[i][j-1];
                b[i][j] = 2;
            }
        }
    }
}

void LCS(int i,int j,char *x,int **b){
    if(i == 0 || j == 0){
        return;
    }
    if(b[i][j] == 1){
        LCS(i-1,j-1,x,b);
        cout<
真题练习
理论题目1

给定两个字符串A和B,长度分别为m和n,设计动态规划算法找出它们最长公共子序列长度,并给出最长公共子序列。例如:A = “HelloWorld”,B = “loopbird”,则A与B的最长公共子序列为”loord”,返回的长度为5。

动态规划经典——最长公共子序列问题 (LCS)和最长公共子串问题 - Excaliburer - 博客园 (cnblogs.com)

理论题目2

设计一个O(n^2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。

力扣1143

待更新。。。

动态规划之最长公共子序列问题详解(解题思路+算法思想+表格详解)

最长公共子序列-II_牛客题霸_牛客网 (nowcoder.com)

NC92 最长公共子序列-Java_快乐的大儿童附体-CSDN博客

在线练习题Alchemist (alchemist-al.com)

矩阵连乘

理论分析

问题描述:给定 n 个矩阵 {A1,A2,…,An} ,其中 Ai 与 Ai+1 是可乘的,用加括号的方法表示矩阵连乘的次序,不同加括号的方法所对应的计算次序是不同的,求矩阵连乘的最佳计算次序。

例如,矩阵连乘积 A1A2A3 有以下 2 种加括号方式:A1(A2A3),(A1A2)A3,所以那种加括号方式是最优的呢?

说明:

  • 1.矩阵 A 和矩阵 B 可乘的条件:矩阵 A 的列数 = 矩阵 B 的行数
  • 2.设矩阵 A 是 p × q 的矩阵,B 是 q × r 的矩阵,乘积结果 C 是 p × r的矩阵,计算量是 p * q * r

1、分析最优子结构

将矩阵连乘的积 Ai Ai+1 … Aj 简记为A[i][j]Ai 的维度记为 pi-1 × pi,那么上述问题变为求解 A[1][n]的最佳计算次序。

A[1][n]的最佳计算次序:设这个计算次序在矩阵 AK (1<=k<n) 和 AK+1 之间将矩阵链断开,则相应的加括号方式:( Ai Ai+1 … Ak )( Ak+1Ai+1 … An ),依此计算顺序,总计算量为 Ai Ai+1 … Ak 的计算量加上 Ak+1Ai+1 … An 的计算量,再加上 ( Ai Ai+1 … Ak ) 和 ( Ak+1Ai+1 … An )相乘的计算量。即 A[1][n] = A[1][k] + A[k+1][n] + pi-1pkpj

2、建立递推公式

设计算 A[i][j] (i<=j) 所需的最少乘法次数为 m[i][j],那么得到以下的递推公式:

3、计算最优值

例如,要计算矩阵连乘积A1A2A3A4A5A6,其中各矩阵的维数分别为:

A1 A2 A3 A4 A5 A6
30x35 35x15 15x5 5x10 10x20 20x25

依据递推公式,按照图 a 的次序,计算出 m[i][j]

★最优值:本题是求解 A[1][6] 的最佳计算次序,即求m[1][6] 。由图 b 可知, m[1][6] =15125,因此矩阵连乘积A1A2A3A4A5A6 的最优值为 15125

4、构造最优解

若将对应m[i][j]的断开位置k记为s[i][j],计算出最优值m[i][j]后,可递归地由s[i][j][][]构造出相应的最优解。

例如,m[2][5] = m[2][3] + m[4][5] + p1p3p5 ,则 k = 3,因此 s[2][5] = 3

★最优解:

s[1][6] = 3 ,因此矩阵链在A3和A4之间断开,则加括号方式为 (A1A2A3)(A4A5A6 )

s[1][3] = 1,因此矩阵链在A1和A2之间断开,则加括号方式为 (A1(A2A3))(A4A5A6 )

s[4][6] = 5,因此矩阵链在A5和A6之间断开,则加括号方式为 (A1(A2A3))((A4A5)A6 )

因此最优解为 (A1(A2A3))((A4A5)A6 )

代码实现
#include <iostream>
using namespace std;
#define N 100
int s[N][N], m[N][N];  //s存储切割位置,m存储最优值 

void MatricChain(int *p , int n) {//p矩阵维数数组,n为矩阵个数
    for (int i = 1; i <= n; i++) {//初始化,对角线上的计算量和加括号的位置为0
        m[i][i] = 0;
        s[i][i] = 0;
    }
    for (int r = 2; r <= n; r++) {//r为矩阵链的长度
        for (int i = 1; i <= n - r + 1; i++) { //i为首矩阵的序号
            int j = i + r - 1; //j为尾矩阵的序号
            m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];//首先尝试在矩阵 i 处分开
            s[i][j] = i;
            for (int k = i + 1; k < j; k++) {  
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 然后尝试在矩阵 k 处分开 (i<=k<j)
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
            }
        }
    }
}
void Traceback(int i, int j) {
    if (i == j) {
        return;
    }
    int k = s[i][j];
    Traceback(i, k); 
    Traceback(k + 1, j);
    cout << "A" << "[" << i << ":" << k << "]" << "×" << "A""[" << (k + 1) << ":" << j << "]"<<"  " ;
}

int main(){
    int p[] = {30,35,15,5,10,20,25};//矩阵维数
    int n = sizeof(p) / sizeof(int) - 1;//矩阵个数

    for(int i = 0; i < n; i++){
        cout << p[i]<<"×"<<p[i+1]<<"  ";
    }
    cout << "这" << n << "个矩阵连乘的最优值和最优解?" << endl;
    cout << endl;

    MatricChain(p,n);
    cout << "m[i][j]:" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << m[i][j] << "\t";
        cout << endl;
    }

    cout << endl;
    cout << "s[i][j]:" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << s[i][j] << "\t";
        cout << endl;
    }
    cout << endl;
    cout << "最少连乘次数(最优值):" << m[1][n] << "次。" << endl;
    cout << "最佳计算次序(最优解):" ;
    Traceback(1, n);
    cout << endl;
}

真题练习
理论题目1

(1)令计算A1 x A2 x A3 x … x An所需要的最少乘法次数为m[i, j] (3分)

​ 则递归关系式为 (5分,其中边界条件1分)

(2)

m(i, j) j = 1 j = 2 j = 3 j = 4 j = 5
i = 1 0 1440 3360 4000 5856
i = 2 / 0 2400 2800 4800
i = 3 / / 0 1600 2880
i = 4 / / / 0 3200
i = 5 / / / / 0

将对应m(i,j)的断开位置k记为s(i,j)

s(i, j) j = 1 j = 2 j = 3 j = 4 j = 5
i = 1 / 1 2 2 2
i = 2 / / 2 2 2
i = 3 / / / 3 4
i = 4 / / / / 4
i = 5 / / / / /

s(1,5) = 2 因此矩阵链在A2和A3之间断开,则加括号方式为 (A1A2)(A3A4A5)

s(3,5) = 4 因此矩阵链在A4和A5之间断开,则加括号方式为 (A1A2)((A3A4)A5)

最优加括号方式为

理论题目2
A1 A2 A3 A4 A5
3x7 7x8 8x5 5x12 12x10

计算矩阵连乘积A1A2A3A4A5最优值和最优解?

m[i][j] 1 2 3 4 5
1 0 168 288 468 828
2 0 280 700 1230
3 0 480 1000
4 0 600
5 0
s[i][j] 1 2 3 4 5
1 0 1 2 3 4
2 0 2 3 3
3 0 3 3
4 0 4
5 0

最少乘法次数为(最优值):828

s[1][5] = 4 因此矩阵链在A4和A5之间断开,则加括号方式为 (A1A2A3A4)A5

s[1][4] = 3 因此矩阵链在A3和A4之间断开,则加括号方式为 ((A1A2A3)A4)A5

s[1][3] = 2 因此矩阵链在A2和A3之间断开,则加括号方式为 (((A1A2)A3)A4)A5

最优加括号方式为(最优解): (((A1A2)A3)A4)A5

分段最小二乘法

网络流

网络流(Network-Flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流是图论中的一种理论与方法,研究网络上的一类最优化问题。

基础概念

网络(NetWork):是指一个有向图 G =(V,E),V 是图 G 中顶点的集合,E 是图 G 中边的集合。(运输水流的水管线路

  • 每条边 (u,v) ∈ E 都有一个权值 c(u,v) ,称之为容量(Capacity),当 (u,v) ∉ E 时 c(u,v) = 0。

  • 图 G 有两个特殊的点:源点 s ∈ V 和汇点 t ∈ V 。

(arc) 图 G 的边 (u,v)水管

源点 (Sources): 可以理解为起点。它会源源不断地放出流量,表示为 s 。(可无限出水的水厂

汇点 (Sinks):可以理解为终点。它会无限地接受流量,表示为 t 。(可无限接收水的小区

容量 (Capacity) 每条弧 (u,v) 的权值 c(u,v)水管规格。即可承受的最大水流量

容量网络: 拥有源点汇点且每条弧都给出了容量网络。(安排好了水厂、小区和水管规格的路线图

容量网络

流量 (Flow) 容量网络G中每条弧< u,v>上的实际流量 ,表示为 f(u,v)运输的水流量

​ 设 f(u,v)定义在二元组 (u∈V, v∈V) 上的实数函数满足:

  • 容量限制:对于每条边,流经该边的流量不超过该边的容量,即 f(u,v)≤c(u,v) (水流量超过了水管规格就爆了

  • 斜对称性:每条边的流量与其相反边的流量之和为 0 ,即 f(u,v)+f(v,u)=0 (可以暂且感性理解为矢量的正负)

  • 流守恒性:从源点流出的流量等于汇点流入的流量。即 ∀x ∈ V - {s,t},∑(u,x)∈Ef(u,x) = ∑(x,v)∈Ef(x,v) (对于所有的水管交界处,有多少水流量过来,就应有多少水流量出去)

流函数

流量网络: 拥有源点汇点且每条弧都给出了流量网络。(分配好了各个水管水流量的路线图)

流量网络

剩余容量(Residual):对于每条边,剩余容量(Residual) = 容量(Capacity) − 流量(Flow)。(表示水管分配了水流量后还能继续承受的水流量

残量网络: 拥有源点和汇点且每条弧还有剩余容量网络**残量网络 = 容量网络 − 流量网络。初始的残量网络即为容量网络。(表示了分配了一定的水流量后还能继续承受的水流量路线图

剩余网络

最大流

问题描述:我们有一张有向图,要求从源点 s 流向汇点 t 的最大流量(可以有很多条路到达汇点),这就是我们的最大流问题。

基础概念

网络的流量: 在某种方案下形成的流量网络汇点接收到的流量值。(小区最终接收到的总水流量

最大流(Maximum-Flow)网络的流量的最大值。(小区可接受到的最大水流量

最大流网络: 达到最大流流量网络。(小区接收到最大水流量的分配方案路线图

增广路径(Augmenting Path): 一条在残量网络中从 s 到 t 的路径,路径上所有边的残留容量都为正。
(可以成功从水厂将水送到小区的一条路线

增广路算法

当残量网络不包含增广路径时能求得最大流

例如如下网络:

初始容量网络 初始残量网络

寻找增广路径,增广路径上的流量为路径上最小容量

增广路径1(s→v2→v4→t) 残量网络1
s→v2→v4→t
增广路径2(s→v1→v3→t) 残量网络2
s→v1→v3→t
增广路径3(s→v1→v4→t) 最终残量网络

求流量网络,流量网络 = 初始容量网络 - 最终残余网络

流量网络

因此最大流为从 s 流出的流量 3 + 2 = 5 或者流入 t 的流量 2 +3 =5

但是这种算法并能保证一定能得到最大流,取决于你选择增广路径的顺序,我们同样以上方初始容量网络图为例,假设第一条增广路径选择 s→v1→v4→t,第二条增广路径选择 s→v1→v3→t,得到如下残量网络 和 流量网络

容量网络 残量网络 流量网络

因此该种方法求得最大流为从 s 流出的流量 4 + 0 = 4 或者流入 t 的流量 1 +3 =4,显然比刚刚求得的最大流 5 要小

总结:这种算法并能保证一定能得到最大流,取决于你选择增广路径的顺序,那么如何保证无论怎么选择增广路径仍然能求得最大流呢?且听我娓娓道来。

Ford-Fulkerson

FF 算法核心是引入反向边,有了反向边,哪怕之前选择的增广路径顺序不好,也有了一个后悔和改正的机会

FF算法复杂度:O(f*m) (f 为最大流,m为原图边的数量)

我们来改造上方的错误求解方法

增广路径1(s→v1→v4→t) 残量网络1 加入路径1反向边
增广路径2(s→v1→v3→t) 残量网络2 加入路径2反向边
增广路径3(s→v2→v4→v1→v3→t) 残量网络3 加入路径3反向边
相当于反悔v4→v1的3份流量 已经没有s到t的增广路径
移除所有反向边得最终残量图 流量图 最大流
因此最大流为从 s 流出的流量4 + 1 = 5 或者流入 t 的流量 2 +3 =5

最小割

:对于一个网络流图 G = (V,E),其割的定义为一种 点的划分方式:将所有的点 V 划分为 S 和 T 两个集合,其中源点 s ∈ S ,汇点 t ∈ T。割并不唯一

上图就为一种割,S = {s,v1,v2},V ={t,v3,v4},s的水无法流到t了

割的容量:我们的定义割 (S,T) 的容量 c(S,T) 表示所有从 S 到 T 的边的容量之和,即 c(S,T) = ∑u∈S,v∈Tc(u,v) 。

容量 c(S,T) = 2 + 2 + 2 = 6

容量 c(S,T) = 2 + 1 = 6

最小割:求得一个割 (S,T) 使得割的容量 c(S,T) 最小,最小割并不唯一。

最大流最小割定理:f(s,t)max = c(S,T)min 最小割的容量等价于最大流的流量

求解最小割: 把最小割问题等价于最大流问题,首先用 FF 算法求出最终残量网络图,然后把 s 能到达的点作为 S,把能到达 t 的点作为 T ,得到的就是最小割啦

初始容量网络 最终残量网络 最小割

因此最小割为{ {s,v1,v2,v4}{t,v3}},容量(最大流)为 5

真题练习

理论题目1

计算下图中从S到T的最大流和最小割.

增广路径:(S, A, B, T),网络流大小+6

增广路径:(S, C, E, T),网络流大小+4

增广路径:(S, A, D, E, T),网络流大小+3

增广路径:(S, B, E, T),网络流大小+3

最大流 6 + 4 + 3 + 3 = 16

最小割 [ {S,A,B,C,D,E},{T} ]

理论题目2

求如下有向图中s和t间的最小割,其中边上的数字表示边的容量。要求给出最少两个中间计算步骤(8分)。

将最小割问题转化为最大流问题

1增广路径:(s, u, t),流量值+5

2增广路径:(s, x, t),流量值+5

3增广路径:(s, v, w, t),流量值+8

4增广路径:(s, u, w, v, x, t),流量值+3

最小割为[ {s, u},{w, v, x, t} ] 容量为21

理论题目3

求下图中S和T间的最大流,要求给出最少两个中间计算步骤。

NP完备性理论

完备性理论

Reference📖

贪心算法

分治

动态规划

网络流

书籍

  • 《算法设计》 Kleinberg,J. ,Tardos,E. 著;张立昂,屈婉玲 译
  • 《计算机算法设计与分析》王晓东 著
  • 《算法图解》 Aditya Bhargava 著 ;袁国忠 译
  • 《大话数据结构》程杰 著

Sponsor❤️

本文实际上没有太多技术含量,但是从查阅资料,到画图构思,再到文章编写前后也经历了近 2 周的时间,在这个喧嚣浮躁的时代,个人博客越来越没有人看了,写博客感觉一直是用爱发电的状态。如果你恰巧财力雄厚,感觉本文对你有所帮助的话,可以考虑打赏一下本文,用以维持本博客的运营费用。

支付宝支付 微信支付

文章作者: 简简
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 简简 !
评论-----昵称和邮箱必填,网址选填
 本篇
Algorithm Review Algorithm Review
本科的时候上过《数据结构与算法》课,但彼时天真的以为搞安全不需要懂太多算法,也就糊弄过去了,没想到读研还是没能逃过,此时也已经意识到算法的重要性,于是作了此文,一来是复习本科阶段学了但又遗忘的知识,二来是以此做为研一《高级算法设计与分析》课
2021-10-07
下一篇 
LeetCode 算法入门 LeetCode 算法入门
在数学和计算机科学之中,算法是一个被定义好的、计算机可施行之指示的有限步骤或次序,常用于计算、数据处理和自动推理。作为一个有效方法,算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。
2021-07-26
  目录