算法考试中的总结 第1篇

采用STL的priority_queue容器作为优先队列（小根堆），优先队列结点类型与前面的相同，添加比较重载函数，即按结点的length成员值越小越优先出队，为此设计Node结构体的比较重载函数如下：

分支限界法与回溯法的主要区别。

分支限界法对问题的解空间树进行搜索的过程

Ø一次性产生当前扩展结点的所有孩子结点；

Ø在产生的孩子结点中，抛弃那些不可能产生可行解(约束）或最优解的结点（限界）；

Ø将其余的孩子结点加入活结点表；

Ø从活结点表中选择下一个活结点作为新的扩展结点。

Ø重复上述步骤，直到找到一个解或优先队列为空为止。

分支限界法的关键问题

Ø如何确定合适的限界函数。

Ø如何组织待处理活结点表（普通队列和优先队列）。

Ø如何确定最优解中的各个分量。

算法考试中的总结 第2篇

剪枝函数图示：（设置了一个全局变量r，记录剩余元素的和，初值为全部元素的和）

剪左支：若当前子集和+w[i]的和大于C，左子树的所有情况都可以排除；

剪右支：若当前子集和+剩余元素的和小于C，右子树的所有情况都可以排除。

背包问题

有n个重量分别为{w1，w2， … ，wn}的物品，它 们的价值分别为{v1，v2， … ，vn}，给定一个容量为W的背包。设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且满足重量限制具有最大的价值。

思路：

用w[1..n]/v[1..n]存放物品信息，x[1..n]数组存放最优 解，其中每个元素取1或0，x[i]=1表示第i个物品放入背包中， x[i]=0表示第i个物品不放入背包中。

case1：放入物品重量等于W。

T(n)=O(2^n);

增加剪枝函数：

左支：对于第i层的有些结点，tw+w[i]已超过了W（ W=6），显然 再选择w[i]是不合适的。

仅扩展满足tw+w[i]<=W的左孩子结点。

右支：rw=w[i]+w[i+1]+…+w[n]，

当不选择物品i（第i个物品的决策已做出,即不选择第i个物品）时：若tw+rw-w[i]物品，重量也不会达到W，因此不必要再考虑扩展这样的结点。

case2：放入物品重量小于W。

前面左剪枝的方式不变，但右剪枝不再有效，需要改为上界函数进行右剪枝。

 假设当前求出最大价值maxv，若 bound(i)≤maxv，则右剪枝，否则继续扩展。

显然r越小，bound(i)也越小，剪枝越多，为了构造更小的r，将所有物品以单位重量价值递减排列。

后问题

N皇后问题，是一个古老而著名的问题，是回溯算法的典型例题，可以简单的描述为：在N*N格的棋盘上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

 思路：

假设皇后t放在第t行上，用ｎ元组x[1:n]表示ｎ皇后问题的解，x[t]表示皇后t放在第t行的第x[t]列上。

剪枝函数：对于两个皇后i，j    两个皇后肯定不同行

两个皇后不同列：x[i] ≠x[j]

两个皇后不同一条斜线： abs(i-j) ≠ abs(x[i]-x[j])

满n叉树：

2.哈密尔顿回路问题

设G=（V，E）是一个有n个结点的无向图。一条哈密顿回路是通过图中每个结点仅且一次的回路。设计算法，给定一个图，求其是否存在一条哈密顿回路。如果是，输出每一条哈密顿回路；否则给出提示。

思路：

用数组x[n]表示该问题的一组解，x[i]表示在 第i次访问的结点号。

当k=n+1时,当前扩展结点是叶结点。此时需要检测无向图G是否存在一条从顶点x[n]到顶点x[1]的边，如果存在，则找到一条哈密顿回路；否则回溯。当k<=n时，当前扩展结点位于排列树的第k层，若图G中存在从顶点x[k-1]到顶点x[k]的邻接的边时，x[1:k]就构成了图G的一条路径。

6.总结

1.分支限界法与回溯法类似，也是对问题在解空间树上的解决，不同之处在于，回溯法是对解空间树进行深度优先搜索，而分支限界法是对解空间树的广度优先搜索。回溯法的目的是找出所有满足条件的解，而分支限界法目的是找出最优解。

Q：求最优解时，如何选择子结点进行再扩展？

A：设计一个限界函数，计算限界函数值，选择一个最有利的子结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

分支限界法与回溯法比较：

 2.设计思想

①设计合适的限界函数

在搜索解空间树时，每个活结点可能有很多孩子结点，其中有些孩子结点搜索下去是可能产生问题解或最优解。通过设计好的限界函数在扩展时删除不必要的孩子结点，从而提高搜索效率。

②组织活结点表

Ⅰ普通队列式分支限界法

队列式分支限界法将活结点表组织成一个队列，并按照队列先

进先出（FIFO）原则选取下一个结点为扩展结点。步骤如下：

①将根结点加入活结点队列。

②从活结点队中取出队头结点，作为当前扩展结点。

③对当前扩展结点，先从左到右地产生它的所有孩子结点，用约

束条件检查，把所有满足约束条件的孩子结点加入活结点队列。

④重复步骤②和③，直到找到一个解或活结点队列为空为止。

Ⅱ优先队列式分支限界法

优先队列式分支限界法的主要特点是将活结点表组成一个优先

队列，并选取优先级最高的活结点成为当前扩展结点。步骤如下：

①计算起始结点（根结点）的优先级并加入优先队列（与特定问题相

关的信息的函数值决定优先级）。

②从优先队列中取出优先级最高的结点(队头）作为当前扩展结点，使

搜索朝着解空间树上可能有最优解的分枝推进，以便尽快地找出一

个最优解。

③对当前扩展结点，先从左到右地产生它的所有孩子结点，然后用约

束条件检查，对所有满足约束条件的孩子结点计算优先级并加入优

先队列（进队）。

④重复步骤②和③，直到找到一个解或优先队列为空为止。

PS：

优先队列利用堆来实现。堆可以看作一棵完全二叉树的顺序存储结构。在这棵完全二叉树中：Ø 若树非空，且根结点的值均大于其左右孩子结点的值，则称之为大根堆；且其左、右子树分别也是大根堆。Ø 若树非空，且根结点的值均小于其左、右孩子结点的值，则称之为小根堆；且其左、右子树分别也是小根堆。

优先队列的两个基本操作：

出队：堆顶出队，最后一个元素代替堆顶位置，重新调整成堆；

进队：新进队元素放在堆末尾之后，重新调整成堆

优先队列出队操作（以大根堆为例）

• 出队：堆顶出队，最后一个元素代替堆顶位置。除了堆顶外，其他结点均满足大根堆定义，只需将堆顶执行“下沉”操作即可调整为堆。

• “下沉” ：堆顶与其左、右孩子进行比较，若满足堆定义，则不需调整。若不满足，则与其值较大的孩子进行交换，交换后，继续向下调整，直到满足大根堆定义为止

优先队列进队操作（以大根堆为例）

• 进队：进队操作后，除了新进队的元素外，其他结点都满足大根堆的定义，需要将新元素执行“上浮”操作，调整成堆。

• “上浮” ：新进队元素与其双亲比较，如果值小于其双亲，则满足堆定义，无需调整。如果其值比双亲大，则与双亲交换，交换到新位置后，继续向上比较、调整，直到满足大根堆定义为止。

 ③.确定最优解的解向量x

两个X均要入队保存的两种方法：

①对每个扩展结点保存从根结点到该结点的“路径” 。每个结点带有一个可能的解向量。这种做法比较浪费空间，但实现起来简单。（0-1背包问题为例）

②在搜索过程中构建搜索经过的树结构。每个结点记录其双亲的信息，当找到最优解时，通过双亲信息找到对应的最优解向量。（单源最短路径为例）

3.算法性能

在最坏情况下，时间复杂性是指数阶。通过设计限界函数和 约束进行剪枝，提高算法效率

有n个重量分别为{w1，w2，…，wn}的物品，它 们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且重量和不超过W具有最大的价值。

设计限界函数：

对于第i层的某个结点e，用表示结点e时已装入的总重量，用表示已装入的总价值。即对应表示结点e的状态是在确定解向量的[]分量;计算当前结点e对应的状态所能达到的价值上界ub。如果所有剩余的物品都能装入背包， 那么价值的上界 (v[i+1]+…+v[n]) 如果所有剩余的物品不能全部装入背包， 那么价值的上界 (v[i+1]+…+v[k])+(物品k+1装入的部分重量)× 物品k+1的单位重量价值。

注：为了计算出来的上界更加紧凑，需要物品按单位重量价值递减有序。

2.图的单源最短路径问题

给定一个带权有向图G=（V，E），其中每条边的权是一个正整数。另外，还给定V中的一个顶点v，称为源点。计算从源点到其他所有顶点的最短路径长度。这里的长度是指路上各边权之和。

算法考试中的总结 第3篇

【例】有一个含n个整数的数组a，所有元素均不相同，求其所有元素的全排列。

将求取1234（4个元素）全排列的问题转换为：分别取1234交换到第一 个位置作为“开头”，求取剩余元素（3个）的全排列问题（递归体） 当只有一个元素的时候其全排列就是该元素本身（递归出口）

为了提高搜索效率，需要不断使用剪枝函数

约束函数：剪去不满足约束（显式、隐式）条件的子树

限界函数：剪去不能得到最优解的子树

归纳起来，用回溯法解题的一般步骤如下：

1、对于给定的问题，确定问题的解空间，确定解空间树类型（子集树or排列树or满M叉树），问题的解空间树应至少包含问题的一个(最优）解。

2、确定结点的扩展规则。

3、以深度优先方式搜索解空间树，并在搜索过程中可以采用剪枝函数来避免无效搜索。

1.子集和问题

思路：

算法考试中的总结 第4篇

 3.主方法

主方法（master method）提供了解如下形式递归方程的 一般方法：T(n)=aT(n/b)+f(n)

其中a≥1，b>1为常数，该方程描述了算法的执行时间，算法将规模为n的问题分解成a个子问题，每个子问题的大小为 n/b。

例如，对于递归方程T(n)=3T(n/4)+n 2，有：a=3，b=4 ，f(n)=n 2 。

例：

将问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

1.快速排序

2.归并排序

3.查找最大元素和次大元素

思路：

 4.折半查找

5.寻找序列中第k小元素

思路：

对于序列a[s..t]，在其中查找第k小元素的过程如下：

将a[s]作为基准(即最小下标位置的元素为数轴)进行一次划分，

对应的划分位置下标为i。3种情况：

若k=i-s+1 ，a[i]即为所求，返回a[i]。

若k<i-s+1 ，第k小的元素应在a[s..i-1]子序列中，递归在

该子序列中求解并返回其结果。

若k>i-s+1，第k小的元素应在a[i+1..t]子序列中，递归在该

子序列中求解并返回其结果。

6.寻找两等长序列的中位数

对于含有n个元素的有序序列a[s..t]，当n为奇数时，中

位数是出现在m=【(s+t)/2】处；当n为偶数时，中位数下标有

m=【(s+t)/2】（下中位）和m=【(s+t)/2】+1（上中位）两个。为了简

单，仅考虑中位数为m=【(s+t)/2】处。

7.求最大连续子序列和

对于含有n个整数的序列a[0..n-1]，若n=1，表示该序列仅含一

个元素，如果该元素大于0，则返回该元素；否则返回0。

若n>1，采用分治法求解最大连续子序列时，取其中间位置mid=【(n-

1)/2】，该子序列只可能出现3个地方。

（1）该子序列完全落在左半部即a[0..mid]中。采用递归求出其最大连续子

序列和maxLeftSum。

（2）该子序列完全落在右半部即a[mid+1..n-1]中。采用递归求出其最

大连续子序列和maxRightSum。

（3）该子序列跨越序列a的中部而占据左右两部分。

贪心法求解问题步骤：

1）确定合适的贪心选择标准

2）证明在此标准下该问题具有贪心选择性质和最优子结构性质

3）根据贪心选择标准，写出贪心选择的算法，求得最优解。

• 贪心法的基本思路是在对问题求解时总是做出在当前看来 是最好的选择，也就是说贪心法不从整体最优上加以考虑， 所做出的仅是在某种意义上的局部最优解。

• 方法的“贪婪性”反映在对当前情况总是作最大限度的选择，即贪心算法总是做出在当前看来是最好的选择。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最 优的选择，即贪心选择来达到。

也就是说，贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这个选择后产生的相应子问题的解。

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心法求解的关键特征。

贪心算法通常用来解决具有最大值或最小值的优化问题。 它是从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元 素，以便尽快地构成问题的可行解。