当前课程知识点:组合数学 > 线性常系数递推关系 > 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算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验