搜索
2.设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。3.分支限界法与回溯法的相同点与不同点相同点：（1）都是一种在问题的解空间树T中搜索问题解的算法。不同点：（1）求解目标不同；（2）搜索方式不同；（3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。4.分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。5.用分支限界法设计算法的步骤是：(1)针对所给问题，定义问题的解空间（对解进行编码）(2)确定易于搜索的解空间结构（按树或图组织解）(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。6.分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。7.算法的要特性是什么？（1）确定性（2）可实现性（3）输入（4）输出（5）有穷性8.算法分析的目的是什么？分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。9.算法设计中常用的算法设计策略？（1）蛮力法；（2）倒推法；（3）循环与递归；（4）分治法；（5）动态规划法；（6）贪心法；（7）回溯法；（8）分治限界法10.１、动态规划算法基本思想？动态规划算法与分治算法异同点？适合用动态规划算法求解问题的基本要素？动态规划算法的基本步骤？答：1）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算.2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。不同：用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归；动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环;3）基本要素：具有最优子结构；子问题具有重叠性4）步骤：1)分析最优解的性质，并刻划其结构特征。2)递推地定义最优值。3)以自底向上的方式计算出最优值.4)根据计算最优值时得到的信息，构造问题的最优解11.贪心算法基本思想？答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解12.贪心算法的基本要素？（1）贪心选择性（2）最优子结构13.贪心算法与动态规划算法的异同?答：1）相同点：对于要求解的问题都具有最优子结构；2）不同点：算法的基本思想不同；求解问题的类型不同；14常用的两种分支限界算法？并说明其思想？（1）队列式（FIFO先进先出）分支限界算法将活动结点表组织成一个队列，并按照队列先进先出原则取下一个结点作为扩展结点基本思想：①开始，根结点是唯一的活结点，根结点入队列；从活结点队中取出根结点后，作为当前扩展结点。②对当前扩展结点，先从左到右地产生它的所有儿子(分支)，用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点队列中。③再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。（2）优先队列式分支限界算法将活结点表组织成一个优先队列（堆），并按照优先队列中规定的结点优先级，选取优先级最高的结点作为当前扩展结点。基本思想：①根结点是唯一的活结点，根结点入堆；从活结点队中取出根结点后，作为当前扩展结点。②对当前扩展结点，先从左到右地产生它的所有儿子节点；用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点表中（堆），并给每个结点设置优先级。③再从活结点表(堆)中取出堆顶结点(堆中优先级最高结点)为当前扩展结点，……，直到活结点表(堆)为空。16什么是易解问题？什么是难解问题？难解问题分为哪两类？（1）易解问题：人们将存在多项式时间算法的问题称为易解问题;（2）难解问题：将需要在指数时间内解决的问题称为难解问题；（3）难解问题有两类：1）不可判定问题2）非决定的难处理问题。17什么是不可判定问题？什么是非决定的难处理问题？（1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。（2）非决定的难处理问题：这类问题是可判定的（即可解的）。但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。18什么是P类问题？什么是NP完全问题？（1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。（2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。