1700494488
舒普认为，停车的很多难题都归因于城市政策，因为这些政策导致停车位占用率极高。如果某个地方的停车费用非常低（更糟糕的是，有的甚至免费），就会刺激人们把车停在那里，而不是停到稍远的位置，然后步行。于是，大家都想在那儿停车，但是大多数人发现那里已经停满了车，因此他们只好开着车四处巡游，试图找到一个停车位，结果既浪费时间，又浪费汽油。
1700494489
1700494490
舒普建议的解决办法是安装数字停车计时器，根据停车需求自动调整价格。（旧金山市区已经采用了这种计时器。）在设定价格时，需要先设定一个目标占用率。舒普认为，这个目标值应该在85%左右（对于路边停车率接近100%的大多数大城市而言，这个占用率已经非常低了）。舒普指出，当停车位占用率从90%升至95%时，尽管仅多停了5%的车，但是大家寻找停车位的时间就会翻一番。
1700494491
1700494492
一旦意识到停车其实是一个最优停止问题，你就会发现占用率对停车策略有着关键的影响。行驶在大街上，每次看到一个空车位时，我们都必须做出决定：是停到这个车位上，还是试试运气，再往前开一点儿？
1700494493
1700494494
假设你行驶在一条无限长的道路上，路边车位均匀分布，而你的目标是把车停到尽可能接近目的地的车位上，以便少走几步路。那么你应该采用摸清情况再行动准则。为了实现最优停止这个目标，在距离目的地一定路程之外，即使看到空车位也不要停车；一旦进入一定距离之内，就应该从观望阶段转变为行动阶段，看到空车位后立刻停车。这段距离的长短，取决于停车位可能被占用的百分比，即停车位占用率。下表列出了与某些有代表性的停车位占用率相对应的转变距离。
1700494495
1700494496
表1-2 寻找停车位的最优策略
1700494497
1700494498
1700494499
1700494500
1700494501
如果这条无限长的街道与大城市一样，停车位占用率高达99%，只有1%的停车位是空闲的，那么在距离目的地大约70个停车位（略多于1/4英里[2]）处开始，只要看到空车位，就应该停车。但是，如果舒普的办法奏效，将占用率降低到85%左右，那么在距离目的地半个街区之前，你都无须着急停车。
1700494502
1700494503
我们行驶的道路大多不是笔直的，也不会是无限长的。因此，同其他最优停止问题一样，研究人员也在上述基本情况的基础上做出了各种调整。例如，他们考虑了若干不同情况，包括允许驾驶者调头、距离目的地越近停车位越少、驾驶者与目的地相同的其他驾驶者形成竞争关系等。但是，无论该问题的参数发生哪些变化，增加空闲停车位的数量都可以使我们的生活更加方便。从某种意义上讲，这是提示市政府的政策制定者：停车问题不是单纯靠增加资源（停车位）并最大化利用资源（占用）就可以解决的。停车还是一个进程（是一个最优停止问题），消耗注意力、时间、汽油，还会导致污染和拥堵等后果。合适的政策可以彻底解决这个问题。而且，适宜居住的街区周围有空的停车位，可能是街区运行良好的一个标志，这正好与我们的直觉相反。
1700494504
1700494505
我们问舒普，他在洛杉矶车流中穿行，前往加州大学洛杉矶分校上班的时候，他的研究是否可以为他提供优化方案。作为一名全世界顶尖的停车问题专家，他是否有什么秘密武器。
1700494506
1700494507
舒普还真的拥有一个秘密武器：“我骑车上下班。”
1700494508
1700494509
[1]第11章将详细讨论博弈论计算中的各种风险。
1700494510
1700494511
[2]1英里≈1.61千米。——编者注
1700494512
1700494513
1700494514
1700494515
1700494516
算法之美：指导工作与生活的算法 [:1700494109]
1700494517
算法之美：指导工作与生活的算法 见好就收的时机
1700494518
1700494519
1997年，鲍里斯·别列佐夫斯基因拥有大约30亿美元的财产，被《福布斯》杂志确认为俄罗斯首富。仅仅10年前，他还是苏联科学院的一名数学家，靠工资度日。他利用在研究过程中建立的业界关系，创建了一家公司，帮助外国汽车制造商与苏联汽车制造商AvtoVAZ沟通交流。随后，他的公司变成了AvtoVAZ汽车的大型经销商，同时还通过分期付款的方法，利用卢布的恶性通货膨胀牟利。他还利用与AvtoVAZ的合作关系套取资金，用来购买这家汽车制造商及俄罗斯公共电视台、西伯利亚石油公司的部分股份。最终，他赚得了几十亿美元的身家，成为寡头阶层的新成员。随后，他开始参与政治。1996年，他支持鲍里斯·叶利钦连任；1999年，他又支持弗拉基米尔·普京成为叶利钦的继任者。
1700494520
1700494521
但是，后来别列佐夫斯基的政治态度开始转变。普京当选总统之后不久，别列佐夫斯基公开反对普京提出的旨在扩大总统权限的宪政改革。他在公开场合不断批评普京，导致他与普京的关系开始恶化。2000年10月，在有人请普京就别列佐夫斯基对他的批评发表评论时，普京说：“政府手持大棒，只需一下，就能击碎其脑壳。目前我们还没有动用大棒……一旦我们真的动怒，就将毫不犹豫地砸下去。”当年11月，别列佐夫斯基就离开了俄罗斯，再也没有回来。流亡到英国之后，别列佐夫斯基继续批评普京。
1700494522
1700494523
别列佐夫斯基如何做出离开俄罗斯的决定？是否可以通过数学方法考虑“见好就收”这条建议？多年前，别列佐夫斯基本人就是一名数学家，而且他研究的正好就是最优停止问题，他创作的第一本书（当然也是他的唯一一本书）全部关于秘书问题，因此他当时可能也考虑了这个问题。
1700494524
1700494525
人们在分析见好就收这个问题时，为它披上了好几种伪装，但是最适合别列佐夫斯基这种情况的可能应该是“窃贼问题”（向俄罗斯寡头表示歉意）。在窃贼问题中，窃贼可以实施一系列盗窃活动。他们的每次盗窃都会有收获，并且每次都有机会带着战利品顺利脱身。但是，一旦被抓住，他们就会失去之前的所有收获。窃贼希望收获最大，那么什么样的算法可以给他提供合理建议呢？
1700494526
1700494527
窃贼问题有解，对于盗窃题材的电影剧本而言不是好消息。当盗窃团队诱惑一位已经金盆洗手的老手，希望他复出并干最后一票的时候，这位狡猾的窃贼只需要认真分析那些数字就知道该怎么做了。凭直觉也可以得出结果。实施盗窃的次数应该大致等于顺利脱身的可能性除以被抓的可能性的值。如果你是一名有经验的窃贼，每次盗窃成功的可能性为90%（损失全部身家的可能性为10%），那么在盗窃9次（90÷10=9）之后，你就应该洗手不干了。如果是一名笨手笨脚、成功率只有一半的生手，情况会怎么样？第一次去偷盗时，你本来就身无分文，因此无须担心有任何损失，但是之后就不要再去碰运气了。
1700494528
1700494529
尽管别列佐夫斯基是最优停止问题方面的专家，但是他的结局仍然十分凄惨。2013年3月，一名保镖在他位于伯克郡的住所里发现了他的尸体。他死在锁着的浴室里，脖子上系着绳子。官方在尸检之后宣布他死于自杀。由于他在一系列高调的诉讼案中输给了俄罗斯对手，也失去大笔财富，因此他走上了上吊自尽这条不归路。或许他抽身而退的时间还应该更早一些，在积累几千万美元的财富之后就应该收手，而且不能介入政治。但是，遗憾的是，那不是他的做事风格。他在数学界的一位朋友里奥尼德·博古斯瓦夫斯基，曾经讲过别列佐夫斯基的一件往事。当时，他和别列佐夫斯基都还是年轻的研究员。他们前往莫斯科附近，准备进行湖上滑水活动。但是，他们计划使用的那条船出了故障。戴维·霍夫曼在他的《寡头》一书中有这样一段文字：
1700494530
1700494531
朋友们都跑上沙滩，点起了篝火，只有博古斯瓦夫斯基和别列佐夫斯基向船坞走去，准备修理那台发动机……三个小时之后，他们已经把发动机拆装了一遍，但是发动机仍然无法工作。尽管已经错过了聚会的大多数活动，但是别列佐夫斯基仍然坚持说，他们一定要继续尝试修理发动机。博古斯瓦夫斯基回忆说：“我们想尽办法，试图修好那台发动机。”别列佐夫斯基从来不会轻言放弃。
1700494532
1700494533
令人吃惊的是，在最优停止的文献资料中也曾提到过不放弃（而且是永不放弃）。有的时序决策问题似乎没有最优停止准则，尽管从我们前面讨论的大量问题看，似乎不应该出现这种情况。“要么三倍，要么赔光”的博弈游戏就是一个简单的例子。假设你带着1美元去玩这个游戏。游戏规则对轮次没有限制，但是要求你每次都要押上所有的钱，你有50%的机会赢回三倍的钱，另外50%的机会全部赔光。那么你应该参与多少轮呢？尽管这个问题非常简单，但它没有合适的最优停止准则，因为每参加一轮游戏，你的平均收益都会略有增加。从1美元开始，你有一半机会赢回3美元，一半机会收回0美元，平均而言，第一轮结束之后，你装进口袋的现金期望值是1.5美元。那么，如果你在第一轮游戏中运气不错的话，第二轮游戏的两个可能结果就会将你刚刚赢回来的3美元变成9美元或者0美元，也就是说，第二轮的平均收益是4.5美元。数学计算结果表明，你应该一直玩下去。但是，果真如此的话，你最终必将输光所有的钱。可见，有的问题有解，反而会有损无益。
1700494534
1700494535
1700494536
1700494537