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
创立啄食顺序，可以从根本上解决一个重要的计算问题。顺便说一句，农场为鸡去喙以免彼此争斗的做法可能是出于好意，但是效果往往适得其反，因为它剥夺了个体为秩序而战的权利，这会大大增加了整个鸡群执行排序程序的难度。结果，在许多情况下，鸡群内部的对抗不减反增。
1700495218
1700495219
从计算机科学的角度看动物的行为，可以给我们几点启示，其中之一便是，随着群体增大，每个个体遭遇敌意对抗的次数就会显著增加（至少成对数增长，甚至是平方增长）。事实上，对母鸡“争斗行为”的研究发现，“每只母鸡的攻击性行为会随着鸡群增长而增长”。因此，排序理论表明，牲畜的“道德培养”可能包括限制牲畜的群体规模。（生活在野外的野鸡群规模在10~20只之间，远小于商业农场中的鸡群。）研究还表明，几周之后，攻击行为就会逐渐消亡，除非有新的成员加入群体。这个发现表明，动物群体是一个秩序井然的群体。
1700495220
1700495221
威斯康星大学麦迪逊分校复杂性计算及集体计算中心的联合主任杰西卡·弗莱克认为，要理解自然界中的这种分散排序，关键是要知道优势等级归根结底是信息等级。弗莱克指出，对于这些分散的分类系统来说，计算的难度非常大。例如，在猕猴群体中，只有在每只猴子都对等级关系有一个非常详细（而且彼此差不多）的理解时，打斗的频次才会降至最低，否则暴力事件就会层出不穷。
1700495222
1700495223
说到动物对当前秩序的了解程度，我们可能需要寄希望于它们的推理与记忆能力。只有提高这些能力，才会减少对抗。或许人类与最高效排序的距离最近。在说到扑克游戏时，哈克斯顿说：“我算不上是世界一流的单挑无限注德州扑克游戏玩家。我心中有一个非常具体的前20名优秀玩家排名表，我想他们心中也有类似的名单。我觉得，大家对这样一个名单的意见高度一致。”只有排名有分歧时，才会有现金游戏。
1700495224
1700495225
1700495226
1700495227
1700495229
算法之美：指导工作与生活的算法 以竞争取代争斗
1700495230
1700495231
至此，我们已经知道了群体为成员排序造成的两个不利结果。随着群体规模扩大，你至少会遭遇线性对数次对抗，因此所有成员的生活将充斥各种斗争。此外，你还将迫使所有竞争对手了解其他所有成员变化不定的状态，否则他们就会遭遇不必要的战斗。因此，群体成员身心俱疲。
1700495232
1700495233
但是，这种情况完全是可以避免的，因为通过某些办法建立秩序不需要付出任何成本。
1700495234
1700495235
例如，有一项体育赛事仅利用一场比赛的时间，就将几万选手全部排好了次序。（反过来，一场有1万名运动员参加的循环赛，需要安排1000万场对决。）唯一需要注意的是，赛事所需的时间是由最慢的选手决定的。这项体育赛事就是马拉松比赛，它给了我们一个重要提示：竞争与争斗在本质上是不同的。
1700495236
1700495237
想一想拳击运动员和滑雪运动员之间、击剑运动员与赛跑运动员之间有什么不同。奥运拳击手必须冒着脑震荡的危险，参加O（logn）次（通常是4~6次）比赛，才能登上领奖台。如果让更多的运动员参加奥运会拳击比赛，就会危及所有人的健康。但是，无论有多少人参赛，俯式冰橇运动员、单板滑雪U型池专业选手都只需要跟重力进行一定场次的对赌。击剑运动员需要O（logn）次面对对手的利剑，而马拉松选手只需坚持完成一场比赛。如果用一个简单数值就可以表示运动员在赛场上的表现，那么就可以用常数时间算法来表示他们的比赛状态。
1700495238
1700495239
把“序数”（只能表示排名）变成“基数”（直接为某人的水平赋予一个度量）之后，自然不需要两两比较就可以为一群对象排好次序。因此，在建立优势等级时，也无须进行一对一的直接对决。《财富》杂志的世界500强名单，创建了一种企业等级制度，从这个意义上讲，该名单就是一种等级体系。为了在美国找到最有价值的公司，分析师不需要花费大量精力，将微软与通用汽车、通用汽车与雪佛兰、雪佛兰与沃尔玛等公司放到一起进行比较。借助美元这个媒介，这些看似不是同类事物之间的竞赛变成了同类事物的竞争。制定基准（无论这个基准是什么），就可以解决排序规模变大时导致的计算难题。
1700495240
1700495241
举个例子。硅谷有一条关于相互关系的格言：“你需要主动追逐财富，财富不会主动找上门。”因此，商贩需要找工厂业主，工厂业主需要找风险资本家，风险资本家需要找他们的有限合作人。个人有可能对这种等级关系的基础心怀怨恨，但是不会真的对它做出的“裁决”提出异议。因此，个体与个体为各自地位而争斗的情况非常少。总的来说，两个人走到一起，无须商量就知道应该向对方表示何种程度的尊重。每个人都清楚应该如何相处。
1700495242
1700495243
同样地，船舶海上通行权在理论上需要遵循一套极其复杂的惯例，但是在实践中，到底哪条船应该给另一方让路是由“总吨位法则”这条简单易行的原则决定的。很简单，小船为大船让路。一些动物很幸运，也建立了非常明确的优势等级。诺依曼说：“比如说鱼。它们的关系就非常简单，大鱼居于优势地位。”正因为简单，所以鱼类可以和平相处。与鸡和灵长类动物不同，鱼可以在不流血的情况下建立秩序。
[
上一页 ]
[ :1.700495194e+09 ]
[
下一页 ]