出栈序列的个数问题

当n个元素\(a_1,a_2,\cdots,a_n\)有序进栈,但不约束出栈时机,但是进栈一定按照排好的顺序,问一共有多少个出栈序列。

如何进行计算出栈序列的个数呢?

首先定义一个函数\(f(n)\),表示n个元素有序进栈时,可能的出栈序列个数

那么现在考虑一个问题在n个元素中,假设第i个元素 \( a_i \)是最后出栈的,这种情况下有多少种可能呢?

分析思路1

参考这篇博客

分析:设f(n)为“n个元素以一定的顺序入栈,出栈顺序的种类数”。显然f(1)=1,f(2)=2。我们现在来分析一般情况。一般情况下,我们可以按照“第一个入栈的元素,在出栈序列中的位置”作为分类手段。

举个例子,我们假设入栈元素为A,B,C,D。我们按照“A在出栈序列中的位置”分类讨论:

(1)当A第一个出栈时,A先进,然后马上出栈。这种情况下,共有“BCD出栈顺序的种类数”种方案。也就是f(n-1)。

(2)当A第二个出栈时,A先进,B再进,之后B需要马上出来(这样才能确保A排第二)。此时共有f(n-2)种方案。

(3)当A第三个出栈时,A先进,之后只要确保排在A后面两个的元素比A先出即可。此时共有f(2)*f(1)种方案。f(2)是指“BC入栈出栈顺序的种类数”,f(1)是指”D入栈出栈的种类数”。

分析思路2

按照分析最后出栈元素进行讨论

首先考虑 元素 \( a_i \) 进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 这些元素肯定都进过栈了,因为进栈是按照指定顺序的。在由于 \( a_i \) 是最后出栈的,而栈是先进后出、后进先出的特定,因此 \( a_i \) 进栈的时候,栈应该是空栈,否则 \( a_i \) 不可能是最后一个出栈,这也意味着 \(a_1,a_2,\cdots,a_{i-1}\) 这些元素在 \( a_i \) 进栈之前都已经出栈了。

总结一下就是当 \( a_i \) 是最后出栈的元素时, \( a_i \) 在进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 都已经完成了进栈和出栈,这就是一个符合我们函数定义的子问题 \(f(i-1)\)。

再考虑 \( a_i \)之后的元素,由于 \( a_i \) 是最后出栈的元素, \( a_i \) 元素进栈之后就只可能一直待在栈底,那么 \(a_{i+1},a_{i+2},\cdots,a_{n}\) 这些元素在 \( a_i \) 元素进栈之后完成了进栈和出栈的操作,这又是一个子问题f(n-i).

那么这样,当 \( a_i \) 是最后出栈的元素,那么这种前提下的可能出栈序列数目为 \( f(i-1) * f(n-i) \)

所以有 \( f(n)=\sum_{i=1}^n f(i-1) f(n-i) \)

实际这个是卡特兰数,有兴趣可以看看相关资料

令f(0)=f(1)=1这样可以正确进行递归过程

\( f(n)=C_{2n}^{n}-C_{2n}^{n-1}= \frac{ C_{2n}^{n} }{n+1} \)

相关推导可以参见下面的视频

个数是指数量级的。

参考文章:

https://blog.csdn.net/harryhare/article/details/69388827?skintest=skin3-template-test

https://blog.csdn.net/qq_26286193/article/details/80216479

最优二叉搜索树(带有查询失败情况)

最优二叉搜索树(不考虑查找失败的情况)详情见另一篇文章

这里是简单地介绍一些这个问题的解题思路,也是采用动态规划策略,思路也大致相似。

问题定义: 现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),查找失败的概率为: \(q_0,q_1,q_2,\cdots,q_n\) 如何构造一颗二叉排序树,使得平均查找次数最少?

首先易知该问题满足最优子结构性质,可以采用动态规划求解,动态数组dp定义通上一篇文章。 定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

不同的是分析状态转移方程。

这里需要将查找失败的情况当做与父亲节点同高度的虚拟节点,初始化就比较好分析。当选择某一个节点k作为根节点时,左右子树的所有节点的高度都增加1(包括真实节点和虚拟节点1)。这样额外的开销可以分为三个部分:左子树\(\sum^{k-1}_{x=i}p_x\), \(\sum^{k-1}_{x=i-1}q_x\) ,右子树 \(\sum^{j}_{x=k+1}p_x\), \(\sum^{j}_{x=k}\),根节点 \(p_k\)。

累加起来就是 \(\sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x\)

那么状态转移方程就是: \(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] + \sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x \}\)

比不考虑查询失败情况下多加了一项而已。

考虑边界和初始化情况,当i>j时,视为空树,代价为0。当i=j时,代价为\(p_i+q_{i-1}+q_i\)符合状态转移方程的定义,因此后续的逻辑就是正确的。

求解过程,自底向上求解,最终求出 \(A[1][n]\)

时间复杂度上界同样是 \(O(n^3)\),空间复杂度 \(O(n^2)\)

练习:

答案:

最优二叉搜索树 动态规划

问题描述:现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),如何构造一颗二叉排序树,使得平均查找次数最少?

贪心策略:每次选择查询最大的那个元素作为根节点,然后依次左右子树递归构建下去。但是贪心问题不是最优的,可以举一个反例进行反驳。

最优子结构分析:假设有一颗树是当前问题的一个最优查询树,根节点为 \(a_i\) ,那么根节点连接的两颗子树(两个子问题 \(a_1,a_2,\cdots,a_{i-1}\)和 \(a_{i+1},a_{i+2},\cdots,a_n\) )也应该是对应的最优查询树(平均查找次数最少),否则原来那个树就不是最优的树,产生矛盾。因此该问题存在最优子结构性质。

动态规划策略:

首先定义dp数组,定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

下面推导状态转移方程:

根据问题的特性当两个子问题要合并成一个大问题的时候,在子问题的基础开销上,子问题的子树上所有节点的高度都增加1,也就是每个节点的开销都需要加上该节点的访问概率,同时根节点的开销是根节点的访问概率,因此也就是从左子问题的头节点的访问概率累加到右子问题的尾节点的访问概率。因此有下面的转态转移方程:

\(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] +\sum^{j}_{x=i}p_x \}\)

初始化条件:,当i=j时,即只有一个元素,只能作为根节点。故此时 \( A[i][i]=p_i\)

边界条件:当i>j是,这种情况不合常理,当时在求解的时候回设计到,为了保障算法的正确运行,将这个值设为0,即没有代价。有了这一步,实际上初始化条件都可以改为将\(A[i][i-1]\)直接设为0,可以结合转态转移方程,并分析自底向上计算过程得到这个结论。

计算顺序:自底向上方法,如果要求最优的二叉排序树的结构,可能该需要一个二维数组记录一下树的结构。

时间复杂度:三层循环,上界为O(n*n*n)

空间复杂度:O(n*n)

练习:

答案

硬币问题(凑零钱) 动态规划

infinity = 9999
def coin_change(coins, a):
    dp = []
    '''初始化过程'''
    dp.append(0)
    min_amount = min(coins)
    for i in range(1, min_amount):
        dp.append(infinity);
    
    '''动态规划自底向上方法计算过程'''
    for i in range(min_amount, a + 1):
        min_count = infinity
        for c_j in coins:
            if i >= c_j and dp[i - c_j] + 1 < min_count:
                min_count = dp[i - c_j] + 1
        dp.append(min_count)
    return dp[a]

时间复杂度分析:求最小硬币面值(\(O(n)\))和初始化dp数组( \( O(1) \) )可以忽略不计,动态规划过程中有两层循环,外层最多执行a次,内层最多执行n次,因此该算法最坏的时间复杂度的 \( O(an) \)

空间复杂度分析 :dp数组所占用的空间为 \(O(a) \)

矩阵连乘

\(A_{n×p}\)和\(B_{p×m}\) 是两个矩阵,这两个矩阵进行相乘的乘法次数为n×p×m。那么考虑一共有N个矩阵进行连续乘法的时候,求最优的乘法次序,使得乘法的次数最少,前提是矩阵乘法满足结合律。

穷举法:所有乘法次序为(N-1)!种,代价太大。

贪心策略:容易观察,矩阵维度 n p p m 变为 n m ,如果p较大的会带来较大的乘法开销,所以我们希望在顺次确定第一步乘法是,贪心地优先消去最大的那个p。

如何确定该贪心策略是否是正确的,举个反例?

。上面是一个反例,这种贪心主要面对当一个最大维度周围是次大或者次次大维度时,造成一步的乘法次数剧增。因此这种贪心策略不满足最优条件。

逆向地思考问题,最优结构的乘法次序总有最后两个矩阵之间进行,可以这两个矩阵将原始矩阵序列划分为,两个子矩阵序列,那么这两个子矩阵序列的乘法序列也应该是最优的,否则与前提矛盾。因此这样思考,矩阵连乘存在最优子结构特性

具有最优子结构特性,那么就动态规划三步走。

最简单的方法,第一步:暴力搜索(通常是用递归来实现),遍历所有的可能,但是对于这个问题,最终的结果是各个步骤的累加,因此在暴力搜素中掺杂了回溯的思想。(自顶向下)

第二步,带有备忘录的暴力搜索,暴力搜索生成树中存在大量的重复子树,可以将已经计算的结果存下来,下次遇到直接取就可以了。 (自顶向下)

第三部,动态规划法(四个步骤) (自底向上)

  • 定义dp数组,这里用cost[i,j],表示矩阵i到矩阵j的最优的乘法次序的代价
  • 写出dp数组包含的最优子结构的递推关系
  • 确定问题的初始条件以及边界条件
  • 自底向上开始计算结果

算法课学习心得

首先明确数据结构在不同层面的意义。

数据结构可以理解为逻辑数据结构以及物理数据结构

逻辑数据结构例如数组,链表,二叉树层面上的逻辑结构,可以在纸面上画出来的结构

以二叉树这个逻辑结构为例子,在代码中用何种物理存储空间对二叉树进行建模就是物理数据结构。

例如,可以用数组物理结构对二叉树进行存储,同时利用数组下标以及以2为基础的乘除运算以及对数运算判断双亲,孩子节点以及树高等。

也可以用链表物理结构对二叉树进行存储,每个节点保存自身数据,左孩子指针以及右孩子指针。

当然逻辑结构对应dd不同物理结构在特定场景下效率各不相同。

Window 10 下 pytorch 安装(CUDA加速)

本人设备情况:Window10操作系统,显卡GTX750Ti(2G),另一张显卡HD 6570 (2G)。

A卡用来接显示器,N卡用来计算。两张显卡驱动都成功安装,没有发生冲突的情况。

首先是按照第一篇参考文献中的内容下载与显卡驱动版本,与操作系统类型以及位数(32/64) 匹配 的CUDA,然后进行安装,下载地址见参考文献2,N卡是否支持CUDA加速以及算力的查询见参考文献3。

第二部安装CUdnn,具体需要到参考文献4中进行下载,可能需要注册然后填写一个问卷。注意下载与CUDA版本匹配的Cudnn,然后将下载的内容解压到Cuda安装目录下的一个地方。

第三步安装pytorch,到参考文献5安装pytorch各项都匹配的pytorch,这里我用主流的conda工具进行安装。

建议安装在conda的虚拟环境之中

验证安装是否成功:

如何在jupyter notebook中对安装了pytorch的虚拟环境使用呢?

直接在anaconda 根用户中安装,nb_conda,基本上就可以了。

如果还不可以的话,再于装cuda加速pytorch的虚拟环境中安装ipykernel,就可以了。

references:

CUDA Toolkit 与 Pytorch 安装过程的一些坑

首先区别显卡驱动和CUDA Toolkit, 首先显卡做为一个硬件,需要驱动软件,才能保障显卡的基本正常工作。

在显卡驱动安装完成的基础上,再安装CUDA Toolkit 才能支持并行计算。但是显卡驱动版本和CUDA Toolkit版本之间是有要求的。

https://docs.nvidia.com/cuda/cuda-toolkit-release-notes/index.html

我之前装了半天pytorch,但是一直无法检查到cuda设备就是因为这个原因。

如何查看cuda版本以及驱动版本。

查看CUDA(将路径已经写入环境变量)

nvcc -V

查看显卡驱动版本

dpkg –list | grep nvidia-* 或者 cat /proc/driver/nvidia/version

我所使用的服务器cuda 版本是9.1, 显卡驱动版本时390,作为一个非管理员用户勉勉强强可以再自动的用户目录下成功装上支持GPU加速有的pytorch版本(0.4.1)。但是pytorch版本1.3都已经出来了,就想着可不可以再自己的用户目录下装一个高版本的CUDA ,然后用新版本的pytorch,那岂不是爽歪歪?

以下为尝试过程,但是失败了

原因是服务器的显卡驱动版本过低(390),与CUDA10.1版本不匹配,因此即使成功装上了pytorch 1.3,也检测不到cuda设备。

失败过程如下,如果你所使用的服务器显卡驱动版本较高,而你又是非管理员用户,又想用新版本pytorch的可以尝试一下。

https://developer.nvidia.com/cuda-downloads?target_os=Linux&target_arch=x86_64&target_distro=Ubuntu&target_version=1604&target_type=runfilelocal

下载CUDA Toolkit ,并安装,注意不要安装驱动的选项,因为你没有劝降,并且将其他安装路径都设置再用户目录以及子目录。

再自己目录下安装好CUDA10.1之后,要将CUDA相关的一些环境变量写入,以方便后续conda安装pytorch。可以参考这篇博客

接着利用conda创建虚拟环境进行pytorch安装,详见我的另一篇博客

https://pytorch.org/get-started/locally/

安装之后就是失败啦,torch.cuda.is_avialible() 返回的结果时False。

原因时服务器显卡驱动版本为390,而CUDA Toolkit 10.1要求显卡驱动版本>=418,只能让管理员去升级显卡版本啦。

Ubuntu 16.04 Cuda 9.1 安装支持gpu加速的pytorch

环境:Ubuntu 16.04 ,cuda 9.1,并且预装好了对应的Cudnn,如果服务器是多用户使用,这些是管理员完成的操作。

对于非root非管理员的用户,首先在自己的根目录下安装好Anaconda 3,网上有很多教程,安装anaconda3 也比较简单,不展开说了。

将系统根cuda的路径,配置到用户的环境变量中

然后用 source ~/.bashrc 来使用配置好的环境变量

接着使用conda包管理工具来安装gpu版本的pytorch

在之前将conda源改为国内的清华镜像源,这样下载过程中比较快。

conda config –add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/

conda config –add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main/

conda config –set show_channel_urls yes

利用conda包管理工具,创建一个名称为pytorch-gpu的虚拟环境,虚拟环境的python版本设置为3.6.

conda create -n pytorch-gpu python=3.6

进入虚拟环境中

source activate  

切换虚拟环境

conda activate pytorch-gpu

安装pytorch,这里安装版本匹配需要和pytorch匹配,因为cuda9.1不支持新版本的pytroch,安装版本不匹配则无法用cuda成功加速。

pip install torch==0.4.1

pip install torchvision==0.2.2

安装完成后则可以验证一下是否可用。

参考资料: