算法概论复习提纲

发表于 | 分类于 ，

一、简答题

记号O、Ω、Θ 的意义？

  • O：表示若存在f(n)=O(g(n))时，则f(n)当n充分大时有上界，且g(n)为它的一个上界
  • Ω：表示若存在f(n)=Ω(g(n))时，则f(n)当n充分大时有下界，且g(n)为它的一个下界
  • Θ：表示当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))时，称f(n)与g(n)同阶

分治法的基本步骤？

  1. 分解(Divide)：将要解决的问题分解成若干规模较小的同类子问题
  2. 解决(Conquer)：递归求解子问题
  3. 合并(Combine)：将子问题的求解结果恰当合并，得到原问题的解

动态规划算法的两个基本要素？

  1. 最优子结构性质
  2. 重叠子问题性质

设计动态规划算法的步骤？

  1. 找出最优解的性质，并刻画其结构特征；
  2. 递归地定义最优值；
  3. 以自底向上的方式计算出最优值；
  4. 根据计算最优值时得到的信息，得到最优解。

分治法与动态规划两种算法策略的异同点？

同：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解；
异：适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

贪心法的两个基本要素？

  1. 贪心选择性质
  2. 最优子结构性质

贪心法的算法正确性证明的基本策略？

贪心算法的正确性证明虽然不容易，但一些常见的方法还是值得总结的。

  • 构造法
    根据描述的算法，用贪心的策略，依次构造出一个解，可证明一定是合法的解，即用贪心法找可行解。 如有N个士兵(1≤N≤26)，编号依次为A，B，C，…。队列训练时，指挥官要把一些士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“P1比P2高”这样的比较结果(P1，P2∈A，B，C，…，Z，记为P1>P2)，如“A>B”表示A比B高。 请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。 注：比较结果中没有涉及到的士兵不参加排队。

  • 反证法
    用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，可以证明是矛盾的。从而S1就是最优解。如在一个超市，有N个人排队到一个柜台付款，已知每个人需要处理的时间为Ti（0<i≤N），请你找一种排列次序，使每个人排队的时间总和最小。

  • 调整法
    用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，找出不同之处，在不破坏最优性的前提下，逐步调整S2，最终使其变为S1。从而S1也是最优解。

贪心法与动态规划两种算法策略的异同点？

同：都要求问题具有最优子结构性质
异：动态规划算法为自底向上的方式解各子问题，贪心法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每一次贪心选择问题就转换为规模更小的子问题。

最大流的概念、流通（circulation）的概念？

最大流：最大流量的问题涉及发现通过单一来源，单汇流网络，它是一个最大可行流。
流通（circulation）：

最大流最小割定理的内容及其证明方法？

最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割
具体的证明分三部分：

  1. 任意一个流都小于等于任意一个割
    这个很好理解 自来水公司随便给你家通点水 构成一个流
    恐怖分子随便砍几刀 砍出一个割
    由于容量限制 每一根的被砍的水管子流出的水流量都小于管子的容量
    每一根被砍的水管的水本来都要到你家的 现在流到外面 加起来得到的流量还是等于原来的流
    管子的容量加起来就是割 所以流小于等于割
    由于上面的流和割都是任意构造的 所以任意一个流小于任意一个割
  2. 构造出一个流等于一个割
    当达到最大流时 根据增广路定理
    残留网络中s到t已经没有通路了 否则还能继续增广
    我们把s能到的的点集设为S 不能到的点集为T
    构造出一个割集C[S,T] S到T的边必然满流 否则就能继续增广
    这些满流边的流量和就是当前的流即最大流
    把这些满流边作为割 就构造出了一个和最大流相等的割
  3. 最大流等于最小割
    设相等的流和割分别为Fm和Cm
    则因为任意一个流小于等于任意一个割
    任意F≤Fm=Cm≤任意C
    定理说明完成

网络流：最大流，最小割 基本概念及算法

多项式归约（reduction）的概念与用途？

可归约意指对每个问题L，总有一个多项式时间多对一变换，即一个决定性的算法可以将实例l ∈ L 转化成实例c ∈ C，并让c回答Yes当且仅当此答案对l也是Yes。为了证明某个NP问题A实际上是NPC问题，证明者必须找出一个已知的NPC问题可以变换成A。

P 问题、NP问题、NP完全问题、NP困难问题（NP-hardproblem）的概念？

P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
NP问题：NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
NP完全问题：同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。(即只要解决这个问题，所有的NP问题都可以得到解决)
NP困难问题：它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比NPC问题的范围广）。

概念详述

NP完全问题的实际证明方法？

目前为止，所有已知解NPC问题的算法需要依照数据数量而定的超多项式（superpolynomial）时间，目前也不知道是否有任何更快的算法存在。因此要在输入数据量大的时候解决一个NPC问题，通常我们使用下列的手段来解：

  • 近似算法：这类算法可以快速发现离最佳解在一定差距内的次佳解。
  • 乱数算法：此类算法可提供一乱数产生的输入数据，让本质上解答分布均匀的受测程序可以有良好的求解效率。对于解答分布不均匀的程序，则可以降低乱数程度以改变输入数据。
  • 特例：此算法可以在题目呈献某些特殊情况时快速得解。参数化复杂度（Parameterized complexity）可视为广义的此类算法。
  • 启发式算法：这种算法在许多时候可以产生理性解答（即运用评比或线索找出解），但无法保证它效率的良莠与解答的好坏程度。一个启发式算法的例子是用在图着色问题以O（n log n）的贪婪算法找次佳解，用在某些编译器的寄存器配置阶段上，此技术又叫图着色全域寄存器配置（graph-coloring global register allocation）。每顶点视为一变数，每边代表两变数同时使用的情况，颜色则代表配置给每一变数的寄存器编号。由于大多数的RISC机器拥有大量通用寄存器，因此启发式算法很适合用来解这类题目。

NP完全-wiki百科

常见的NP完全问题？

  • 图着色问题
  • 哈密顿回路问题
  • TSP问题

NP问题例子详述

递归方程的求解方法？

  1. 递推法
  2. 公式法
  3. 生成函数法

递归方程求解方法综述-百度文库

二、应用题

多段图上的最短路径动态规划推导

阶段：将图中的顶点划分5个阶段，k
状态：每个阶段有几种供选择的点s
决策：当前状态应在前一个状态的基础上获得。决策需要满足规划方程
规划方程：f(k)表示状态k到终点状态的最短距离。
初始条件：f(k)=0;
方程：f(k-1)=min{f(k)+W(k-1,k)}其中W(k-1,k)表示状态k-1到状态k的距离

最大流最小割问题的求解算法Ford-Fulkerson及应用

Ford-Fulkerson方法依赖于三种重要思想：残留网络，增广路径和割。Ford-Fulkerson是一种迭代的方法。开始时，对所有的u,v属于V，f(u,v)=0(这里f(u,v)代表u到v的边当前流量)，即初始状态时流的值为0。在每次迭代中，可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直到增广路径都被找出为止。
最大流问题Ford-Fulkerson方法
Ford–Fulkerson algorithm-wiki

强连通分量的划分算法

Kosaraju算法、Tarjan算法、Gabow算法皆为寻找有向图强连通分量的有效算法。但是在Tarjan 算法和 Gabow 算法的过程中，只需要进行一次的深度优先搜索，而Kosaraju算法需要两次DFS，因而相对 Kosaraju 算法较有效率。这些算法可简称为SSC(strongly connected components)算法。
Kosaraju 算法即为算法导论一书给出的算法，比较直观和易懂。这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。 它利用了有向图的这样一个性质，一个图和他的transpose graph(边全部反向)具有相同的强连通分量！
算法思路：

  1. DFS遍历原图，对每个访问到的节点标记时间戳（访问完成时间）。
  2. 按照时间戳的降序DFS遍历反向图，得到的每个连通块就是一个强连通分量。
    算法步骤如下：
  3. 创建一个空的栈 ‘S’ ，然后对图做DFS遍历. 在顶点访问完成后加入栈中。访问完成是说回溯返回时，而不是第一次发现该节点时。fillOrder()函数
  4. 得到图转置，即将所有边反向。
  5. 从S中依次弹出每个顶点，设为 ‘v’. 将v看做遍历的源点 (调用 DFSUtil(v)). 做第二次DFS遍历，可以找到以v为起点的强连通分量，打印出即可。
    时间复杂度
    DFS遍历的时间复杂度为O(V+E) ，图的转置也为O(V+E) 。因此总的时间复杂度为O(V+E)。
    从渐进分析来说，这个复杂度是最好的，但是用到了两次DFS遍历，还有一个常见的更高效的算法 Tarjan’s algorithm ，后面再做讨论。
    应用
    在社交网络上，有些群体可能是强连通的(例如一个班级的学生)，这些群体中的人一般会有一些共同感兴趣的页面或游戏，可以使用SSC算法来找到这样的群体，然后推荐相关的页面或游戏。
    求强连通分量-Kosaraju算法

    图的深度优先搜索算法的扩展及应用

深度优先搜索-百度百科

Bellman-Ford算法的基本思想及应用


递归方程的求解方法

递归方程求解方法综述-百度文库