问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 15. 分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝限界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）： 1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
2) （优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找 一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费 的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E-节点是具有最大收益的活节点
16. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同； （4）存储空间的要求不同。
17. 分治法所能解决的问题一般具有的几个特征是： （1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
18. 用分支限界法设计算法的步骤是：
(1)针对所给问题，定义问题的解空间（对解进行编码）； (2)确定易于搜索的解空间结构（按树或图组织解） ；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
19. 常见的两种分支限界法的算法框架：
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
20. 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。
21. 分支限界法的搜索策略是：
在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
22. 请叙述动态规划算法与贪心算法的异同。
共同点：
都需要最优子结构性质， 都用来求有优化问题。 不同点：
动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解； 贪心方法： 自顶向下求解。
可用贪心法时，动态规划方法可能不适用； 可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。 答：
最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.
24. 请说明：
(1)优先队列可用什么数据结构实现？
(2)优先队列插入算法基本思想？ (3)优先队列插入算法时间复杂度？ 答：（1）堆。
（2）在小根堆中，将元素x插入到堆的末尾，
然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字，
则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。 （3）O( log n)
25. 衡量算法时间效率的方法有哪两种？请叙述。 答：有事前分析法和事后分析法两种。
事后分析法：先将算法用程序设计语言实现，然后度量程序的运行时间。 事前分析法：算法的时间效率是问题规模的函数，假如，随着问题规模n的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作： T(n)=○(f(n)) 称T(n)为算法的渐进时间复杂度。简称时间复杂度。
26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况
下，O、Ω、Θ分别提供了算法运行时间的什么界？ 答：
如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。
若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为f(N)=?(g(N))。这时我们说f(N)的阶不低于g(N)的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N))
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均
?
27. 概率算法
很多算法的每一个计算步骤都是固定的，而概率算法允许算法
在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。 28.概率算法的一个基本特征
是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。
29．概率算法大致分为四类:
数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 30.数值概率算法
常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。 31.蒙特卡罗算法
用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。 32.拉斯维加斯算法
不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。 33.舍伍德算法
总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除