△什么是算法 算法的特性是什么
算法是指解决问题一种方法或一种过程。算法是由若干条指令组成的有穷序列。特性：输入、输出、确定性、有限性。
△算法的时间复杂法与问题的什么因素有关？
要解决的问题的规模 算法的输入 算法本身的函数
△简述递归算法相比于非递归算法的优缺点
优点：由于递归算法结构清晰，可读性强，且容易用数学归纳法证明算法的正确性，因此它为设计算法、调试程序带来很大方便
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。


△简述分治法基本思想。
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
△常见的分支限界法有哪两种，特点是什么
1.队列式分支限界法 特点：队列式分支限界法将活结点表组织成一个队列，并按队列先进先出原则选择下一个结点为当前扩展结点。
2.优先队列式分支限界法 特点：优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

△什么是备忘录方法？与动态规则法有什么区别？它在什么情况下较为有效？
备忘录方法是动态规则算法的变形，与动态规则算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。
区别：与动态规则算法不同的是：备忘录方法的递归方式是自顶向下的，而动态规则算法则是自底向上递归的。
一般来讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利。
△什么是剪枝函数
回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树，其二是用限界函数剪去得不到最优解的子树，这两类函数统称为剪枝函数。

△简述回溯法设计算法的步骤。
1.针对所给问题，定义问题的解空间
2.确定易于搜索的解空间结构
3.以深度优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
△什么是子集树和排列树？遍历他们需要花费的时间？
当所给的问题是从N个元素的**S中找出满足某种性质的子集时，相应的解空间树称为子集树。遍历子集树任何算法均需要Ω(2^n)的计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。遍历排列树需要Ω(n!)的计算时间。

△分支限界法与回溯法相同点，不同点
相同点：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法
不同点：1.一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即某种意义下的最优解。
2由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间


△分治法与动态规划法相同点，不同点。
相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
不同点：1.与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。2.若用分治法来解这类问题，则分解得到的子问题数目太多，以至于最后解决问题需要耗费指数时间。3.然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，如果我们能保存已解决的子问题的答案，而在需要时再找出已得的答案，这样就可以避免大量的重复计算。
△简述动态规划的主要步骤和基本要素。
1.找出最优解的性质，并刻画其结构特征
2.递归的定义最优值
3.以自底向上的方式计算出最优值
4.根据计算最优值时得到的信息，构造最优解
基本要素：最优子结构性质，子问题重叠性质。

→_→