文档章节

几种常用的算法简介

hanzhankang
 hanzhankang
发布于 2014/01/21 10:51
字数 2165
阅读 103
收藏 9
点赞 0
评论 0

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

粉丝 158
博文 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
程序员?这些面试题你能答对几个?

  三人行必有我师,人生是需要不断学习的,在这里我们相遇就是缘分,希望各位可以看完这篇文章,也欢迎大家在下面留言讨论,天冷了,也动动手指转发收藏一下,谢谢大家!   一、数据结构...

java分享
2017/12/03
0
0
Java 进阶面试问题列表

翻译自Java developer interview questions: The hard part 面向对象编程的基本理念与核心设计思想 解释下多态性(polymorphism),封装性(encapsulation),内聚(cohesion)以及耦合(cou...

大黄有故事
2017/01/17
0
0
机器学习(四)--- 从gbdt到xgboost

gbdt(又称Gradient Boosted Decision Tree/Grdient Boosted Regression Tree),是一种迭代的决策树算法,该算法由多个决策树组成。它最早见于yahoo,后被广泛应用在搜索排序、点击率预估上...

云栖希望。
2017/12/04
0
0
缓存失效策略(FIFO 、LRU、LFU三种算法的区别)

当缓存需要被清理时(比如空间占用已经接近临界值了),需要使用某种淘汰算法来决定清理掉哪些数据。常用的淘汰算法有下面几种: FIFO:First In First Out,先进先出。判断被存储的时间,离...

weixin_37589896
2017/12/07
0
0
【office培训】【王佩丰】Excel2010视频教程第1讲:认识Excel 2010

Excel 2010 入门系列视频教程,每周更新一期,每期一小时。 本视频将从最基础的内容开始,涵盖Excel常用工具、函数、数据分析工具、图表等工作中常用的内容。是一套全面学习Excel2010的零基础...

xiaopei050
06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

arts-week1

Algorithm 594. Longest Harmonious Subsequence - LeetCode 274. H-Index - LeetCode 219. Contains Duplicate II - LeetCode 217. Contains Duplicate - LeetCode 438. Find All Anagrams ......

yysue
16分钟前
0
0
NNS拍卖合约

前言 关于NNS的介绍,这里就不多做描述,相关的信息可以查看NNS的白皮书http://doc.neons.name/zh_CN/latest/nns_background.html。 首先nns中使用的竞价货币是sgas,关于sgas介绍可以戳htt...

红烧飞鱼
49分钟前
0
0
Java IO类库之管道流PipeInputStream与PipeOutputStream

一、java管道流介绍 在java多线程通信中管道通信是一种重要的通信方式,在java中我们通过配套使用管道输出流PipedOutputStream和管道输入流PipedInputStream完成线程间通信。多线程管道通信的...

老韭菜
今天
0
0
用Python绘制红楼梦词云图,竟然发现了这个!

Python在数据分析中越来越受欢迎,已经达到了统计学家对R的喜爱程度,Python的拥护者们当然不会落后于R,开发了一个个好玩的数据分析工具,下面我们来看看如何使用Python,来读红楼梦,绘制小...

猫咪编程
今天
1
0
Java中 发出请求获取别人的数据(阿里云 查询IP归属地)

1.效果 调用阿里云的接口 去定位IP地址 2. 代码 /** * 1. Java中远程调用方法 * http://localhost:8080/mavenssm20180519/invokingUrl.action * @Title: invokingUrl * @Description: * @ret......

Lucky_Me
今天
1
0
protobuf学习笔记

相关文档 Protocol buffers(protobuf)入门简介及性能分析 Protobuf学习 - 入门

OSC_fly
昨天
0
0
Mybaties入门介绍

Mybaties和Hibernate是我们在Java开发中应用的比较多的两个ORM框架。当然,目前Mybaties正在慢慢取代Hibernate,这是因为相比较Hibernate而言Mybaties性能更好,响应更快,更加灵活。我们在开...

王子城
昨天
2
0
编程学习笔记之python深入之装饰器案例及说明文档[图]

编程学习笔记之python深入之装饰器案例及说明文档[图] 装饰器即在不对一个函数体进行任何修改,以及不改变整体的原本意思的情况下,增加函数功能的新函数,因为这个新函数对旧函数进行了装饰...

原创小博客
昨天
1
0
流利阅读笔记33-20180722待学习

黑暗中的生物:利用奇技淫巧快活生存 Daniel 2018-07-22 1.今日导读 如果让你在伸手不见五指的黑暗当中生存,你能熬过几天呢?而大千世界,无奇不有。在很多你不知道的角落,有些生物在完全黑...

aibinxiao
昨天
6
0
Hystrix降级逻辑中如何获取触发的异常

通过之前Spring Cloud系列教程中的《Spring Cloud构建微服务架构:服务容错保护(Hystrix服务降级)》一文,我们已经知道如何通过Hystrix来保护自己的服务不被外部依赖方拖垮的情况。但是实际...

程序猿DD
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部