今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》,虽然工作这么几年没在什么地方用过算法,但算法的思想还是影响深刻的,可以在系统设计时提供一些思路。大致翻了翻,重温了一下几种几种经典的算法,做一下小结。
- 分治法
- 动态规划
- 贪心算法
- 回溯法
- 分支限界法
分治法
1)基本思想
将一个问题分解为多个规模较小的子问题,这些子问题互相独立并与原问题解决方法相同。递归解这些子问题,然后将这各子问题的解合并得到原问题的解。
2)适用问题的特征
- 该问题的规模缩小到一定的程度就可以容易地解决
- 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题
3)关键
- 如何将问题分解为规模较小并且解决方法相同的问题
- 分解的粒度
4)步骤
分解->递归求解->合并
- divide-and-conquer(P)
- {
- if ( | P | <= n0) adhoc(P); //解决小规模的问题
- divide P into smaller subinstances P1,P2,...,Pk;//分解问题
- for (i=1,i<=k,i++)
- yi=divide-and-conquer(Pi); //递归的解各子问题
- return merge(y1,...,yk); //将各子问题的解合并为原问题的解
- }
google的核心算法MapReduce其实就是分治法的衍生
5)分治法例子:合并排序
规约过程:
动态规划
1)基本思想
将待求解问题分解成若干个子问题,但是经分解得到的子问题往往不是互相独立的,如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算
2)适用问题的特征
- 最优子结构
- 在递归计算中,许多子问题被重复计算多次
3)步骤
- 找出最优解的性质,并刻划其结构特征。
- 递归地定义最优值。
- 以自底向上的方式计算出最优值。
- 根据计算最优值时得到的信息,构造最优解。
贪心算法
1)基本思想
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择
2)适用问题的特征
- 贪心选择性质,即所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
- 最优子结构性质
3)步骤:不断寻找局部最优解
4)例子:找硬币,哈夫曼编码,单源最短路径,最小生成树(Prim和Kruskal)
最小生成树图示:
回溯法
1)基本思想
在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索
2)适用问题的特征:容易构建所解问题的解空间
3)步骤
- 定义问题的解空间
- 确定易于搜索的解空间结构
- 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索
4)回溯法例子:N皇后问题
分支限界法
1)基本思想
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非 最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找 到所需的解或活结点表为空时为止。
2)分支限界法例子:单源最短路径问题
问题描述:在下图所给的有向图G中,每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
相关推荐
本论文主要研究用于训练 Pi-Sigma 神经网络的几种梯度学习算法的相关理论问题,包括学习效率、收敛性等.另外,在网络结构优化方面做了一些尝试. 本论文的结构及内容如下: 第一章回顾有关神经网络的一些背景知识....
对于计算机科学专业的学生和从业者,本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士,它确实打开了每天所使用的工具的核心——算法世界的大门。”—— G. Ayorkor Korsah,阿什西大学...
6. 2 几种经典的载波跟踪环 6. 2. 1 抑制载波跟踪环的结构形式 6. 2. 2 松尾环的QPSK解调 6. 2. 3 16QAM解调环 6. 2. 4 通用载波恢复环 6. 3 数字Costas环的设计 6. 3. 1 数字Costas环的功能部件及参数设计 6. 3. 2 ...
在回顾经典算法的基础上,对近期的图像去模糊算法研究进展进行分类分析,从自然图像统计特性、图像边缘、字典学习这三个方面介绍了近期经典的图像去模糊算法研究进展,并给出了几种有代表性算法的实验结果。...
介绍了几种常用的符号率盲估计方法,简单回顾了基于循环相关符号率盲估计的基 本算法,在此基础上,通过理论分析提出一种基于循环相关符号率盲估计的快速实现方法。该方 法利用FFT 运算代替循环频率遍历搜索,计算量...
摘要我们回顾了几种可用于解决将矩形打包成二维有限分箱问题的算法。大多数提出的算法都在文献中得到了很好的研究,但有些变体鲜为人知,有些显然被视为“民间传说”,以前
本文针对性地介绍了几种常用的单片机系统RAM测试方法,并在其基础上提出了一种基于种子和逐位倒转的RAM故障测试方法。一、RAM测试方法回顾方法1:一种测试系统RAM的方法是分两步来检查,先后向整个数据区送入#00H和#...
然后我们解释了算法偏差的潜在来源并回顾了几种偏差校正方法。 最后,我们讨论了代理的战略行为如何导致有偏见的社会结果,即使算法本身是无偏见的。 我们最后讨论开放性问题和未来的研究方向。
主要包含两部分,一部分是数据结构的代码实现(src/data-structures),另一部分是leetcode算法题的实现(src/algorithms),有的题目会有几种实现方式。 算法刷题练习步骤 5-10分钟:读题和思考 有思路:自己开始做和写...
模糊降质图像的恢复是图像...在回顾经典算法的基础上,对近期的图像去模糊算法研究进展进行分类分析,从自然图像统计特性、图像边缘、字典学习这三个方面介绍了近期经典的图像去模糊算法研究进展,并给出了几种有代表性
然后,他们通过在工作站上实施几种传统的对称加密算法,设计了一系列实验,以评估三种主要类型方法的有效性。 实验结果表明,与不间断电源系统电池相比,外部测量和软件配置文件更为准确。 功耗的改善分别为27.44和...
最近在面试中,除了基础&算法&项目之外,经常被问到或被要求介绍和描述下自己所知道的几种分类或聚类算法(当然,这完全不代表你将来的面试中会遇到此类问题,只是因为我的简历上写了句:熟悉常见的聚类 &分类算法...
本文针对性地介绍了几种常用的单片机系统RAM测试方法,并在其基础上提出了一种基于种子和逐位倒转的RAM故障测试方法。 一、 RAM测试方法回顾 方法1:一种测试系统RAM的方法是分两步来检查,先后向整个数据区送入#...
本报告对最先进的 ODP 算法进行了系统回顾和基准测试。 进一步介绍了一种新的算法“智能超像素”,专门为在显微图像中检测空气真菌孢子而开发。 基准测试考虑了几个关于算法速度、空间效率、召回准确度、定位精度和...
第 4 章设计了三种鲁棒预测控制算法,并比较了几种典型粒子滤波器的 估计精度 与计算速度; 第 5 章针对跟踪问题,设计了非线性预测控制器; 第 6、7 章将 预测控制应用于具体系统; 第 8 章对全书工作进行了回顾和...
首先回顾了与变分包含问题...这种等价性允许使用预解算子技巧提出一种新型的Man迭代算法。最后对算法的收敛性进行了分析,在所给定理条件下,利用文献[3]中被广泛应用的一个引理,不仅可以证明这类变分包含问题存在唯一解
这种新证明的优点是它将导致几种新的学习算法。 我们证明了深度神经网络实现了扩展并且扩展已经完成。 首先,我们简要回顾一下基本的玻尔兹曼机,以及玻尔兹曼机的不变分布会产生马尔可夫链。 然后,我们回顾θ变换...
本文回顾了几种最新开发的用于保水结构(WRS)的最低成本优化设计的技术,这些技术综合了渗流的影响。 这些措施包括将不确定性纳入非均质土壤参数估算和可靠性量化。 这篇评论仅限于基于耦合仿真优化(SO)模型的...