【老万】想买便宜世界杯球赛票？还是想找个好对象？一招搞定both
老万约 8 分钟（微信公众号改版后，有朋友反映说收不到推送。敬请把《老万故事会》公众号设成星标，确保能看到最新文章。）
同事 F 君自波士顿来，约好一起午饭。
席间，说到如火如荼的世界杯。我说今年票好贵。F 君说可不是，他刚买票花了 $800 多。
我不看球，但对钱感兴趣，便问他这算是买贵了还是占便宜了。
F 君说他在官方售票网站上盯了两个星期，价格起落很大，最后小心脏受不就下单了，也不知是否买贵了。
我一听，计算机科学家上身，立马问他知不知道这个买票问题有最优算法，可以保证长期来说平均价最低。理查德·费曼跟朋友吃饭时发现了这个算法，写在餐巾纸上。别的数学家也独立证明了它的最优性。
算法是这样的：
先预设一个自己能承受的等待期限，也就是说等待期结束前必须买票。然后数数从现在到截止有多少天，把这个时间长度除以 e（就是那个自然对数的底 2.71828…）。假设答案是 K 天。在前 K 天，你要做的是捂紧钱包，紧盯市场，记下这前 K 天的最低价（假设为 C）。记住，在观望期千万不能出手。
观望期一完，进入执行期。在这个期间，一旦看到价格低于你曾经见过的最低价 C，不要犹豫，马上下单。
要是不幸到等待期结束也没有看到更低价，只能愿赌服输，按当时的市场价买下这张票。
数学家证明，用这种策略长期平均来看拿到的票价是最低的。（此处省去 15000 字论文。）
～～～～
同事点头：你说的是“秘书问题”。
我暗吃一惊：F 君的数学储备还真是丰富！
这个问题确实有一种另外表述，就是面试秘书：N 个申请者，你只能一个一个地看，永远不知道后面的人水平会更高还是更低。每面试完一个人你要当场做决定是否录用。要是 no，就开始面试下一个人；要是 yes，后面的申请者就全都不要看了。你没有机会回头，一旦对一个人说了“no”，就不能再回去说“yes”。
聪明的你已经看出来了，这个问题实际上是跟买票是一模一样的，完全可以用同样的算法解决：先面试前 N/e 位（要是你懒得仔细算，就取三分之一的近似值好了）申请人，记录最佳的状态。然后一旦见到更优秀的马上录用。
其实，这个算法还有一个适用场景更广的应用，那就是相亲。如果你有 N 次相亲机会，用它可以最大化你对老婆/老公的满意度。
～～～～
说到数学，同事开始滔滔不绝，说你知不知道还有一个相关的“住院医师配对问题”？
每年美国医学院毕业生都要申请当住院医师，各个医院也要在申请人中择优录用。每个医学院毕业生会给自己理想的医院排一个名，每个医院也给这些学生做一个排名。如何选择才最优呢？
美国医学学会的算法可以保证结果是稳定的：不会出现某个学生比起自己现在配对的医院更想去某家医院，而那个医院正好比起自己配对的学生更想要这个学生。
这个场景离我们大多数人生活太远。但一个场景大家都可以感同身受：让我们又回到相亲。
假定有 N 个男生和 N 个女生，数学家证明了必定存在一个全局稳定解。虽然它不保能证每个人都能找到自己最满意的对象（因为可能有情敌，即两个人最满意的都是同一个人），但可以保证大家都可以凑合，无人私奔。
也就是说，在这样的一个稳定解里，不存在这样一对男女（不妨叫他们阿强和阿珍）：
比起现在的老婆，阿强其实更喜欢阿珍；
同时，比起现在的老公，阿珍也更喜欢阿强。
要是这样的组合存在，阿强阿珍就会私奔，就会不稳定。
寻找这个稳定解有个经典算法，在数学和经济学中被称为盖尔-沙普利算法（Gale-Shapley），也叫稳定婚姻算法（Stable Marriage Algorithm）。
这个算法由数学家戴维·盖尔（David Gale）和劳埃德·沙普利（Lloyd Shapley，2012 年诺贝尔经济学奖得主）在 1962 年提出。它的伟大之处在于：它证明了无论男女双方偏好排序如何，永远存在至少一种稳定的匹配方案。
不光有证明，还有完整的操作方法：男生追求，女生筛选。
或者，时代不同了，反过来女生追求，男生筛选也可以。
具体说，假设有相同数量（N 个）的单身男生和女生，每人手里都有一张自己对异性的满意度排名表（从最喜欢到最不喜欢）。算法采用回合制。
第一步：男生求婚。每个还没找到未婚妻的男生，走向还没拒绝过他的女生中自己最喜欢的那位，求婚。
第二步：女生考虑。每个女生收到求婚后，会查看自己的排名表：要是她目前单身，就暂时接受这个男生的求婚（进入订婚状态）。如果她已经有了未婚夫，就拿新求婚者和现任进行对比：要是新人更好，就无情地甩掉现任，接受新人。反之就拒绝新人。
第三步：重复迭代。在这一轮被拒绝或被甩掉的男生，按以上算法继续求婚。过程不断重复，直到所有人都成功配对，然后大家领证。
这个算法看似简单，却蕴含着几个奇妙的数学特性：
第一：必定会结束且人人有份（阿 Q 都说好）。由于男生的名单有限，且女生一旦订婚就不会再回到单身状态（只会换更好的），算法在有限步骤内一定会终止，达到完全匹配。
第二：绝对稳定。最终的匹配结果一定不存在任何可以私奔的组合。（不是说没有人想出轨，而是每个人想出轨的对象都看不上那个人。）
我问这个算法的时间复杂度是什么？同事说只有 N²，在理论和实践中都相当可行。
最坏情况： 每次有男生被拒绝，他都要向自己名单上的下一个女生求婚。在极端情况下，所有男生都把自己的志愿表从头到尾表白了一遍。因为每个人有 N 个志愿， N 个男生总共最多可以发起 N * N 次求婚。
日剧《第 101 次求婚》
～～～～
我正在为数学家大庇天下有情人终成眷属而欢颜，F 君又指出，现实情况要比理想复杂。
在原版算法中，有两个非常理想化的假设：
第一，每个人的心仪名单里必须对所有人排出高低，不允许有并列（不能既要曼玉又要青霞）。
第二，只要是异性来求婚，单身的你就不能拒绝。
在现实中这很不人性化。如果允许人们对某些人打一样的分，并且允许把某些不感冒的人从名单中划掉，宁可单身也不将就（吴妈宁可寡居也不要阿Q），这就变成了 SMTI（Stable Marriage with Ties and Incomplete lists）问题。
在 SMTI 中，由于有并列和空缺，不能保证人人有份，同时可能会存在多种不同大小的稳定匹配（比如方案 A 撮合了 10 对，方案 B 只能撮合 8 对）。
SMTI 有不同大小的稳定匹配这件事让人头疼 - 作为一个婚恋平台，我们显然想让尽可能多的有情人配种对成功。找到一个稳定解容易，找到一个最大的稳定解就困难了。
事实上，这件事难于登天。在计算机科学里，它的难度属于 NP-hard。
学过《可计算性和计算复杂性》这门课的同学会立马认识到，这件事在现有的技术条件下就算是判了死刑了。
～～～～
什么是 NP-hard？我来介绍一下。
按照用计算机解决的难度，我们可以把问题分为几类：
第一类：P 问题（对计算机来说，算个 P 事）。这类问题不仅有解，而且计算机能在多项式时间内直接把答案算出来。比如：查字典、排序、或者前面的原版稳定婚姻算法。
第二类：NP 问题（难算易验）。这类问题很难直接算（目前还没找到多项式时间的算法），但是容易验证。如果别人给你一个号称是正确的答案，你能在多项式时间内判断它对不对。比如： 数独。让你解开一个高难度数独很难，但如果别人填好了拿给你，你一行一行检查有没有重复数字非常快。
计算机领域的圣杯问题就是 P 到底等不等于 NP，也就是说那些很难算的 NP 问题有没有可能实际上有多项式时间的算法只是我们还没有发现？计算机科学家被这个问题困扰半个多世纪了还是一筹莫展。要是你能解决，不管答案是 yes 还是 no，你都可以马上成为巨擎、伟人、传奇（任选）。
大多数人倾向于认为 P 不等于 NP，也就是说 NP 不是虚难，确实更难。但是一直没有实锤。
什么是 NP-hard 呢？它是一个终极无底洞，通俗地说，就是至少和 NP 问题中最难的那些问题一样难，甚至可能更难。
它就像是计算机界的万恶之源。如果一个问题被证明是 NP-hard，就意味着目前人类和计算机根本没有办法在合理的时间内完美地解决它。当数据量变大时，计算所需的时间会指数级爆炸（比如要算到宇宙毁灭）。
NP-hard 问题有一个神奇的特性：只要你能发明一种天才算法在很快的时间内解出某一个 NP-hard 问题，世界上所有的 NP 问题（比如各种密码学难题、数独、最优排班等）都能被瞬间迎刃而解。
注意：NP-hard 问题本身不一定是 NP 问题。也就是说，有些 NP-hard 问题不仅极难计算，甚至连验证别人给的答案对不对都做不到。
～～～～
不知不觉，公司的免费午餐吃完了。我们端起托盘走向出口。我说：
F，听君一席话，我学到了 - 婚姻是 NP-hard 的。
～～～～～～～～～～
关注老万故事会公众号：
码字不易，呕心沥血只是希望更多人看到。如果喜欢这篇文章，请不吝三连。谢谢！🙏
～～～～～～～～～～
老万近期文章：