初级经济基础
填空题回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。
题目
填空题
回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。
如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案
第1题：
以深度优先方式系统搜索问题解的算法称为()
A.分支界限算法
B.概率算法
C.贪心算法
D.回溯算法
参考答案：D
第2题：
● 迪杰斯特拉（Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 （63） 算法策略
（63）
A. 贪心
B. 分而治之
C. 动态规划
D. 试探＋回溯
正确答案：A
第3题：
矩阵连乘问题的算法可由什么设计实现()
A.分支界限算法
B.动态规划算法
C.贪心算法
D.回溯算法
参考答案：B
第4题：
常见的两种分支限界法的算法框架是什么？
正确答案: （1）队列式（FIFO）分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
第5题：
以下的算法设计方法中，( )以获取问题最优解为目标。
A．回溯方法
B．分治法
C．动态规划
D．递推
正确答案：C
解析：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是；适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。
解析：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是；适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。
第6题：
常见的分支限界法的算法框架有3种。()
此题为判断题(对，错)。
正确答案:×
第7题：
不能保证求得0-1背包问题的最优解。
A．分支限界法
B．贪心算法
C．回溯法
D．动态规划策略
正确答案：B
解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。
解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。
第8题：
分支限界法与回溯法的相同点是()
A.求解目标相同
B.搜索方式相同
C.对扩展结点的扩展方式相同
D.都是一种在问题的解空间树T中搜索问题解的算法
参考答案：D
第9题：
试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？
正确答案: 不同点：求解目标，搜索方式，空间消耗。
回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。
回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。
分支限界法适合解决大量离散最优化的问题。
第10题：
下列哪一种算法是随机化算法（）
- A、贪心算法
- B、回溯法
- C、动态规划算法
- D、舍伍德算法
正确答案:D