1700495169
算法之美：指导工作与生活的算法 发牢骚的权利：噪声与健壮性
1700495170
1700495171
将算法应用于体育的另外一个方法，也许是更加重要的方法，即不要问我们应该在银牌上有多大的信心，而是看我们应该对金牌有什么样的信心。
1700495172
1700495173
迈克尔·特里克解释说，在一些体育项目中，“例如棒球，无论哪支球队，都会输掉30%的比赛，都会赢得30%的比赛”。对于单淘汰赛制而言，这个事实就会产生令人不安的影响。比如说，美国大学体育协会锦标赛在70%的比赛中是更强大的球队获胜，并且冠军需要在6场比赛中连续获胜，那么最好的球队只有0.7的6次方（不到12%）的概率夺冠！换句话说，联盟中最优秀的球队每10年才会夺得一次冠军。
1700495174
1700495175
在一些体育项目中，哪怕对一场比赛的结果有70%的信心，也可能会让人们过于相信最后的比分。加州大学圣迭戈分校的物理学家汤姆·墨菲利用数值模拟技术来研究足球，结果发现足球的得分通常比较低，因此比赛结果的随机性远远超出了大多数球迷的想象。他说：“如果比分是3：2，那么获胜球队实力强于对手的概率只有5/8……就我个人而言，我觉得这并不是一个难以接受的事实。即使是6：1的完胜，也有7%可能是统计学上的一个巧合。”
1700495176
1700495177
计算机科学家把这种现象称作噪声。我们目前所考虑的所有排序算法都假设我们可以完美地完成比较这个步骤，而且比较结果准确无误，绝不会发生优劣颠倒的情况。一旦你接受“带噪比测器”，计算机科学中被人们敬若神明的算法就会走下神坛，而受到最多诟病的算法也有死灰复燃的机会。
1700495178
1700495179
新墨西哥大学计算机科学教授戴夫·阿克利研究的是计算机科学和“人工生命”的交叉领域。他相信生物学对计算机有一定的借鉴意义。首先，在生物生活的世界中，几乎所有过程的可靠性都比不上计算机不可或缺的那种可靠性，因此必须从头开始，培养研究人员所谓的健壮性。阿克利称，从现在开始，我们也应该认识到算法健壮性的好处。
1700495180
1700495181
因此，尽管权威的编程巨著《排序与搜索》大胆地宣称：“冒泡排序并没有明显的可取之处。”阿克利和合作伙伴的研究却表明，冒泡排序等算法或许可以卷土重来。冒泡排序的效率的确低下——每次只移动一个位置，但是它们对抗噪声的能力比较强，远胜于合并排序等速度更快的算法（在这种算法中，每一次比较都有可能将一个物品移动非常长的距离）。合并排序的效率非常高，因此健壮性不足。在合并排序早期发生错误，就会像在第一轮淘汰赛中意外失利一样，不仅会使有望夺冠的球队希望破灭，还会把球员们的排名永久性地降到半数球队之后。[1]另一方面，排位赛与冒泡排序相似，意外失利只会让运动员的排名下降一个位置。
1700495182
1700495183
但是，在带噪比测器面前表现最好的并不是冒泡算法，获得这项殊荣的是一种叫作比较计数排序的算法。在该算法中，每个排序对象都会与其他对象做比较，从而统计出比该排序对象小的对象一共有多少个。这个数字可以直接表示该排序对象的排名。因为比较计数排序让所有的排序对象都结对比较，因此与冒泡排序一样，它也是一个平方时间算法。正因为如此，它在传统的计算机科学应用程序中并不是一个深受欢迎的选择，但是它的容错能力非常强。
1700495184
1700495185
这个算法的作用原理听起来应该很熟悉。比较计数排序与循环赛十分相似。换句话说，就像一个运动队参加常规赛一样：与同一赛区中所有其他球队一一对垒，并通过胜败记录决出名次。
1700495186
1700495187
在所有已知的算法中，包括平方时间算法和其他更优秀的算法，比较计数排序是最健壮的排序算法。了解这个事实应该可以帮助体育迷们正确面对某些具体情况。如果球队没有进入季后赛，就不要怨天尤人了。采用合并排序的季后赛有运气的成分，但是采用比较计数排序的常规赛是无法碰运气的。冠军戒指也许不是那么可信，但是分区的排名货真价实。换句话说，如果一支球队在季后赛早早出局，那是运气太差。但是如果一支球队不能进入季后赛，那这就是一个严酷的事实了。失望的球队球迷可能会在运动酒吧里向他们表示同情，但是计算机科学家不会心生任何怜悯。
1700495188
1700495189
[1]值得注意的是，美国大学体育协会的“疯狂三月”锦标赛有意识地采取了某些安排，以缓和算法中的缺陷。前面说过，单淘汰赛制的最大问题是实力排第二位的球队有可能第一个被击败淘汰，从而跌进名次表的下半部分（没有具体名次）。为了解决这个问题，美国大学体育协会采取了设立种子队的办法，这样排名靠前的球队不能在较早轮次中相遇。设立种子的效果似乎比较可靠，至少没有出现最极端的情况。在“疯狂三月”的历史上，16号种子从来没有击败过1号种子。
1700495190
1700495191
1700495192
1700495193
1700495195
算法之美：指导工作与生活的算法 杀戮排序：啄食顺序与优势等级
1700495196
1700495197
在我们目前考虑的所有例子中，每一个案例中的排序过程都是按照自上而下的顺序进行的，例如图书管理员把图书上到书架上，美国大学体育协会告诉各运动队的赛程安排。但是，如果在纯粹自愿的情况下进行面对面直接比较呢？自下而上、按部就班地完成排序工作，情况又会怎么样呢？
1700495198
1700495199
这种情形可能与在线扑克游戏相似。
1700495200
1700495201
大多数体育运动都有这样那样的管理机构，但是在过去10年里迅速蹿红的扑克游戏仍然是一种无人管理的状态。尽管一些高知名度的赛事会确定参赛玩家的排名（作为发放奖金的依据），但是有相当一部分人仍然利用扑克玩“现金游戏”。两名以上玩家自发地达成一致之后，就可以在网上游戏，为每一手牌押上现金。
1700495202
1700495203
几乎没有人比艾萨克·哈克斯顿更了解扑克世界，他是世界上最好的扑克现金游戏玩家之一。在大多数体育运动中，只要可以充分发挥就足够了，无须过分在意自己的技术水平。但是，哈克斯顿解释说：“在某些方面，作为职业扑克玩家，最重要的技能是能够评估自己的水平。如果你不是世界上最优秀的扑克玩家，如果你总想和更优秀的玩家同台竞技，那么你最终必将倾家荡产。”
1700495204
1700495205
哈克斯顿是无限注单挑扑克游戏的专家。“单挑”的意思是一对一，而“无限注”的意思就是赌注不设上限，只要你的筹码和胃口可以接受就没有问题。在多人现金扑克游戏中，通常会有一个比较弱的玩家（比如一个富有的业余爱好者），他会把满桌子的职业玩家都喂饱。在这种情况下，那些赢家就不会太关心谁的牌更好。单挑游戏的情况完全不同，“你和对手肯定都认为自己的牌更好，除非有一方甘心认输”。
1700495206
1700495207
那么，如果大家的意见都非常一致，不愿意和更优秀的玩家游戏，会有什么样的结果？这种情况与玩家争取游戏席位非常相似。大多数在线扑克网站的牌桌数量有限。哈克斯顿说：“假设只有10张牌桌可以玩盲注为50美元和100美元的无限注单挑游戏，那么只有10个公认的水平最高的玩家能坐到桌边，等着人去和他们玩。”这时候，如果一个超级玩家坐到其中一张桌子上，会怎么样呢？如果原先坐在那里的那位玩家不愿下赌注，他们就都会离开那张桌子。
1700495208
1700495209
克里斯托弗·诺依曼说：“假设有两只猴子。一只猴子坐在那里，正在慢条斯理地吃东西。这时候，另一只猴子走了过来，来到第一只猴子的旁边。通常，第一只猴子就会站起来，离开那里。”
1700495210
1700495211
诺依曼并不是用猴子来比喻扑克牌游戏。他是纳沙泰尔大学的行为生物学家，研究方向是猕猴的优势等级。他举那两只猴子的例子，目的是介绍转位这个概念。
1700495212
1700495213
如果一个动物根据它对等级概念的了解，判断不值得实施某个对抗行为，就会发生转位这种现象。在很多动物群体中，资源、机会、食物、配偶、受欢迎的空间等都非常稀缺，因此群体必须决定如何分配这些资源和机会。预先建立好秩序是一种比较温和的机制，这样，当出现一个交配机会或者发现一片茂盛的草地时，群体成员不至于相互争斗。尽管看到生物利用利爪、坚喙互相攻击时，我们可能会感到不寒而栗，但生物学家常常把啄食顺序视为一种以暴制暴的预防手段。
1700495214
1700495215
听上去是不是有点儿耳熟？其实搜索与排序的取舍问题在本质上是一样的。
1700495216
1700495217
创立啄食顺序，可以从根本上解决一个重要的计算问题。顺便说一句，农场为鸡去喙以免彼此争斗的做法可能是出于好意，但是效果往往适得其反，因为它剥夺了个体为秩序而战的权利，这会大大增加了整个鸡群执行排序程序的难度。结果，在许多情况下，鸡群内部的对抗不减反增。
[
上一页 ]
[ :1.700495168e+09 ]
[
下一页 ]