文档章节

几种常用的算法简介

hanzhankang
 hanzhankang
发布于 2014/01/21 10:51
字数 2165
阅读 106
收藏 9

1、穷举法

穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解。

穷举法的运用关键在于解决两个问题:

如何列举所有的可能解;

如何判别可能解是否满足条件;

在运用穷举法时,容易出现的问题是可能解过多,导致算法效率很低,这就需要对列举可能解的方法进行优化。

以题1041--纯素数问题为例,从1000到9999都可以看作是可能解,可以通过对所有这些可能解逐一进行判别,找出其中的纯素数,但只要稍作分析,就会发现其实可以大幅度地降低可能解的范围。根据题意易知,个位只可能是3、5、7,再根据题意可知,可以在3、5、7的基础上,先找出所有的二位纯素数,再在二位纯素数基础上找出三位纯素数,最后在三位纯素数的基础上找出所有的四位纯素数。

2、分治法

分治法也是应用非常广泛的一种算法设计策略,其思想是将问题分解为若干子问题,从而可以递归地求解各子问题,再综合出问题的解。

分治法的运用关键在于解决三个问题:

确定分治规则,即如何分解问题。

确定终结条件,即问题分解到什么状态时可以直接求解。

确定归纳方法,即如何由子问题的解得到原问题的解。这一步并不总是需要的,因为对某些问题来说,并不需要对子问题的解进行复杂的归纳。

我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例。

以题1045--Square Coins为例,先对题意进行分析,可设一个函数f(m, n)等于用面值不超过n2 的货币构成总值为m的方案数,则容易推导出:

f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1) 
这里的k是币值为n2 的货币最多可以用多少枚,即k=m/(n*n)。

也很容易分析出,f(m, 1) = f(1, n) = 1

对于这样的题目,一旦分析出了递推公式,程序就非常好写了。所以在动手开始写程序之前,分析工作做得越彻底,逻辑描述越准确、简洁,写起程序来就会越容易。

3、动态规划法

动态规划法多用来计算最优问题,动态规划法与分治法的基本思想是一致的,但处理的手法不同。动态规划法在运用时,要先对问题的分治规律进行分析,找出终结子问题,以及子问题向父问题归纳的规则,而算法则直接从终结子问题开始求解,逐层向上归纳,直到归纳出原问题的解。

动态规划法多用于在分治过程中,子问题可能重复出现的情况,在这种情况下,如果按照常规的分治法,自上向下分治求解,则重复出现的子问题就会被重复地求解,从而增大了冗余计算量,降低了求解效率。而采用动态规划法,自底向上求解,每个子问题只计算一次,就可以避免这种重复的求解了。

动态规划法还有另外一种实现形式,即备忘录法。备忘录的基本思想是设立一个称为备忘录的容器,记录已经求得解的子问题及其解。仍然采用与分治法相同的自上向下分治求解的策略,只是对每一个分解出的子问题,先在备忘录中查找该子问题,如果备忘录中已经存在该子问题,则不须再求解,可以从备忘录中直接得到解,否则,对子问题递归求解,且每求得一个子问题的解,都将子问题及解存入备忘录中。

例如,在题1045--Square Coins中,可以采用分治法求解,也可以采用动态规划法求解,即从f(m, 1)和f(1, n)出发,逐层向上计算,直到求得f(m, n)。

在竞赛中,动态规划和备忘录的思想还可以有另一种用法。有些题目中的可能问题数是有限的,而在一次运行中可能需要计算多个测试用例,可以采用备忘录的方法,预先将所有的问题的解记录下来,然后输入一个测试用例,就查备忘录,直接找到答案输出。这在各问题之间存在父子关系的情况下,会更有效。例如,在题1045--Square Coins中,题目中已经指出了最大的目标币值不超过300,也就是说问题数只有300个,而且各问题的计算中存在重叠的子问题,可以采用动态规划法,将所有问题的解先全部计算出来,再依次输入测试用例数据,并直接输出答案。

4、回溯法

回溯法是基于问题状态树搜索的求解法,其可适用范围很广。从某种角度上说,可以把回溯法看作是优化了的穷举法。回溯法的基本思想是逐步构造问题的可能解,一边构造,一边用约束条件进行判别,一旦发现已经不可能构造出满足条件的解了,则退回上一步构造过程,重新进行构造。这个退回的过程,就称之为“回溯”。

回溯法在运用时,要解决的关键问题在于:

如何描述局部解。

如何扩展局部解和回溯局部解。

如何判别局部解。

回溯法的经典案例也很多,例如全排列问题、N后问题等。

5、贪心法

贪心法也是求解最优问题的常用算法策略,利用贪心法策略所设计的算法,通常效率较高,算法简单。贪心法的基本思想是对问题做出目前看来最好的选择,即贪心选择,并使问题转化为规模更小的子问题。如此迭代,直到子问题可以直接求解。

基于贪心法的经典算法例如:哈夫曼算法、最小生成树算法、最短路径算法等。

但是,贪心法的运用是有条件的,必须能够证明贪心选择能够导出最优解,且转化出的子问题与原问题是同性质的问题,才能使用贪心法求解。

一个比较经典的贪心法求解的问题就是找硬币问题:有1、2、5、10、20、50、100七种面值的硬币,要支付指定的金额,问怎么支付所用的硬币个数最少。这是一个非常日常化的问题,凭直觉我们会想到,尽可能先用大面值的硬币,这就是“贪心选择”,而在这个问题上,这个贪心选择也是正确的。

6、限界剪枝法

限界剪枝法是求解较复杂最优问题的一种算法策略,与回溯法类似的是,限界剪枝法也是在问题状态空间树上进行搜索,但回溯法是搜索一般解,而限界剪枝法则是搜索最优解。限界剪枝法的基本思想是通过找出权值函数的上下界函数,以下界函数来指导搜索的方向,以上界函数来帮助剪除一些不可能含有最优解的分枝。

关于算法和算法策略的讨论是一个非常庞大的话题,几乎每个问题点都能扩展出一大堆可讨论的内容和案例。我实在不知道该怎样用简短的几篇文字就能够把这个话题说透,这里只能蜻蜓点水地对竞赛中经常用到的几种策略做一极为简略的介绍。

也许我们可以在以后的文章中,针对具体的题目进行算法和策略的分析,效果可能会更好。


本文转载自:http://blog.csdn.net/woods2001/article/details/4292518

共有 人打赏支持
hanzhankang

hanzhankang

粉丝 159
博文 220
码字总数 82578
作品 0
海淀
高级程序员
浙大的游戏设计教程

第一部分 游戏程序设计概览 计算机游戏简介:什么是游戏、游戏的分类等 游戏的基本开发流程? 游戏开发的基本理念及方法 游戏软件的体系结构:包括三维游戏引擎的架构分析 游戏的调试与测试 ...

Matrix4X4
2012/08/19
361
2
阿里年薪50WJAVA工程师转大数据学习路线!

大数据有两个方向,一个是偏计算机的,另一个是偏经济的。你学过Java,所以你可以偏将计算机的。 Java程序员想转大数据可行吗?Java是全世界使用人数最多的编程语言。不少程序员选择Java做为...

JAVA丶学习
04/25
0
0
数据挖掘算法及工具教程--DataHref

随着大数据技术的普及,对数据挖掘的需求在不断上升,本项目为一些常用的数据挖掘工具提供中文文档,并提供一部分数据挖掘算法的教程,仍在不断更新中。 mllib、scikit等数据挖掘工具的教程 ...

CrawlScript
2015/12/29
1K
1
后台开发常问面试题集锦(问题搬运工,附链接)

Java基础问题 String的’+’的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记 深入理解Java Stream流水线 抽象 & abstract关键字 Java final 修饰符知识点总结(必看篇) Java中的...

大黄有故事
2017/11/18
0
0
【Java 9】【排序算法】【微信开发】【反钓鱼】【Spring】| Chat · 预告

1 Java 9 平台模块系统初探 作者简介: 成富,十年全栈软件开发经验,精通多门编程语言与前后端开发,涉猎诸多软件技术。 创业公司首席软件工程师。新技术的狂热追求者与布道者。 出版书籍《...

gitchat
2017/11/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
1
0
Spring5对比Spring3.2源码之容器的基本实现

最近看了《Spring源码深度解析》,该书是基于Spring3.2版本的,其中关于第二章容器的基本实现部分,目前spring5的实现方式已有较大改变。 Spring3.2的实现: public void testSimpleLoad(){...

Ilike_Java
今天
1
0
【王阳明心学语录】-001

1.“破山中贼易,破心中贼难。” 2.“夫万事万物之理不外于吾心。” 3.“心即理也。”“心外无理,心外无物,心外无事。” 4.“人心之得其正者即道心;道心之失其正者即人心。” 5.“无...

卯金刀GG
今天
2
0
OSChina 周三乱弹 —— 我们无法成为野兽

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ _刚刚好: 霸王洗发水这波很骚 手机党少年们想听歌,请使劲儿戳(这里) hahahahahahh @嘻酱:居然忘了喝水。 让你喝可乐的话, 你准忘不了...

小小编辑
今天
9
0
vm GC 日志 配置及查看

-XX:+PrintGCDetails 打印 gc 日志 -XX:+PrintTenuringDistribution 监控晋升分布 -XX:+PrintGCTimeStamps 包含时间戳 -XX:+printGCDateStamps 包含时间 -Xloggc:<filename> 可以将数据保存为......

Canaan_
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部