第六讲 计算思维之问题求解思想—5
《第六讲 计算思维之问题求解思想—5》由会员分享，可在线阅读，更多相关《第六讲 计算思维之问题求解思想—5（32页珍藏版）》请在文档大全上搜索。
1、主题四算法策略大搜罗 枚举算法 递推算法 递归算法 迭代算法 分治算法 贪心算法 回溯算法某女相亲贪心算法定义算法定义 贪心算法（Greedy Algorithm），是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。即通过局部最优决策能得到全局最优决策。贪心算法特点 算法特点有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合。随着算法的进行，将积累起其它两个集合：一个包含已经被考虑
2、过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。最后，目标函数给出解的值。贪心算法思路 算法思路贪心算法的主要思路是：建立数学模型来描述问题。把求解的问题分成若干个子问题。对每一子问题求解，得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。对于一个给定的问题，往往可
3、能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪心算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪心算法求解则特别有效。贪心算法案例 算法案例【背包问题】假定有N个物体和一个背包，物体I 有质量WI，价值为PI，而背包的载荷能力为M。当PI最大时，装入的物品总重量不超过背包容量：WI=M。这个问题称为背包问题（Knapsack Problem）。若将物体I的一部分XI（1=I=N,0=X
4、I=1)装入背包中，则有价值PI*XI；在约束条件（W1*X1+W2*X2+WN*XN)=M下；使目标(P1*X1+P2*X2+PN*XN)达到极大，此处0=XI0,1=I=N。贪心算法案例算法案例 【背包问题】 能直接得到最优解的算法就是枚举算法。但是现在运用贪心算法来实现这个问题的一个近似最优解。 根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ 每次挑选所占空间最小的物品装入是否能得到最优解？ 每次选取单位容量价值最大的物品，成为解本题的策略。 贪心算法案例算法案例 【背包问题】选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。要想得到最优解，就要在效益增长和
5、背包容量消耗两者之间寻找平衡。也就是说，总应该把那些单位效益最高的物体先放入背包。首先挑选pi/wi最大但又符合约束条件WI=M的物品，并记录I，如果不满足约束条件，就选下一个，直到所有物品都被遍历。将所有记录的I值输出，就是被选中可以装入背包中的物品序号。主题四算法策略大搜罗 枚举算法 递推算法 递归算法 迭代算法 分治算法 贪心算法 回溯算法回溯算法定义 算法定义 回溯法（Back-Track Algorithm）是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解空间（Solution Space）树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结
6、点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯算法特点 算法特点 回溯算法从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路； 回溯算法其实就是一种枚举算法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯算法思路算法思路 用回溯算法解决问题的一般步骤：针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。确定易于搜
7、索的解空间结构,使得能用回溯法方便地搜索整个解空间。以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。回溯算法思路算法思路其基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以
