数据结构与算法
2022-04-25 17:09:21 0 举报AI智能生成
算法思想
作者其他创作
大纲/内容
常见算法思想及案例
1.穷举法
概念
枚举法、暴力破解法、强力法、完全试凑法
基本思想是不重复、不遗漏地穷举所有可能情况
基本思想是不重复、不遗漏地穷举所有可能情况
运用实例
1~100的素数
1~100中数9
所有水仙花数的个数
10000以内的完数
2.递归与分治策略
算法总体思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之
递归概念
直接或者间接地调用自身的算法称为递归算法
用函数自身给出定义的函数称为递归函数
用函数自身给出定义的函数称为递归函数
适用条件
2.1该问题的规模缩小到一定程度就可以容易地解决
2.2该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
2.3利用该问题分解出的子问题的解可以合并为该问题的解
2.4该问题分解出的各个子问题是互相独立的，即子问题之间不包含公共的子问题
这条特征涉及到分治法的效率
如果各子问题是不独立的，则分治法要做许多不必要的工作，重复解公共的子问题，
此时一般用动态规划较好
如果各子问题是不独立的，则分治法要做许多不必要的工作，重复解公共的子问题，
此时一般用动态规划较好
运用实例
汉诺塔
求n！
二分法查找
归并排序
快速排序
二叉树遍历
3.动态规划
总体思想
与分治法类似，将基本问题分解为若干子问题，
但子问题往往不是相互独立的，分治法有些子问题被重复计算了很多次
动态规划有一个表来记录已经解决的子问题的答案，需要时直接找出
但子问题往往不是相互独立的，分治法有些子问题被重复计算了很多次
动态规划有一个表来记录已经解决的子问题的答案，需要时直接找出
基本步骤
3.1找出最优解的性质，并刻划其结构特征
3.2递归地定义最优值
3.3以自底向上的方式计算最优值
3.4根据计算最优值时得到的信息，构造最优解
运用案例
斐波拉契数列
台阶问题
0-1背包问题
4.贪心法
概念
总是做出在当前来看最好的选择，并不从整体来考虑，只是作出在某种意义上的局部最优选择
基本要素
4.1.1贪心选择性质
所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来达到
这是与动态规划的主要区别
4.1.2最优子结构性质
当一个问题的最优解包含其子问题的最优解是，称此问题具有最优子结构性质
这是该问题可用动态规划或者贪心算法求解的关键特征
4.1.3贪心与动态规划的异同
两者都要求问题具有最优子结构性质
背包问题与0-1背包问题
背包问题：可以选择物品的一部分，而不一定是全部
计算单位重量的价值，直至装满
0-1背包：只能是装或者不装，不能多次装或者部分装
0 --- 1
可能最终导致背包未满，此时单位重量价值降低，
在最终方案上，会出现许多互相重叠的子问题，所以动态规划
在最终方案上，会出现许多互相重叠的子问题，所以动态规划
基本思路
4.2.1建立数学模型来描述问题
4.2.2把求解的问题分成若干个子问题
4.2.3对每个子问题求解，得到子问题的局部最优解
4.2.4吧子问题的局部最优解合成原来解问题的一个解
运用实例
冒泡排序
选择排序
背包问题
找零钱问题
活动安排问题
最优装载问题
5.回溯法
概念
走不通就掉头，按某一分支为新出发点，向下探索，
当无法到达目标是，回退到上一出发点，继续探索，
不断回头寻找目标的方法（穷举搜索）
当无法到达目标是，回退到上一出发点，继续探索，
不断回头寻找目标的方法（穷举搜索）
三要素
搜索方式
主要采用深度优先搜索的方式
5.1.1解空间：该问题包含的解
问题的解向量：回溯法希望一个问题的解能够表示为一个n元式（x1，x2...）的形式
显约束：对分量xi的取值限定
隐约束：为满足问题的解而对不同分量之间施加的约束
解空间：对于问题的一个示例，解向量满足显示约束条件的所有元组，构成了该实例的一个解空间
5.1.2约束条件
5.1.3状态树
基本思想
5.2.1针对所给问题，定义问题的解空间
5.2.2确定易于搜索的解空间结构
5.2.3以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
常用剪枝函数
用约束条件在扩展结点处剪去不满足约束的子树
用限界函数剪去得不到最优解的子树
显著特征
在搜索过程中动态产生问题的解空间
实现方式
递归回溯
深度优先
递归实现
迭代回溯
非递归深度优先遍历
6.分支限界法
基本思想
6.1.1以广度优先或以最小耗费(最大利益)优先的方式搜索问题的解空间树
6.1.2每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有的孩子结点。
在孩子结点中，导致不可行或导致非最优解的孩子结点被舍弃，其余加入活结点表中。
在孩子结点中，导致不可行或导致非最优解的孩子结点被舍弃，其余加入活结点表中。
6.1.3之后，在活结点表中取下一个结点成为当前扩展结点，并重复上述结点扩展过程。
一直到找到所需的解或者活结点表为空
一直到找到所需的解或者活结点表为空
与回溯法差异
6.2.1求解目标不同
回溯法：找出解空间树中所有满足约束条件的解
分支限界法：找出满足约束条件的一个解，或在满足约束条件的解中找出最优解
6.2.2搜索方式不同
回溯法：深度优先
分支限界法：广度优先或以最小耗费优先
常见的两种方法
队列式
优先队列式
7.概率算法
基本概念
也叫随机化算法，允许在执行过程中随机选择下一个计算步骤
当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好
当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好
0 条评论
下一页
