9512.net
甜梦文库
当前位置:首页 >> 其它课程 >>

算法复习材料



☆设计思想:动态规划法将待求解问题分解成若干个相互重叠的子问题, 每个子 问题对应决策过程的一个阶段, 一般来说,子问题的重叠关系表现在对给定问题 求解的递推关系中, 将子问题的解求解一次并填入表中,当需要再次求解此子问 题时, 可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计 算。 解题过程:原问题→(子问题 1、子问题 2?子问题 n)→填表→原问题的解 解题

步骤:找出最优解的性质,并刻画其结构特征。递归地定义最优值。以自底 向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。 适用范围:满足最优性原理。 ☆设计思想:根据已有的信息和局部最优原则做出选择, 并且无论结果是什么都 不会改变。 解题过程:考虑以下几个方面: (1)候选集合 C(2)解集合 S: (3)解决函数 solution (4)选择函数 select(5)可行函数 feasible 解题步骤:使用选择函数 select 按照某种贪心策略,从候选集合 c 中选择一个元 素 x,用可行函数 feasible 去判断解集合 s 加入 x 后是否可行,如果可行,把 x 合并到解集合 s 中,并把它从候选集合 c 中删去;否则,丢弃 x,从候选集合 c 中根据贪心策略再选择一个元素,重复上述过程,直到找到一个满足解决函数 solution 的完整解。 适用范围:具有最优子结构性质和贪心选择性质的问题 ☆贪心算法与动态规划算法的差异:以 0-1 背包问题为例,贪心选择之所以不能 得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背 包空间使每公斤背包空间的价值降低了。事实上,在考虑 0-1 背包问题时,应比 较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就 导出许多互相重叠的子问题。 这正是该问题可用动态规划算法求解的另一重要特 征。

☆回溯法的一半框架(递归形式) :主算法 1、X={};2、flag=false;3、advance (1) ;4、if(flag)输出解 X else 输出“无解” ; Advance(int k)1、对每一个 x∈S(下标 k)循环执行下列操作 1.1 x(下标 k) =x;1.2 将 x(下标 k)加入 X;1.3 if(X 是最终解)flag=true;return;1.4 else if (X 是部分解)advance(k+1) ; 回溯法的非递归迭代形式的一半框架: 1、X={};2、flag=flag;3、k=1;4while(k)=1)4.1 当(S(下标 k)没有被 穷举)循环执行下列操作 4.1.1 x(下标 k)=S(下标 k)中的下一个元素;4.1.2 将 x(下标 k)加入 X;4.1.3 if(X 为最终解)flag=true;转步骤 5;4.1.4 else if (X 为部分解)k=k+1;转步骤 4; 4.2 重置 S(下标 k) ,使得下一个元素排在 第 1 位; 4.3 k=k-1; 5、if flag 输出解 X;else 输出“无解” ☆设计思想:首先,确定一个合理的限界函数,并根据限界函数确定问题的目标 函数的界[down, up];然后,按照广度优先策略遍历问题的解空间树:当搜索到 达一个扩展结点时, 一次性扩展它的所有孩子,估算每一个孩子结点的目标函数 的上(下)界值(又称为耗费函数值);将那些满足约束条件且耗费函数值不超过目 标函数的界的孩子, 插入活动结点表 PT 中,再从 PT 表中取耗费函数值极大(小)

的下一结点同样扩展;直到找到所需的解或 PT 表为空为止。其耗费函数值是极 值(极大或极小),则该叶子结点对应的解就是问题的最优解;否则,调整问题的 目标函数的界为该叶子结点的耗费函数值,然后丢弃 PT 表中超出目标函数界的 结点,再次选取结点继续扩展。 解题过程:1.根据限界函数确定目标函数的界[down, up];2.将待处理结点表 PT 初始化为空;3.对根结点的每个孩子结点 x 执行下列操作 3.1 估算结点 x 的目标函数值 value; 3.2 若(value>=down),则将结点 x 加入表 PT 中;4.循环直到某个叶子结点的目 标函数值在表 PT 中最大 4.1 i=表 PT 中值最大的结点; 4.2 对结点 i 的每个孩 子结点 x 执行下列操作 4.2.1 估算结点 x 的目标函数值 value; 4.2.2 若(value>=down),则将结点 x 加入表 PT 中; 4.2.3 若(结点 x 是叶子结点 且结点 x 的 value 值在表 PT 中最大), 则将结点 x 对应的解输出, 算法结束;4.2.4 若(结点 x 是叶子结点但结点 x 的 value 值在表 PT 中不是最大), 则令 down=value, 并且将表 PT 中所有小于 value 的结点删除; ☆分支限界法与回溯法的区别: 求解目标不同: 回溯法——找出满足约束条件的 所有解 分支限界法——找出满足条件的一个解,或某种意义下的最有解搜索方式不同: 回溯法——深度优先分支限界法——广度优先或最小耗费优先。此外,在分支限 界法中,每一个活结点只有一次机会成为扩展结点。



更多相关文章:
算法复习题(精炼版)
算法复习题(精炼版)_数学_高中教育_教育专区。填空题动态规划算法的基本要素为:...材料分析测试与方法复习... 暂无评价 13页 2下载券 辽宁省大连市真金教育信...
分数混合运算练习题[1]
分数混合运算练习题[1]_数学_小学教育_教育专区。分数混合运算练习题一、脱式计算。 (能简便的要简便运算。 )(请同学们认真审题,弄清运算 顺序,再细致计算。)...
算法复习题1
算法复习题1_数学_高中教育_教育专区。1、二分搜索算法是利用( A、分治策略 ...2014教师资格材料分析辅... 2014小学教师资格考试《... 2014年幼儿园教师资格考...
简便算法练习题
简便算法练习题_四年级数学_数学_小学教育_教育专区...出示练习纸复习(一)第 5 题,怎样简便就怎样计算...2014教师资格材料分析辅... 2014小学教师资格考试《...
算法设计与分析复习
算法设计与分析复习题_工学_高等教育_教育专区。研究生算法复习题算法设计与分析复习题 1、一个算法应有哪些主要特征? 有限性、确定性、输入、输出、可行性 2、...
智能计算复习题1
、 2. 计算智能算法主要包括: (神经计算)(进化计算)和模糊模糊计算三个分 、...智能计算复习题 3页 免费 计算智能复习资料 4页 免费 计算智能复习 11页 ...
小数乘法简便运算练习题
小数乘法简便运算练习题_数学_小学教育_教育专区。人教版五年级数学上册专项练习题 小数乘法简便运算练习题 一、简便运算 0.25×8.5×4 12.5×0.96×0.8 0.25×...
数据结构与算法复习提纲(详细版)
数据结构与算法复习提纲(详细版)_工学_高等教育_教育专区。严蔚敏版教材数据结构与算法复习提纲 第一章 引论 一、数学知识复习 1、对数(重要公式:XA=B 当且仅当...
五年级数学简便计算练习题
五年级数学简便计算练习题_数学_小学教育_教育专区。五年级数学简便计算练习卷下面各题怎样算简便就怎样算。 (1)小数加减法计算 6.9+4.8+3.1 0.456+6.22+3.78...
小学数学五年级上册简便计算及解方程练习题集锦
小学数学五年级上册简便计算及解方程练习题集锦_数学_小学教育_教育专区。小学数学五年级上册简便计算练习 1 一、请用简便方法计算下列各题 0.25×0.28 0.125×3...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图