1700494466
卖房子问题的最优停止阈值
1700494467
1700494468
威斯康星大学麦迪逊分校的优化专家劳拉·阿尔伯特·麦克莱回忆说，她在卖房子时，就用到了最优停止问题的相关知识。她说：“我们收到的第一个报价就非常高，但是他们希望我们比预计的搬离日期早一个月搬走。这个代价太大了。这时候，又有人报出了一个有竞争性的报价……但是我们一直不为所动，直到最后有人报出了令我们满意的报价为止。”对很多卖家而言，建议他们拒绝一两个优厚的报价都会让他们神经紧张，如果随后的报价比不上前者，那么他们就会更加紧张。但是，麦克莱很冷静，坚守立场没有动摇。她承认：“如果我不知道数学计算的结果，就很难坚持下来。”
1700494469
1700494470
在任何情况下，只要你可以得到一系列报价，而寻找或等待下一个报价需要付出一定成本时，就可以应用上述准则。因此，除了卖房子，在很多情况下我们都可以考虑这条准则。例如，经济学家利用这个算法构建的找工作模型，可以轻而易举地解释失业工人与空缺岗位并存这个看似矛盾的事实。
1700494471
1700494472
事实上，最优停止问题的这些变种还有一个更令人吃惊的特性。前面说过，在开普勒寻觅爱情的过程中，可以“复活”之前被自己拒绝的机会是一个非常重要的条件。但是，在卖房子或者找工作时，即使我们可以重新考虑之前的报价或工作邀请，即使我们可以肯定那个报价或工作邀请仍然有效，我们也绝不应该重新考虑它。如果之前它没有达到阈值的要求，那么现在它也不会高于阈值。在拒绝那个报价或工作邀请之后，我们的付出已经成为已支付成本。因此，不要妥协，不要试图亡羊补牢。坚持住，不要回头！
1700494473
1700494474
1700494475
1700494476
1700494477
算法之美：指导工作与生活的算法 [:1700494108]
1700494478
算法之美：指导工作与生活的算法 最优停车位置
1700494479
1700494480
克拉克·克尔，加州大学伯克利分校校长（1958—1967年）
1700494481
1700494482
我发现，大学校园里有三个主要的行政管理问题：学生关心性爱，校友关心体育，教职员工关心停车问题。
1700494483
1700494484
最优停止问题经常出现的另一个领域与汽车驾驶有关（在这个领域，回头同样是不明智的）。在某些早期文献中，秘书问题的主角是驾车者，而汽车只进不退的基本设定把驾车旅行中的所有决策过程（包括寻找饭店、寻找浴室，以及最令城市驾车者头疼的寻找停车位等过程）全部变成了停止问题。要讨论进出停车场的问题，加州大学洛杉矶分校著名的城市规划教授、被《洛杉矶时报》称作“停车场摇滚明星”的唐纳德·舒普显然是最合适的人选。我们从加州北部出发，驾车前往学校拜访舒普。我们告诉舒普，我们为这段行程预留了大量时间，让他不要担心我们会因为意外的交通情况而无法按时抵达。舒普回答说：“说到针对‘意外的交通情况’制订计划，我认为你们应该考虑的是预计的交通情况。”舒普的知名度或许大多归功于他的著作《免费停车的高昂代价》，此外他还做了大量工作，推动人们讨论、了解驾车旅行的真实情况。
1700494485
1700494486
我们真应该同情那位可怜的驾驶员。根据舒普的模型，理想的停车位应该在停车位“标价”、行走所需时间及造成的麻烦、寻找停车位所需时间（随着目的地、一天中的时间不同而发生显著变化）以及整个过程所消耗的汽油等方面实现优化并达成精确平衡。因为车内乘客人数不同，上述等式会发生变化，因为乘客可以分担停车费用，但是无法分担搜寻时间，也无法分担步行的时间与麻烦。与此同时，驾驶者还需要考虑到的一个问题是：停车位最多的地方可能也是停车需求最大的地方。停车问题含有博弈论的成分，因为在你算计道路上其他驾车者的时候，他们也在算计你。[1]话虽如此，停车难题大多归根于一个数字，即停车位占用率——目前被占用的所有停车位占总停车位的比例。如果占用率很低，找到一个好的停车位并非难事；如果占用率很高，想为你的车找到一席之地就不是那么容易了。
1700494487
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