当前课程知识点:组合数学 >  线性常系数递推关系 >  Fibonacci数列的应用 >  Fibonacci优选法

返回《组合数学》慕课在线视频课程列表

Fibonacci优选法在线视频

Fibonacci优选法

下一节:艾略特波浪曲线

返回《组合数学》慕课在线视频列表

Fibonacci优选法课程教案、知识点、字幕

我们给大家介绍一下斐波那契在算法中的应用

也是它在优选法有什么用处

我们都知道其实在对应一些函数

或者说一些个序列取值时

我们经常要找最优的那个

而有一些函数它们具有一些特殊的性质

比如说有些函数它具有单峰性

也就是它本身就是一个上升又下降

只有这一个单独的高峰或者低峰

我们称之为是一种具有单峰函数性质

那么我们就问了

在这样一个单峰函数的一个取值区间内

怎么能够找到它的的极值呢

其实一个简单的方法

比如说我们就拿这样一个凸的函数来看

我们想要找到极值点在哪里

很简单

大家会说不停地去试啊

那怎么去试才比较高效呢

比如说在这里

因为它具有单峰性质

所以呢距离极值点越近

那么离极值越接近

离的越远

那么它有可能会越来越偏离极值点

利用这样的性质

我们可以用三分法来进行求解

比如说这样的一个取值区间内

我们把它分成了三等分

在三等分点上

我们分别取一个测试点

然后去测试相应的取值是什么

如果这两个取值它们的最终答案不一样

会有什么样的后果呢

比如说我们这个函数被称为fx

我们现在取值点是在a到b之间

中间取了x1和x2

如果说fx1比fx2要大的话

我们现在要找一个极大值

那意味着既然说它那边已经低了

fx2已经低了

它的右侧相对来说比fx2更低

那没有希望取得极值啊

我们就可以把那一部分删掉

因此通过这样三分法

我们做一次就可以删掉三分之一的空间

那么下一步呢

我们如果说x1比x2大的话

这时候我们去掉的区间是x2部分

如果说正好相反

x1这边小

而x2大的话

那么我们去掉的是x1左边的部分

如果它们俩相等呢

如果他们俩相等

意味着他们两边的都不会达到极值

因此相当于把两边都取掉

在这样的规则下

我们可以一步一步地逐渐利用三分法把我们寻找的区间

逐步逼近到极值

但是就会有一个问题

每次做三分法的时候

我们都需要把它分成三份儿

其中会对两个测试点进行测试

那这时候就会看了

比如说我们举个例子

在这样一个函数中

如果对应的x1是小于x2的

那么我们去去掉什么呢

如果x1小于x2

x1部分呢就会去掉

我们留下的区间实际上是x1到b

在这个区间内

我们还会再取两个点

分别进行测试

这时候我们就会有一个很有意思的问题

比如说在第一次测试的时候

我们测了x1点和x2点

我们将x1左边去掉以后

留下了x1到b的区间

那这时候前一次测试有一个测试点还落在我当前要测试的里面

这个测试点如果用三分法的话

我们就基本上把它扔掉了

那有没有可能把这个点还带着

那么下一步我们再做的时候

只需要再测一个新的测试点

而这个x2点被复用

我们就把我们的测试次数大大地降低了

根据这样的一个思想

我们来分析一下

假如的我们的可行区间正好在0到1之间

这时候我们不再简单的利用三分了

我们用一个x比例

比如说在0到1之间

我们取x和1减x两个点

这两个测试点肯定是落于0到1之间

因为这时候x是小于1大于0的

那么这时候我们如果已经发现了

比如说x这个点它的值更小

那我们会保留哪部分呢

我们会保留0到x部分

那下一步在0到x这个部分呢

我们接着再去乘x

它就变成了x平方再乘以1减x x

它们落在的区间是在0到x之间

但是刚才在这个区间内

有个1减x

我们已经用过了

所以我们就想

是不是有可能这个1减x刚好等于下一步将要测试的点呢

那么有没有可能1减x就等于x平方呢

这时候我们求解一下

x平方加x减1等于0

我们算出来x的一个取值

就是二分之根号5减1

这个值是什么

刚好是黄金分割点

也就是0.618

有了这样一个思路以后

我们来看在0到1之间

我们用这种0.618法该怎么去测试

这时候第一步我选择的点

是0.618和1减去0.618

刚好就是这个0.382这个位置

那么在这个两个测试之后

我发现0.618之后的这个区间偏小

我已经可以把它舍去了

剩下的区间变成了从0到0.618

在这个区间内

我再继续乘以0.618

得到的是下一个测试点

刚好是0.618再乘0.618

这个值刚好等于前面测试过的0.382点

我们来分析一下

利用0.618法怎么进行优选

这时候第一步我们在0到1区间取了两个点

一个点是0.382

一个是0.618

如果说0.618向右侧的所有的点偏小的话

那么留下的区间就是0到0.618

在它们中间我们再继续乘以0.618

下一个测试点是0.236和0.382

可以看到0.382在第一次测试中已经测出来的

所以下一次我只要再做一次新的测试

也就是在0.236点做就可以了

接着往下呢

我们如果又是右侧的偏小的话

接着往下

我们还要继续乘以0.618

得到的是0.146和0.236

同样0.236点上次可以做过了

所以我们会发现

在进行n次的测试中

我们实际上所有的测试点

只需要n加1次

这就是0.618法给我们带来的一个测试点的减少

而同时大家会觉得

0.618要做浮点相乘

对于离散的点来说

并不是适用

所以斐波那契实际上是我们的解决之道

但是大家就会觉得

0.618法总是在进行浮点相乘

其实它的精度误差会很复杂

而且对于离散的点

我们觉得0.618法怎么相乘总会有误差

似乎并不适用

这时候提醒大家就会想到了

斐波那契实际上和0.618有着密切的关系

所以对于处理离散的点的时候

我们经常使用斐波那契方法

比如说对于从0到1这样区间

我们把所有的离散点归结起来

正好也许就能凑足刚好是fn的点

那么从0一直到fn

我们同样在这个区间里选两个点

第一个点是fn减2

第一点是fn减1

在这两个点中进行测试

这时候就会有两种情况发生

我们考虑比如说如果是正好是fn减2这一段偏小的话

那我们将会留下fn减2到fn区间

那么下一步我们该怎么做呢

在fn减2到fn区间

我们照样重新编号

从0开始往后取取取

取到下一个fn减1和fn减2的位置

这时候n实际上比刚才那个n要偏小一个

那这时候我们会发现什么

实际上留下了部分应该有多少个点呢

fn减去fn减2刚好等于fn减1点

所以这时候我们留下的所有测试点

刚好是fn减1个点

fn减1个点再接着往下

可以去取后面的fn减3和fn减2

所以这时候我们会看到

在这个fn减2这个点

原来有个起始点位置是fn减2

所以fn减2加上fn减2

变成了2倍的fn减2

而原来那个点

是fn减3

这时候我们再累加一个fn减2的话

它就正好变成了fn减1

而fn减1在刚才的测试点中已经测过了

所以我们会发现

下一步进行测试的时候

仍然可以省一个测试点

我们分析了其中的一种情况

下面来分析另外一个情况

比如说对应的这样一个区间0到fn

我们是fn的右侧偏小

那这个时候我们留下的区间刚好是从0到fn减1

这fn减1个点

这fn减1个点在依次往前按照斐波那契数去取

当然自然取到的就是fn减2和fn减3

fn减2在第一步我们已经测出来了

这时候我们只需要再测一个fn减3就可以了

所以根据斐波那契的它的性质

我们会发现

同样我们要进行n次测试的话

其实我们只要每次进行求一个新的测试点就可以得到极值点所在

当然还会有些情况

同学们说了

我未必能够凑到正好fn个数

其实没有关系

你只要在后面加若干个虚点

让它变成正好是fn个数

那么其他的测试和原来就是一模一样

只是那些虚点你不需要认真地去做求它的极值了

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Fibonacci优选法笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。