“算法设计与分析”课程基本概念复习参考。
1、 什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。
答：算法是指解决问题的方法和过程。
算法的基本特征。
1） 输入：有零个输入或者、多个外部量作为算法的输入；
2） 输出：算法产生出一个量作为输出；
3） 确定性：组成算法的每条指令是清晰地，无歧义的；
4） 有限性：算法中的每条指令执行的次数有限，执行每条指令的时间也有限。
算法与程序相同点和不同点。
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的有限性。
课件之“绪论”，教材之“绪论”，page:1）
2、 请描述算法设计的一般过程。（课件之“绪论”）
1） 先选用该问题的一个数据模型。
2） 看清楚问题数据模型在一直条件下的初始状态和要求的结果状态，以及这两个状态间的隐含关系；
3） 探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。
3、 什么是算法复杂性？它主要有哪两个方面构成？（课件之“绪论”）
算法复杂性：算法运行时所需要的计算机资源的量。
构成：时间复杂性，即需要时间资源的量。
空间复杂性，即需要空间资源的量。
4、 时间复杂性分析主要分哪三种情况，哪种情况的可操作性最好，最具有实际价值？（课件之“绪论”）
1）分三种情况。
最好的情况：
平均情况：最坏的情况：
2）实践表明：可操作性最好，最具有实际价值的是最坏情况下的时间复杂性。
5、 熟练掌握算法复杂性分析中符号“o”的运算规则。（教材之“绪论”，page:15）
6、 请问二分搜索算法、快速排序算法、线性时间选择算法和最近点对问题的时间复杂性各为多少？（教材之“递归与分治”，page:27,37,39,43）
1） 二分搜索方法充分利用了元素间的次序关系，可在最快的情况下用时间完成搜索任务。因为最坏的情况，while循环被执行了次，循环体内运算需要o(1)的时间，因此整个算法的时间复杂度为。
2） 快速排序法： 解为。
3） 线性时间选择算法：
4） 最近点对算法：
7、 分治算法和动态规划算法都是通过对问题进行分解，通过对子问题的求解然后进行解重构，从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。（课件之“递归与分治”，课件之“动态规划”）
分治法：将一个问题划分成大小相等的k个子问题的处理方法行之有效。
分治法的求解过程---分解，递归求解，合并。
动态规划：i. 分解后的子问题往往不互相独立；
ii. 采用记录表的方法来保存所有已解决问题的答案。
在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
）8、 动态规划算法的本质是什么，请简要阐述。（课件之“动态规划”）
动态规划的实质是分治思想和解决冗余。
因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有贪心实质，但是各个子问题又不是完全零散的。
9、 如果一个问题可以利用动态规划算法求解，那么该问题应满足什么条件？（教材之“动态规划”，page:67）
最有子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
子问题的重叠：用递归算法子顶向下求解问题时，每次产生的子问题之间存在重叠现象。
10、 动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。（教材之“动态规划”，page:61）
1）基本思想：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
2）动态规划算法的一般步骤。
1) 找出最优解的性质，并刻画其结构特征；
2) 递归地定义最优值；
3) 以自底向上的方式计算出最优值；
4) 根据计算最优值时得到的信息，构造最优解；
11、 什么是备忘录方法？它同动态规划法相比主要不同点是什么？请指出动态规划法和备忘录方法各自的适用范围。（课件之“动态规划”）
1）备忘录方法动态规划算法的变形，采用**保存已经解决的子问题答案，下次需要时查看即可。
2）与动态规划算法的不同之处。
i. 动态规划算法：自底向上递归求解。
ii. 备忘录方法：自顶向下递归求解。
其控制结构与直接递归方法的控制结构相同，但备忘录方法为每个求解过的子问题建立了备忘录以备需要时查看。
3)运用方面：
a)当一个问题的所有子问题都至少要解一次时，建议使用动态规划算法（动态规划算法没有任何多余计算）
b)当子问题空间中的部分子问题不需要求解时，建议使用备忘录方法（从其控制结构可以看出，该方法只求解那些需要求解的子问题）
12、 贪心算法的设计思想是什么，有什么特点？如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件？（课件之“贪心算法”，教材之“贪心策略”,page110）
1）贪心算法的设计思想与特点：
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
在做出贪心选择后，原问题简化为规模更小的类似子问题。
用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的全局最优解。
2） 应该满足贪心选择性质与最优子结构性质。
13、 请简要描述回溯法的实现过程。用回溯法求解0/1背包问题、tsp问题、n皇后问题和连续邮资问题时，其各自的解空间树各是什么形式？(课件之“回溯法”，教材之“回溯法”page147）
1）实现过程：“通用解题法”——系统地搜索问题的所有解。
在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。当搜索到解空间树的任一结点时，先判断该结点是否包含问题的解。
如果确定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。
2）0/1背包问题：完全二叉树。
tsp问题：用完全ｎ叉树表示解空间。
n皇后问题：
连续邮资问题；
14、 影响回溯法效率的主要因素有哪些？如何有效地估算回溯法在求解具体实例时产生的中间节点数量？(课件之“回溯法”，教材之“回溯法”page187，188）
1）主要因素。
a) 产生x[k]的时间。
b) 满足显约束的x[k]值的个数。
c) 计算约束函数constrain的时间。
d) 计算上界函数bound的时间。
e) 满足约束函数和上界函数约束的所有x[k]的个数。
2）可用概率方法估算回溯法将产生的节点数。
15、 请简述分支限界法的算法思想以及两种主要的实现方法。(课件之“分支限界法”，教材之“分支限界法”page195，196）
1) 思想：在解空间树上搜索问题解的方法，但是求解目标：找出满足约束条件的解（可行解或最优解）
i. 队列式fifo分支限界法：将活结点表组织成一个队列，并按队列的先进先出fifo原则选取下一个结点作为当前扩展结点；
ii. 优先队列式分支限界法：将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级，选取剩余队列中优先级最高的下一个结点作为当前扩展结点；
16、 请指出回溯法与分支限界法的相同点与不同点。(课件之“分支限界法”）
相同点：1) 两者在进行问题求解前，都需要完成解空间的定义和组织；
2) 都是通过在解空间搜索来寻找问题的解。
不同点：a）搜索方式。
i. 回溯法：深度优先；
ii. 分支限界法：广度优先；
b）搜索策略。
iii. 回溯法：根据剪枝函数，选择下一个扩展接点并按深度优先方式进行搜索；
iv. 分支限界法：在扩展结点处，先产生其所有的子结点（分支），然后根据限界函数，确定哪些子结点将导致不可行解或非最优解，将这些子结点剔除，用剩下的子结点构造当前的活结点表，然后从该表中取一个结点作为当前扩展结点，并重复上述过程；
17、 概率算法主要有哪些类型？它们各自的主要特点是什么？如何有效提高概率算法获得正确解的概率或提高算法的求解精度？(课件之“概率算法”，教材之“概率算法”page241）
1) 数值概率算法。
常用于数值问题的求解，得到的往往是近似解。
解的精度随计算时间的增加而提高。
在许多情况下，计算出问题的精确解是不可能或没必要。
2) 蒙特卡罗算法。
用于求解问题的准确解。
在有些情况下，近似解没有意义，比如“0/1”判定问题。
可以求得问题的一个解，但该解未必正确。
求得正确解的概率依赖于算法的计算时间。
蒙特卡罗算法的主要缺点就在于无法有效判定所得到的解是否肯定正确。
3) 拉斯维加斯算法。
不会得到不正确的解，但有时找不到问题的解。
找到正确解的概率随算法计算时间的增加而提高。
用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。
4) 舍伍德算法。
总能求解得到问题的一个解，而且所求得得解总是正确的。
当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定算法中引入随机性，将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的差别。
舍伍德算法的精髓：不是避免算法的最坏情况，而是设法消除这种最坏情形行为与特定实例之间的关联性。
算法设计与分析复习
12 动态规划算法基本思想 自底向上 全局最优 讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质 问题的最优解包含了其子问题的最优解 子问题重叠性质 在用递归算法自顶...
算法设计与分析复习
分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...
算法分析与设计复习
一 迪杰斯特拉算法。1 对下图中的有向图，应用dijkstra优化算法计算从源顶点0到其它顶点间最短路径。2 利用优化的dijkstra算法求解以节点1为源节点到其他各个节点。的的最短路径。用贪心法求解，写出具体步骤 二 多波段图问题。1 用动态规划法求下图中从源点0到终点8的最短路径，写出具体步骤...