您正在使用IE低版浏览器,为了您的雷峰网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
人工智能 正文
发私信给AI研习社-译站
发送

0

动态规划:二项式序列

本文作者: AI研习社-译站 2019-05-05 10:39
导语:今天,我终于理解了帕斯卡三角的实际应用。

动态规划:二项式序列

本文为 AI 研习社编译的技术博客,原标题 :

Dynamic Programming — Binomial Sequence

作者 | Barun Halder

翻译 | 孙稚昊2  

校对 | 邓普斯•杰弗        审核 | 酱番梨       整理 | 立鱼王

原文链接:

https://medium.com/@bhalder/dynamic-programming-binomial-sequence-62e92d1cc2b1

今天,我终于理解了帕斯卡三角的实际应用。帕斯卡序列是我在大学第一年编程实现的东西。这是一个很有趣的练习。它是一种找到规律并用C或Java编程实现的问题。

动态规划问题可以是非常难的。二项式序列和它的变种问题一直都是我的短板。我从没简单地得到答案,有时即使我有了想法,也不能直接写出可以工作的代码。这是为什么我这次决定尝试一种新的动态规划方法,并且阅读Skiena的前八章。在阅读的过程中,问题被探讨,并且我一下豁然开朗。二项式,帕斯卡三角和动态规划之间的联系被重新建立起来。讽刺的是,我一直困惑的问题,二项式问题的变种的答案,就是我写的第一个程序,帕斯卡三角。

动态规划:二项式序列

帕斯卡三角

帕斯卡三角如上图所示。其中每一个元素都是它正上面两个数字之和。问题就是,什么叫“正上方”?这样的东西要如何在代码中表达?

如果我们用图中的6作为例子,它正上方的两个数字是3和3. 6在第4行,第3列。两个3在上一行--第三行,第二和第三列。同样的规律也适用于第五行的两个10. 现在,我们能够提取的规律是--- 第[n, k] 个元素是 第 [n-1 , k] , [n-1, k-1]个元素的和。

那么,这和二项式原理有什么关系呢?回想一下,二项式数是像这样的:

动态规划:二项式序列

二项式序列

这个的物理意义是:如果我们从n 个元素中选取k  个元素。我们既可以先选择第n 个元素,然后从剩下n- 1个元素中选取 k-1 个,也可以丢掉第n 个元素,从剩下n-1 个元素中选取k 个。我们在帕斯卡三角中看到的对称性在这里很明显。

现在来用代码实现它。如果我们把每个 nCk 的结果存进一个矩阵中,我们可以更高效地计算高维序列。很明显,一个值被计算好后,它会被保存起来给后续的运算使用。这很有记忆化的潜力!

我们先从二项式序列的递归解开始。这里面可以观察到明显的递归关系。对于任何递归函数,初始值都是必须的。对于二项式序列,我们用从n个元素中选取0个元素的情况当作初始值。这样的选择只有一种方法:空集。

另一种初始情况是:从n 个元素集中选取全部的n 个元素,只有一种方法。最后,从n个元素中选取1个,有n种方法。这就是我们需要的所有初始情况。

递归解如下图所示:

动态规划:二项式序列

二项式序列-递归解

注意上面的解法中有很多被重复计算的子问题。为了避免重复计算,我们把中间结果存在一个矩阵中。我们来用一种遍历的方法来实现它。我们先用上文提到的初始情况来填充矩阵。(图中我用了简单的方法,把所有值都初始化为1。这有些浪费)这里只有从n 中取1的情况没被表示。我们要计算得到这种情况。用python 实现的遍历解法如下图所示:雷锋网雷锋网雷锋网

动态规划:二项式序列

二项式序列--遍历解

运行的结果如下图所示:

动态规划:二项式序列

输出结果

在这篇文章中,我们讨论了二项式序列和它与帕斯卡三角之间的关系。我们沿着这个关系,并且意识到有时连接一些点要花10年。我们还讨论了同样解的递归和遍历方法。我很推荐阅读Skiena 和 CLRS 来学习你不熟悉的算法。

继续编程!

想要继续查看该篇文章相关链接和参考文献?

点击动态规划:二项式序列即可访问:

https://ai.yanxishe.com/page/TextTranslation/1416

社长今日推荐:AI入门、大数据、机器学习免费教程

35本世界顶级原本教程限时开放,这类书单由知名数据科学网站 KDnuggets 的副主编,同时也是资深的数据科学家、深度学习技术爱好者的Matthew Mayo推荐,他在机器学习和数据科学领域具有丰富的科研和从业经验。

点击链接即可获取:https://ai.yanxishe.com/page/resourceDetail/417


雷峰网原创文章,未经授权禁止转载。详情见转载须知

动态规划:二项式序列

分享:
相关文章

知情人士

AI研习社(yanxishe.com)译站频道,传播前沿人工智能知识,让语言不再成为学习知识的门槛。(原雷锋字幕组)
当月热门文章
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说