知到答案算法分析与设计（山东联盟）智慧树答案_2022年

第八章

回溯法是按广度优先策略搜索解空间树。
答案:错
死结点是正在产生儿子的结点。
答案:错
回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。回溯法不适用于解一些组合数相当大的问题。
答案:错
好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。下列算法中，通常以深度优先方式系统搜索问题解的是（ ）。
贪心法
回溯法
动态规划法装载问题的回溯算法所需的计算时间为
O（nlogn）
O（2ⁿ）
O（n²）问题的状态生成法有（）
子集树生成法
深度优先生成法
排列树生成法回溯法解题步骤
针对所给问题，定义问题的解空间
确定最优子结构的性质
确定易于搜索的解空间结构回溯法的效率依赖于下列哪些因素（ ）
确定解空间的时间
计算约束函数的时间 
满足显约束的值的个数剪枝函数包括（ ）和约束函数
限界函数

最优函数
估计函数回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。
答案:错
回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O( n! ) 计算时间. 回溯法的两种解空间树为（）