返回

算法设计与分析

算法设计与分析

第1章 算法概述

image-20211112191628957
image-20211112191628957

算法具有下述四个性质:输入、输出、确定性和有限性

而程序是算法使用某中程序设计语言的具体实现

算法的复杂度有时间复杂度和空间复杂度之分。

image-20211112184755718
image-20211112184755718

上面的三个式子分别是时间复杂度最好、最坏和平均复杂度。

渐进符号:$O、\Omega、\theta$。分别表示渐进上界,渐进下界,同阶。

NP完全性理论

将可由多项式时间算法求解的问题看作易解的问题,需要超多项式时间的问题看作难解问题。于是人们提出了非确定性的图灵机计算模型,使得许多问题可以在多项式时间内求解。

对于每一个最优解问题,都有一个与之对应的判定问题。所有可以在多项式时间内求解的判定问题构成P类问题(多项式问题)。

非确定性算法的概念:非确定性算法将问题求解分为猜测和验证两个阶段,算法的猜测阶段是非确定性的,给出问题解的一个猜测。算法的验证阶段是确定性的,验证猜测阶段给出解的正确性。P类问题是确定性计算模型下的易解问题类,NP类问题是非确定性的计算模型下的易验证问题类。所以所有非确定性多项式时间可解的判定问题构成NP类问题。

另一种叙述:

image-20211112191137809
image-20211112191137809

第2章 递归与分治策略

image-20211112191718610
image-20211112191718610

一波总结

问题 时间复杂度 备注
二分搜索 $O(logn)$
大整数的乘法 $O(n^2)$或$O(n^{log_23})$…..
Strassen矩阵乘法 $O(n^3)$$O(n^{log_27})$$O(n^{2.376})$
合并排序 $O(nlogn)$
快速排序 最坏$O(n^2)$最好$O(nlogn)$
线性时间选择 $O(n)$
最接近点对问题 $O(nlogn)$

递归的概念

主要提到了许多问题:阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分、汉诺塔问题。其中整数划分问题的递归式和汉诺塔的伪代码如下:

image-20211112192340033
image-20211112192340033

image-20211112192414984
image-20211112192414984

分治法的基本思想

可能涉及到时间复杂度的计算

image-20211112193510850
image-20211112193510850

问题T可以划分为m个子问题,需要递归k次。其时间复杂度有两种计算方法:

image-20211112193551538
image-20211112193551538

主定理法:$aT(n/b)$和$f(n)$的问题规模,问题规模大的,说明其阶数大,即为主问题的主要时间消耗成分。$aT(n/b)$的时间复杂度可以用下式表示$O(n^{log_ba})$,所以比较$f(n)$和$aT(n/b)$的阶,只需要两者做比(类似洛必达的处理方式):$\frac{n^{log_ba}}{n^{log_ba-\epsilon}}$。所以就有了如下内容:

image-20211112194220117
image-20211112194220117

迭代法:不想多说,就是求和,而且在某种情况下极度难求

image-20211112194309541
image-20211112194309541

image-20211112194340341
image-20211112194340341

二分搜索

已经排好序的n个元素搜索某个数字:

input x, a[n]
int left=0, right=n-1
while (left<right)
	int middle = (left+right)/2
    if (x == a[middle])
        return middle
    if (x > a[middle])
        left = middle + 1
    else
        right = middle - 1
return -1

时间复杂度为$O(logn)$

大数乘法

不是特别的固定,所以考的可能性不大吧。

正常的计算复杂度为$O(n^2)$。使用分治法的大数乘法:

image-20211112201322857
image-20211112201322857

所以对应的递归式:

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 4T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

如果非要考的话可能会考上式如何得到:AC表示A与C相乘,即两个$n/2$长度的整数相乘,同理,还要计算AD、BC、BD所以总共是$4T(n/2)$,$O(n)$表示位移和加法运算和。但是上述的时间复杂度还是$O(n^2)$

因为大数惩罚的的核心是减少乘法次数,所以可以化简成下式:

image-20211112202038383
image-20211112202038383

不难看出其对应的递归式:

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 3T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

此时时间复杂度为$T(n)=O(n^{log_23})$。(这里其实也体现了主定理方法求时间复杂度)至于觉得会考的部分可能是给出一个化简式让你写递归式,但是概率太小了……

Strassen矩阵乘法

大数相乘尚且需要$O(n^2)$,a*b与b*c的矩阵相乘需要$O(abc)$,方阵需要$O(a^3)$所以不太行。与大数乘法类似,核心是减少乘法次数,所以有两个方案:

正常人想出来的:

image-20211112202739873
image-20211112202739873

递归式为:

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 8T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

时间复杂度为$O(n^3)$

Strassen矩阵乘法:

image-20211112202750122
image-20211112202750122

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 7T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

时间复杂度为$O(n^{log_27})$

棋盘覆盖

都说了不考了,所以就不说了

合并排序

思想就是把数组分成两份,连接时排序,上伪代码:

input a[n], left, right
b[n] 为创建出来的空数组,用于保存结果
void MergeSort(a[], int left, int right)
    if (left < right)
        int mid = (left + right)/2
        MergeSort(a, left, mid)
        MergeSort(a, mid+1, right)
        Merge(a, b, left, mid, right)
        Copy(a, b, left, right)

时间复杂度:$T(n)=O(nlogn)$

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 2T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

哦,真是优雅的屎代码啊,为了了解其实现的细节,我们来看看下面的代码(为了方便,代码并不符合c++规范):

void MergeSort(int a[], int n)
    int b[n]={0,,,0}
	int s = 1 # 记录块大小,也可以表示递归层数
    while (s < n)
        MergePass(a, b, s, n)
        s += s
        MergePass(b, a, s, n)
        s += s

void MergePass(x[], y[], s, n)
    int i = 0
    while (i <= n-2*s)
        Merge(x, y, i, i+s-1, i+2*s-1)
        i = i+2*s
    if (i+s < n)
        Merge(x, y, i, i+s-1, n-1)
    else
        for(int j=i; j<=n-1; j++)
            y[j] = x[j]

void Merge(c[], d[], l, m, r)
    int i=l, j=m+1, k=l
    while ((i<=m) && (j<=r))
        if (c[i]<=c[j])
            d[k++] = c[i++]
        else
            d[k++] = c[j++]
        if (i>m)
            for(int q=j;q<=r;q++)
                d[k++]=c[q]
        else
            for(int q=i;q<=m;q++)
                d[k++] = c[q]

敲一遍的话不是很难理解,但是切记不要眼高手低,毕竟这代码自己写不出来。

快速排序

快排是基于分治的另一个排序方法,步骤为分解,递归求解,合并

void QuickSort(int a[], int p, int r)
    if (p < r)
        int q = Partition(a, p, r)
        QuickSort(a, p, q-1)
        QuickSort(a, q+1, r)

在我看来,快排是由基准和合并两个部分组成的,其基准方案是参考了什么排序算法来着?已经忘了

基准获取函数:

int Partition(int a[], int p, int r)
	int i=p, j=r+1
	int x = a[p]
	while (true)
		while(a[++i]<x && i<r);
		while(a[--j]>x);
		if (i>=j)
            break
        Swap(a[i], a[j])
   	a[p] = a[j]
	a[j] = x
	return j

这就是那个一趟排序可以保证一个数字位置正确的算法。这一趟时间复杂度只有$O(r-p-1)$

但是上述总体的快排与划分是否对称有关,最坏的情况下为$O(n^2)$:

$$\begin{equation} T(n)= \begin{cases} O(1)& n\leq 1\ T(n-1)+O(n)& \text{n>1} \end{cases} \end{equation}$$

最好情况下是$O(nlogn)$

$$\begin{equation} T(n)= \begin{cases} O(1)& n\leq 1\ 2T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

平均复杂度是$O(nlogn)$

可见该算法的时间复杂度取决于划分,可以考虑使用随机的划分方案。

线性时间选择

还是基于快排的思想,首先找到一个基准元素,一趟快排决定他的位置,判断是在左还是右,继续。

这个不是特别难,代码直接贴过来了:

Type RandomizedSelect(Type a[],int p,int r,int k) 
{
    if (p == r) 
		return a[p]; 
	int i = RandomizedPartition(a, p, r), j = i-p+l; 
	if (k<=j) 
		return RandomizedSelect(a, p, i, k); 
    else 
    	return RandomizedSelect(a, i+l, r, k-j);
}

其实和快排一样,速度在$\Omega(n^2)$到$O(n)$之间,但是平均性能很好。

那么能不能让算法在最坏的情况下还能$O(n)$?很离谱,根据主定理,我们只要让划分的时间复杂算法思路如下:

  • n个元素分为$n/5$组,每组5个元素,然后排序,取中位数,也就是获得了$n/5$个中位数
  • 递归调用上面的算法

虽然不太懂,但是很nb,最后得到递归式

image-20211112221632393
image-20211112221632393

代码如下:

template<class Type> 
Type Select(Type a[], int p, int r, int k) { 
    if (r-p < 75) { 
        return a[p+k-1]; 
					}
	for (int i=0; i <= (r-p-4)/5; i++) { 
    	Type x=Select(a, p, p+(r-p-4)/5, (r-p-4)/10); 
		int i = Partition(a, p, r, x), j = i-p+l; 
		if (k <= j) 
			return Select(a,p,i,k); 
		else 
    		return Select(a,i+l,r,k-j)
	}
}

最近点对问题

说是不出大题,所以可能会好一点。一维的不难理解,每次划分成两份,找到相邻两份的最大值和最小值,差即为最小距离,合并,重复操作。时间复杂度为$O(nlogn)$递归方程如下:

$$\begin{equation} T(n)= \begin{cases} O(1)& n<4\ 2T(n/2)+O(n)& n\geq 4 \end{cases} \end{equation}$$

重头戏在后面,所以这种算法就贴个截图算了

image-20211112222519860
image-20211112222519860

实际上感觉没必要考二维,毕竟其核心在于一个奇怪的证明,也有点看不懂,建议自己理解算了。

image-20211112223815664
image-20211112223815664

时间复杂度为:$O(nlogn)$,就这?确实不会考大题。

个人还是比较青睐于两个排序和线性时间排序。

第3章 动态规划

同样,先准备一个小结:

image-20211112224123330
image-20211112224123330

感觉难的地方到了

问题 时间复杂度 备注
矩阵连乘 $O(n^3)$ 最优值在dp[0][n]处
最长公共子序列 $O(mn)$ and $O(m+n)$ 最优值在dp[m][n]处
最大子段和 $O(mn^2)$或$O(m(n-m))$ 最优值在dp[n]处
凸多边形最优三角剖分 $O(n^3)$ 最优值在dp[0][n]处
流水作业调度 $O(nlogn)$ 最优值在dp[m][n]处
0-1背包问题 $O(min{nc,2^n})$ 最优值在dp[i][j]处
最优二叉搜索树

首先分析一下动态规划的核心吧,类似分治,就是把问题分为子问题求解。但是存在的最大不同就是子问题之间是有关系的,所以不必要在分治的情况下花费指数倍的时间。

动态规划对应的有几个固定的步骤:

  • 找出最优解的性质并刻画其结构特征
  • 递归地定义最优解
  • 自底向上的方式计算最优值
  • 根据计算最优值得到的信息构造最优解

动态规划的有效性是基于它的两个形式:

  • 最优子结构,通俗点讲,就是对最优解和原问题求相同的子集后,对应的解仍然为子集问题的最优解
  • 重叠子问题,即在使用分治法计算时得到子问题并不总是新问题,也正是因此,我们会用到备忘录方法

矩阵连乘问题

直接上备忘录方法吧:

image-20211113163135927
image-20211113163135927

我们令p0~p7=[30,35,15,5,10,20,25]

对于该题,我们创建一个方阵

image-20211113163019814
image-20211113163019814

实际上每个坐标表示一个子问题,如m[2][5]就表示从第2个矩阵到第5矩阵连乘的最优解。

那么不难得知,m[i][i]=0所以先进行对角线的初始化。在此之后,开始计算第1与第2矩阵相乘的最优解,乃至第5到第6矩阵相乘的最优解,也就是上图的第二条对角线。以m[2][3]为例,该点的最优解计算就是p1*p2*p3。

这个还不是很难。那么对于m[2][4],这个时候情况不一样了,其计算应该为:

$$\begin{equation} m[2][4]= min\begin{cases} m[2][2]+m[3][4]+p_1p_2p_4\ m[2][3]+m[4][4]+p_1p_3p_4\end{cases} \end{equation}$$

即第2个矩阵到第4个矩阵连乘的可能解有两种可能,即$(A_2)(A_3A_4)$和$(A_2A_3)(A_4)$而之前又求过m[3][4]和m[2][3]的最优解,所以…

基于上述内容,我们可以得到其递归式

$$\begin{equation} m[i][j]= \begin{cases} 0&i=j\ min{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j}&i<j\end{cases} \end{equation}$$

应该是难度比较合理的题目了,基于上述的递归式,我们也应该能大致得知其伪代码(但是这种考循环体的说实话不大可能,直接贴过来)

image-20211113164650749
image-20211113164650749

时间复杂度为$O(n^3)$因为要解矩阵,而且该矩阵每个值得通过多个计算比较最小值。

最长公共子序列

注意是序列而不是船,串必须连续但是序列不需要。

根据题目要求,给出两个序列X和Y,分别长度为m和n,还是基操,创建一个m*n的矩阵。那么每个坐标m[i][j]的意义为:n中前i个元素构成的序列与m中前j个元素构成的序列的最长公共子序列。

这道题并不难搞。感性的分析一下,无非就是两个序列从0开始,某一个长度加1,如果发现增加的元素是相同的元素,那么矩阵该位置的值相较于之前的状态+1,否则不变,把整个矩阵填完即可。

但是考虑到考试会考动态规划的证明,所以需要证明该问题有最优子结构性质。所以有如下的内容:

image-20211113203912650
image-20211113203912650

image-20211113203921395
image-20211113203921395

image-20211113203928047
image-20211113203928047

那么基于上面的分析,我们得到的子问题递归结构为:

image-20211113204101376
image-20211113204101376

因为每个单元的计算时间$O(1)$,所以整体的时间复杂度为$O(mn)$,回溯获得最长子序列的时间复杂度为$O(m+n)$

最大子段和

也是十分简单的动态规划问题,可以在leetcode上找到原题,甚至不需要二维表。

分治法的时间复杂度$O(nlogn)$

动态规划法很简单啊,递归式如下:

$b[j]=max{b[j-1]+a[j],a[j]}$

时间复杂度和空间复杂度都为$O(n)$,对于空间复杂度可以化简到$O(1)$

一维的难度并不大,所以书上还给出了矩阵的最大子段和,但是典懒得看书,不如看垃圾CSDN[https://blog.csdn.net/kavu1/article/details/50547401]

上代码:这里也用到了最大子段的代码函数MaxSum

int MaxSum2(int m,int n,int a[M][N])
{
    int sum = 0;
    int *b=new int[n];
    int max=0;
    for (int i=0;i<m;i++){
        for (int k =0;k<n;k++)
            b[k]=0;       
        for(int j=i;j<m;j++){//枚举初始行i,结束行m
            for(int k = 0;k<n;k++)
                b[k] += a[j][k];//b[k]为纵向从行i到行m的之和
            max=MaxSum(n,b);   
            if(max>sum)
                sum=max;
        	}
        	}
    return sum;
}
int MaxSum(int n,int *a)
{
   int sum1=0,b=0;
    for(int i=0;i<n;i++){
        if(b>0){
            b += a[i];
        }else{
            b=a[i];
        }
        if(b>sum1){
            sum1=b;
        }
    }
    return sum1;
}

这样的时间复杂度为$O(mn^2)$,空间复杂度为$O(mn)$,书上还叙述了时间复杂度和空间复杂度分别为$O(m(n-m))$和$O(n)$的算法,就不多说了。

凸多边形的最优三角剖分

这部分可谓是完全没有听。题目就是一个凸n边形,可以通过n-3条弦分成n-2个三角形,现在给弦和边函数和一些数值,使得剖分得到的函数和最小。

十分抽象的是,我们可以把这类问题等价于矩阵连乘问题(这个正常人真想不到)

image-20211113214325107
image-20211113214325107

把矩阵连乘变成树我还是可以理解的,毕竟dp和分治也不能说是没有一点关系,其中同层的节点先乘。但是把树扭一扭就能变成凸多边形属实是想不到的,这东西叫语法树。但是换个角度想,我加一条弦,就是把多边形(边)分成了两部分(子树),之后每部分(子树)继续加弦,就能成为一个二叉树,完全合理。

注意,该问题的递归式和矩阵连乘的递归式是完全相同的

image-20211113215816472
image-20211113215816472

对应的时间复杂度也是类似的$O(n^3)$。但是构造最优三角剖分的时间复杂度为$O(n)$

流水作业调度

我们令S为所有作业N的子集,那么当M1开始加工S中作业时,机器M2还在加工其他作业,到时间t之后才可利用,所以我们描述最短时间为$T(S,t)$,整个流水调度问题的最优解为$T(N,0)$。实际上不难理解,对于一个最优调度,整体的时间等于M1处理第一个任务的时间和M2处理其余所有任务的时间和。关于子结构的性质证明参见书上内容:

image-20211113221200081
image-20211113221200081

实际上,根据它的最优子结构性质,我们也能得到递归式:

$T(N,0)=min_{1\leq i\leq n}(a_i+T(N-{i},b_i))$

通常情况如下:

image-20211113221352259
image-20211113221352259

以上是作为一个动态规划问题的正常算法,但是也没有给代码。

然后书上提到了一个极度让人看不懂的东西:Johnson算法?实际上就是在调度时,相邻的两个任务,如果在这种调度下的时间小于交换这两个任务的之后调度的时间,那么这时候这两个相邻作业是满足Johnson不等式的。所以存在不断地交换相邻任务(逆序对),使得整体的时长最短。所以问题就变成了一个排序问题。时间复杂度为$O(nlogn)$。

说实在的,感觉这道题貌似跟动态规划没有太大关系。Johnson算法如下:

image-20211113224102955
image-20211113224102955

把$a_i<b_i$的任务归给$N_1$,其他的归给$N_2$。对$N_1$升序排序,$N_2$降序排序。就满足了最优调度。

没得说

0-1背包问题

这东西看上去就是个动态规划问题,但是做到这里,也应该怎么证明一个最优子结构性质了。

首先根据问题的描述设一个最优解,取问题和最优解的子集,接着反证,说子问题有另一个最优解,让他和去除的部分结合,结果发现与最优解不相等,所以矛盾了,所以有最优子结构性质。

image-20211113224621202
image-20211113224621202

image-20211113224627663
image-20211113224627663

终于是回归到了正常的动态规划算法,实际上,如果没有背包容量作为限制条件的话其实就是最大子段和问题。基于上述内容,艹,电子书上的递归式有点绕,换一个,就直接创建这样一个表:

image-20211113231137302
image-20211113231137302

image-20211113231202166
image-20211113231202166

二层遍历,时间复杂度为$O(n*m)$但是我不理解啊,为什么书上的这么复杂?完全不懂,摆烂先。

最优二叉搜索树

我开始以为这道题就是构建一颗二叉搜索树,结果发现不是这样的。给定一个集合,我们生成许多个二叉搜索树,使得访问的期望最小。这颗树同样也是满足最优子结构的,但是由于涉及到了递归,所以细节不好说明。

但是思路也是很简单,有点晕,先鸽了,明天继续。

第4章 贪心算法

趟过了动态规划之后就没有太大的难度了,接下来就是贪和图论里面的经典操作。

image-20211113234113069
image-20211113234113069

要证明贪心策略和贪心选择有效性。

动态规划具有最优子结构问题,即问题的最优解,将问题取子问题,解取对应的子解同样满足最优,而贪心则意味相反的,在当前(子情况)中最优解就是整体的最优解,这决定了贪心算法并不难,但是对应的,我们需要证明原因。

与动态规划类似,可以使用贪心算法的题目通常具有以下两个性质:贪心选择性质和最优子结构性质。贪心选择性质即目光短浅,只考虑当前情况就可以满足全局最优解。而最优子问题在动态规划中就有提到了。所以说,在某个层面,贪心算法算是动态规划问题的子集。

问题 时间复杂度 备注
活动安排问题 $O(nlogn)$
最优装载 $O(nlogn)$
哈夫曼编码 $O(nlogn)$
最小生成树 P$O(n^2)$ K$O(eloge)$
多机调度问题 $O(nlogn)$

活动安排问题

给出一堆活动,要求安排活动使得尽可能少的天数完成。那就硬贪,贪结束最早的活动。具体算法是花$O(nlogn)$对活动根据结束时间进行升序排序,之后活动不冲突的就丢进去,最后就能得到最多的活动安排。

那么如何说明?在该题中,贪心的意义是使剩余的可安排时间最大化。至于具体而又冗杂的说明,看看书吧:

image-20211114002936531
image-20211114002936531

image-20211114002944079
image-20211114002944079

总而言之,难度不大,时间复杂度为$O(nlogn)$

最优装载问题

承载量为c的轮船,集装箱i的重量为$w_i$,尽可能装多的集装箱。不愧是贪心,容易的一匹。升序排序,丢进轮船。时间复杂度同样为排序的时间$O(nlogn)$

至于性质证明:

image-20211114013718825
image-20211114013718825

哈夫曼编码

哈夫曼编码也是数据结构里面学过的东西,甚至能拿出来在编码论中反复鞭尸。关键是如何说明哈夫曼算法是正确的。

首先证明贪心选择性质:

image-20211114014845653
image-20211114014845653

image-20211114014856487
image-20211114014856487

接下来证明最优子结构

image-20211114014922709
image-20211114014922709

算法的难度确实不大,但是理解证明确实难度不小。

最小生成树

最小生成树是指对图进行剪枝得到路径权值之和最小的树(因为树不存在环)。同样在数据结构中有所涉及。有两个方案:Prim算法和Kruskal算法,两种算法的流程和使用场合也有所不同,需要一一讨论,而且相较于上面的贪心,这个难度更大了一点,所以可能需要熟悉的掌握了。

设$G=(V,E)$是无向连通带权图。上述的两个算法都是做了贪心,虽然凡是不同,但是都利用了MST性质,即对于U为V的真子集,若有$(u,v)\in E$且$u\in U, v\in V-U$,在所有的边中,$(u,v)$的权最小,那么一定存在$G$的一颗最想生成树,以$(u,v)$为其中一条边。证明如下:

image-20211114015836277
image-20211114015836277

基于上述的MST,接下来康康Prim和Kruskal算法的步骤。

Prim算法:不断选择最短的边,直到所有的点均包含在图中。(贪在选最短边)但是实现的过程中稍微有点要考虑的是如何找到满足$i \in S和j\in V-S$两个条件的边。首先把一个节点作为起点放到列表里,之后找到该节点所连接的所有节点以及对应的边,取最小的边添加到边数组中,同时节点也添加回到列表中。(BFS)所以整体的复杂度为$O(n^2)$

书上的源码是正经做法,实际上我们也在数据结构中学到过使用队列的代码:

image-20211115163848199
image-20211115163848199

image-20211115163855854
image-20211115163855854

至于基于优先队列的实现可以看看这个:https://blog.csdn.net/qq_37497322/article/details/75043491

Kruskal算法Kruskal的算法则是直接找图最小的边,直到生成一棵最小生成树。同样可以整个优先队列来玩。

image-20211115164520823
image-20211115164520823

时间复杂度是$O(eloge)$,其中将边按权组成优先队列需要$O(e)$的时间,while循环中的需要$O(loge)$时间,所以整体就是一个乘积。

根据两者的时间复杂度来看,需要根据不同的情况使用不同的算法来取得最好的时间损耗。当$e=\Omega(n^2)$时,Kruskal算法比Prim算法差,但是当$e=O(n^2)$时,Kruskal算法比Prim算法好得多。

多机调度问题

NP完全问题,无有效解法,所以使用贪心选择策略设计较好的近似算法。

使用最长处理时间作业优先的的贪心选择策略,没有证明,也不算很难,时间复杂度为$O(nlogn)$

image-20211115184750626
image-20211115184750626

至此就完成了贪心算法的一个说明,难度不大,但是涉及到证明还是需要好好看看。那就再看看贪心策略的证明方案吧.

贪心正确性证明

贪心的正确性证明有一个方法叫做:Exchang Arguement,交换参数,该方法的核心思想就是:假设存在一个最优算法和我们的贪心算法接近,之后交换算法中的一个步骤或元素,得到一个新的最优算法,且该算法比前一个最优算法更接近我们的贪心算法从而得到矛盾,说明我们的贪心算法是正确的。

很绕,举个例子:以活动安排问题为例。首先贪心算法就是排序,把结束时间最早的加入活动列表,我们叫这个算法(贪心)为A。假设A不是最优的,那就一定存在一个算法O,其和A最相近(前k-1个选择相同,第k个不同),也就是说,原本算法A的第k个选择是$(a_i,b_i)$而算法O的第k个选择是$(a_j,b_j)$,根据我们对A的定义,可以知道$b_i<=b_j$。那么我们构造一个$O’=O-(a_j,b_j)+(a_i,b_i)$

那么这个$O’$有两个性质:1、没有重叠。$O’$中的前k-1个元素和A一样而k之后的元素和O一样,且由于$b_i<=b_j$所以未发送冲突。2、$O’$是一个最优解,因为它的元素个数和O是一样的。

至此就找到了最优解$O’$与A具有K个共同的元素,但是这与我们之前的假设冲突了,所以A最优。

同理,其他的算法也是类似的原理,可以参考着试一下。

第5章 回溯法

回溯法和下一章的分支界限法是有点关系的,回溯法主要使用了DFS,即一次得到一个结果,获取所有结果。就像每一章都会有对应的重点一样,这章的重点不是暴力搜索和建树,而是判断终止条件。

image-20211115192333382
image-20211115192333382

问题 时间复杂度 备注
装载问题 不记录$O(2^n)$,记录可以$O(2^n)和O(n2^n)$
批处理作业调度 $O(n!)$
符号三角形问题 $O(n2^n)$
n后问题 $O(n!)$
最大团问题 $O(n2^n)$
旅行售货员问题 $O(n!)$

在解决问题时,回溯有两个方案。一个是基于递归的,也是比较喜欢的方案:

image-20211115193254416
image-20211115193254416

另一个则是基于迭代的(也可以叫做非递归写法)

image-20211115193342530
image-20211115193342530

image-20211115193348341
image-20211115193348341

装载问题

首先要注意的是,这里的装载问题只有两艘船,属于第4章题目的特殊情况,同时又可以看作是0-1背包问题。

这一道题给出了4种代码,我们直接看带记录的:

image-20211115203441339
image-20211115203441339

不带记录的话时间复杂度为$O(2^n)$,带记录的话时间复杂度为$O(n2^n)$但是也可以通过一些方法把时间复杂度降到$O(2^n)$。分别为得到最优解后重新访问得到节点和动态更新最优解。

本题中的终止条件为cw+w[i]>=c即对于一个新的货物,当放到船1上的时候,如果放的下,则继续对船一放置货物(左子树),否则向船二放置(右子树)。

除了上述的方法以外还有一种迭代的回溯法,当然时间复杂度是不变的,但是可能会更加恶心一点。

批处理作业调度

前面没有提到的是,对于回溯法问题,通常由两种典型的解空间树,分别为子集树和排序树。当问题为从集合中找到满足某个性质的子集时,称解空间树为子集解。当问题是确定n个元素满足某种性质的排序时,解空间是排列树。上题即为子集树,而该题为排序树。

子集树的框架:

image-20211115204457047
image-20211115204457047

搜索树的框架:

image-20211115204516714
image-20211115204516714

image-20211115204522018
image-20211115204522018

批处理作业调度问题指的是一堆任务和两个机子,每个作业都要先机器1完成之后机器2完成。每个任务对两个机子的运行时间不同。可以证明,只有两个机子完成的顺序相同时时间最短。

image-20211115204725760
image-20211115204725760

看到这里,首先要澄清一下这道题和dp中流水作业算法的关系。该题目的目的是求n个作业的最小 完成时间之和,就是操作系统中的那个概念。而流水作业则是所有任务完成消耗的时间。

愚蠢的回溯法啊,就是暴力列举出所有可能的情况以及对应的结果,找到和最小的就好了。所以时间复杂度为$O(n!)$

image-20211115212614860
image-20211115212614860

由于该题目是一个排序树,其终止条件是递归地层数达到排序元素的个数,即j<=n

符号三角形问题

给定一个符号数n,生成一个符号三角形,其中两个同号下为+,异号下为-,找到所有+和-符号个数相同的情况:

image-20211115212926539
image-20211115212926539

怎么个做法?实际上可以通过一颗二叉树实现,对于两种符合号,假设左子树为+,右子树为-,那么n个符号,最后的叶子就有$2^n$个,那么这$2^n$个叶子,但是实际上,为了保证生成的树+和-的数量相等,我们需要最后生成的符号三角中两种符号的数量都不超过$\frac{n(n+1)}{22}$。此外为了进一步简化复杂度,我们不难得知,当我们确定了前i个字符之后,接下来只需要斜着添加一行就是i+1个字符的符号三角形了。在回溯过程中,以两种符号的个数都不超过$n(n+1)/4$为可行性约束并减去子树,且当$n(n+1)/2$为奇数时不存在数量相同的符号三角形,基于上述条件核心的代码如下:

image-20211115215702240
image-20211115215702240

其中t表示层,count为+的数量,half即为$n*(n+1)/4$,sum表示符号三角数量。终止条件即为count>half(+的数量)或是(-的数量)超过half。时间复杂度为$O(n2^n)$。感觉不会很乐意考

n后问题

n个棋子放在n*n的棋盘上,每行每列没斜线不能出现多个皇后。算是一个排序树吧。

image-20211116003511611
image-20211116003511611

其中的place函数即为终止条件的判断,判断是否在一条线上。其中x为当前解的数组,t为递归深度。可以这样理解,每一层递归都对应着期棋盘的一行,x记录了每一行皇后的位置,所以判断的时候只需要看看有无同列即可(x[j]==x[k])。而abs(k-j)==abs(x[j]-x[k])则判断有无同对角线。对应的时间复杂度为$O(n!)$

0-1背包问题

可恶,拿一道题反复鞭尸,不讲武德。0-1背包问题是NP完全问题,而且是解空间树是子集树,相较于dp,其实更容易理解,即左子树放,右子树不放,暴力列举所有情况,然后计算叶子节点的价值即可。为了加速算法,可以首先对物品进行降序排序。

终止条件可以有两个,一个很简单,就是当超出背包容量的时候剪枝,另一个就是当前物品的价值大于最优价值时对右子树剪枝。分别对应着cw+w[i]<=c和Bound(i+1)>bestp

image-20211116005914296
image-20211116005914296

image-20211116005922877
image-20211116005922877

时间复杂度为$O(n2^n)$

最大团问题

还是一个子集选取问题,还是子集树,所以复杂度就不用多说了$O(n2^n)$。左子树即为连通点,右子树需要确认有足够多的可选择顶点。

因此终止条件也就是对应的,不是很想整理这道题。

image-20211116011540433
image-20211116011540433

旅行商售货问题

好家伙连题都不给了,但是这是一个排序树,所以复杂度是$O(n!)$。

第6章 分支界限法

如果说第五章是DFS,那么第六章就是BFS,尽可能快的找到最优解。通常使用队列实现,也正是因为如此,队列可能为本章的主要考核,除此之外还有树的生成和遍历。好在本章的内容并不多。

image-20211116012636143
image-20211116012636143

问题 时间复杂度 备注
最优装载 $O(2^n)$

分支界限法的核心就是尽可能的伸出多个解,当找到一个解的时候所有分支全部中断,其最大的好处在于代码很容易看懂(xs)直接上题目吧:

装载问题

老牌问题,通常BFS是来找距离最近的解的方案,但是这道题也确实可以这样用(实际上就是BFS暴搜)。康康代码:

image-20211116013033125
image-20211116013033125

对于一个起始的节点,把所有的放到队列里面,接下来取出来,遍历所有边,把符合条件(能承载下)的结点放到队列里,接下来继续。这道题之所以可以使用这个方案的另一个原因是图不存在环。时间复杂度是$O(2^n)$。

除此之外还有基于优先队列的分支界限法。与上述方法不同,优先队列首先将数据进行排序以生成最大最小,该题目中的优先级定义为根节点到节点x的路径相应的载重量再加上剩余集装箱的重量之和

image-20211116014937117
image-20211116014937117

image-20211116014947931
image-20211116014947931

Licensed under CC BY-NC-SA 4.0
豫ICP备2021032923号
Built with Hugo
Theme Stack designed by Jimmy