启发：什么样的算法是巧妙的算法？-新东方前途出国

启发：什么样的算法是巧妙的算法？

为了让搜索的速度更快，我们可以采用“空间换时间”的方式，为书籍提前制定索引卡。算法中其实有很多类似的精妙设计。  

但在外人的眼中，很难看出哪些算法巧妙，哪些又比较一般。这就像欣赏电影一样，“外行看热闹，内行看门道”。  

咱们不求让你成为算法专家，但我希望能帮你在算法的欣赏上入个门，了解在算法工程师眼里，算法的“巧妙”之处。咱们就从三个算法中常见的问题出发，看看什么样的算法是巧妙的算法。  

1 效用选择模型：近似现实且保持可解性  

第一个问题是，如何用模型对现实世界进行近似。为什么这一点很重要呢？算法是用数学公式表达的计算方法，和现实之间有一条鸿沟。而数学模型是连接这两端的桥。  

桥的选址有讲究，模型的选择也一样。算法工程师怎么评判哪个数学模型更巧妙呢？咱们来看一个实际问题。  

我们知道，美国的总统是全民选出来的。不过，说是“全民”选的，但其实有大约40%的人从来不投票。  

如果竞选团队能提前找到这些人，就可能增加给自己投票的选民数量。所以这些选民是两个政党竞选团队的主攻对象。  

问题来了，怎么找到这些选民呢？  

有调查显示，年轻人，尤其是18到24岁的年轻人，投票率只有大约40%，大大低于其他年龄段。那是不是说，集中精力专攻年轻选民就可以了呢？  

这样效果肯定不好。因为这个模型距离现实太远了。  

你想想，影响一个选民投不投票的因素，除了年龄，肯定还有其他的，比如性别、族裔、受教育程度、职业，等等。而且，知道年轻人的投票率低，并不能让你知道他们的决策过程是什么样的，你也就不知道该怎么影响他们。  

那怎么做才能贴近现实呢？算法学家做了一个大胆又合理的假设。  

他们认为，人们在做选择的时候，一般会选那个能给自己带来最大满足感的选项。苹果和橘子，如果苹果能给你的满足感更大，你就会选苹果。这有个比较学术的词，叫效用。人们会选择对自己来说效用最大的选项。  

在这个假设的基础上，我们刚刚说的年龄、性别、族裔等等，都是影响一个人对“投票”或者“不投票”两个选项效用的因素。只要能把这些因素对效用的影响用公式表示出来，我们就能预估每个选民投不投票的可能性。这种模型就比较贴近现实了。  

但新的问题又来了。  

影响效用的因素太多，有些因素之间还有复杂的相关关系。比如说，年纪小并不直接影响投票意愿，但很多人因为投票日要上班，这才没投票。这只是个简单的例子，在实际当中，影响人投票效用的因素就更复杂了。  

如果把这些复杂的情况都考虑在模型里，贴近现实是做到了，但数学模型太复杂，就求不出来解了。  

这时候必须简化模型。算法学家又做了一个假设，假设所有因素之间的关系，只是线性叠加，相互之间没有复杂的交互。这样，模型就变得可解了。  

在算法领域，这个数学模型叫“线性效用模型”。 算法学家就是用这个模型，去找到那些不愿意投选票的人的。  

你看，如果数学模型建立得过于粗糙，把实际问题中的重点漏掉了，算法得到的结果也就不能重新应用回现实。而如果一个数学模型非常贴近现实，却没有有效的算法能帮助求解，那也没有用。  

所以，能不能合理地近似现实，同时保持可解性，是算法工程师评价一个模型是不是巧妙的重要角度。  

2 德州扑克：问题规模的减小  

有时候，我们即使有了明确的数学模型描述，但仍旧面临问题规模太大的问题。规模大得计算机也没法处理了，就得想办法扔掉一些信息。但是怎么扔、扔哪些，就是学问了。  

我们拿德州扑克游戏举个例子。  

在德扑游戏中，每个玩家有两张自己的手牌，每张手牌有52种可能性。牌桌中间会发5张公共牌，每张牌也有52种可能性。每个玩家可能会下注四轮。因为下注的金额是任意的，所以每次下注对应的情况就更多。  

所有的可能性组合在一起，有10的71次方那么多种，比宇宙中原子的数量稍微小点儿。别说人类没法计算，就是计算机也计算不了。  

但是最近几年，有一种“德州扑克算法”，就解决了这个原本被认为不可能解的问题。  

2017年1月，四个世界著名的德州扑克选手汇聚在美国城市匹茨堡，和一个叫Libratus的算法大战了20天。结果他们每个人都败下阵来。  

为什么德州扑克算法这么厉害呢？其中一个原因，就是它通过把相似的状态合并，处理了德州扑克规模巨大的问题。  

这是什么意思呢？比如说你的两张手牌是，梅花K和黑桃K。这种情况和红桃K加方片K是一样的。我们就可以把它们合并当成一种状态。这一下就把要处理的总可能性减小了6倍。  

这样不断合并不同的状态，德州扑克算法就把问题降到了一个计算机可以处理的规模。  

能减小规模的算法有很多，它们背后的思想都是通过舍弃了少量信息，把一个大到不能计算的问题减小到了计算机可以处理的规模。这也是算法工程师说一个算法巧妙的重要角度。  

3 探索与利用：迭代得到结果  

不管是前面说的建立数学模型，还是缩小规模，我们都是为了能通过算法得到一些答案。  

但算法中有一类常见的问题，就是如果不能直接得到答案，那怎么办？  

比如咱们来看一个例子。  

假设有位算法工程师，叫小扎，是个男青年。他每次跟女孩约会，问对方下次什么时候见面的时候，女孩经常回绝他。他也很有意思，觉得女孩拒不拒绝他，跟他穿的衣服颜色有关。他想知道到底穿哪种颜色更能博得女孩的好感。  

在小扎最近的记录中，10次穿蓝衣服的约会，有6次女孩答应了继续见面。而2次穿黄衣服的时候，对方只同意了1次。  

是蓝颜色好，还是黄颜色好？这个答案就不能直接得到。那怎么办呢？  

小扎可能简单算一算，穿蓝衣服时候的成功率更高，于是从此永远选择穿蓝色衣服。  

但这个办法有个问题，就是他记录的次数太少了，其实黄色的更好，只是还没显现出来，但他已经放弃了探索其他可能性的机会。  

更好的办法是什么样的呢？  

小扎是个算法工程师嘛，他为两个颜色分别设计了一个随机数生成器。蓝色随机数生成器会生成一个平均值为0.6的数，黄色随机数生成器会生成一个平均值为0.5的数。哪个随机数大，他约会就穿哪个颜色的衣服。  

现在蓝色随机数的平均值比较大，小扎穿蓝色的可能性也就大些。但还是有穿黄色的机会。如果黄色表现更好，小扎会把黄色随机数生成器的数值调得更高，这样将来选黄色的机会就更大了。小扎不断得到更多的数据，更新随机数的平均值，到最后，就会非常确定到底哪个颜色更好。  

其实视频网站的算法，就是这样的逻辑。你一定有过这样的体验：刚开始用的时候，视频网站会给你推荐各种广受用户喜欢的内容，过一段时间，它就开始推荐一些你最常看的内容了。对我来说，推荐的就都是英超和西甲的足球比赛集锦。  

这个过程在算法领域叫“探索与利用”。  

所谓“探索”，就是不断推荐各式各样的视频内容，看看我更容易观看什么。这就相当于，小扎在知道蓝色衣服更好的情况下，也没有放弃探索穿黄色衣服的可能性。  

所谓“利用”，就是在知道我对足球感兴趣的时候，更多地推荐足球视频给我看。这就相当于，小扎在不断调整两种颜色的随机数，逐步确定了哪个颜色更容易成功。  

在算法问题中，不能一蹴而就得到答案的情况有很多。这时算法能不能通过不断迭代，最终得到解决方案，同时又能保证很高的效率，也是算法工程师评价它巧不巧妙的重要角度。  

总结一下这一讲的内容。能不能利用模型来逼近现实，同时保证模型的可解性，能不能减小问题的规模，能不能高效地逐步逼近结果，都是算法工程师评价一个算法巧不巧妙的重要角度。  

如果把这三个角度合在一起，你会发现，巧妙的算法常常有一个特点，就是背后的思想符合人的直觉。算法工程师厉害的一个原因，就是能把直觉的思路以一种明确的方式表达出来，转换成算法，然后攻克复杂问题。

在线咨询！

【免责声明】

1、个别文章内容来源于网络善意转载，版权归原作者所有，如侵权，请联系删除；

2、所有图片来源于网络，版权归原作者所有。如有侵权问题请告知，我们会立即处理。