Python使用爬山算法寻找序列“最大值”

爬山算法是人工智能算法的一种,特点在于局部择优,所以不一定能够得到全局最优解,尽管效率比较高。使用爬山算法寻找序列最大值的思路是:在能看得到的局部范围内寻找最大值,如果当前元素已经是最大值就结束,如果最大值仍在前面就往前移动到该最大值位置(往上爬),重复上面的过程。如果原始数据的大小和分布类似于下面的图,那么从右往左爬的话就可以找到全局最大值,并且能节省一些时间。而如果从左往右爬的话无法找到全局最大值,只能找到局部最大值,除非把“邻域”定义的非常大,但是如果邻域定义的非常大的话有时候会严重影响算法效率。

from random import randint

def hillMax(lst, howFar):

'''

lst:待确定最大值的列表

howFar:爬山时能看到的“最远方”,越大越准确

'''

#由于切片是左闭右开区间,所以howFat必须大于1

assert howFar>1, 'howFar must >1'

#从列表第一个元素开始爬

#如果已经到达最后一个元素,或者已找到局部最大值,结束

start = 0

ll = len(lst)

while start <= ll:

m = lst[start]

loc = lst[start:start+howFar]

mm = max(loc)

if m == mm:

return m

else:

#局部最大数的位置

mmPos = [p for p, v in enumerate(loc) if v==mm]

start += mmPos[0]

#测试

lst = [randint(1, 100) for i in range(20)]

print(lst)

print(max(lst))

print(hillMax(lst,6))

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2017-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据风控

R中如何用ifelse进行数据分组

数据分组,根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间部分来研究,以揭示内在的联系和规律性; 在R中,我们常用ifelse函数来进...

38480
来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

12630
来自专栏AILearning

【机器学习实战】第13章 利用 PCA 来简化数据

第13章 利用 PCA 来简化数据 ? 降维技术 场景 我们正通过电视观看体育比赛,在电视的显示器上有一个球。 显示器大概包含了100万像素点,而球则可能...

354110
来自专栏编程理解

动态规划(二):0-1背包

代码中存在两层循环,以二维数组的形式记录中间数据,分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断,分别用于判断空间大小

50710
来自专栏Pulsar-V

用不动点法和牛顿迭代法求解函数根-Julia

30220
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

10220
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

38050
来自专栏小樱的经验随笔

Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

31940
来自专栏WD学习记录

牛客网 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候...

12320
来自专栏技术点滴

算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法

算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法 在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n),本文针对形如T(n)=aT(n/...

27470

扫码关注云+社区

领取腾讯云代金券