试题详情
- 简答题简述贪心法和动态规划法思路的异同。
- 贪心法和动态规划法都是用于解决多阶段决策的最优化问题。基本的求解思路,都是 把一个复杂的问题分解为若干子问题,通过对子问题求解的一系列的决策或选择,最后得到原问题的解。但是,两者的决策方法不相同。贪心法总是把原问题分解为一系列较为简单的局部最优选择,每一步选择都是在当前状态下做出的最优选择,同时扩展了当前的部分解,直到求得问题的完整解。这个贪心选择过程是以自顶向下的方式进行的,即从原问题出发,每做一步贪心选择都把问题简化为规模更小的子问题,直到对规模最小的子问题做出贪心选择。动态规划法中,分解成的子问题具有两个特点。其一,子问题之间往往不是互相独立的,而是有重叠的部分,这种重叠关系通过动态规划函数表现出来,为了避免对重叠部分的重复计算,以表格形式保存每一步对子问题的求解结果,当需要再次求解已经解决的子问题时,只要做简单的查表操作即可。其二,每个子问题对应决策过程的一个阶段,每步所做的决策往往依赖于相关子问题的解,因此,只有在解决了相关的子问题之后,才能做出决策或选择。正因为此,其求解子问题时,通常以自底向上的方式进行,即从求解最后分解得到的子问题开始,逐层向前,最后求得原问题的解。
关注下方微信公众号,在线模考后查看
热门试题
- ()的遍历仍需要栈的支持
- 栈和队列都是()。
- 线性表的链接存储比顺序存储最有利于进行(
- 数据的逻辑结构在计算机内存中的表示是()
- 计算机算法指的是(),它具备输入,输出和
- 线性表(a n,a2,…’an)中,每个
- 线性表的两种存储结构分别为()和()
- 假定用一个单循环链表来表示队列(也称为循
- 下述哪一条是顺序存储结构的优点()。
- 非空二叉排序树的任意一棵子树也是二叉排序
- 当待排序序列的关键字次序为倒序时,若需为
- 链表是采用链式存储结构的线性表,进行插入
- 下列选项中不是算法的特性是()。
- 对长度为n的查找表进行查找时,假定查找第
- 二叉树是一棵无序树。
- 广度优先遍历类似于二叉树的()
- 深度为k(k>=1)的二叉树至多有()个
- 任何一棵二叉树的叶子结点在先序、中序和后
- 数据结构里,由n(n>=0)个结点的有限
- (1)以1,2,3 ,6,7