一位旅行家、两名将军、四份礼物和五个哲学家（烧脑）
本文经「原理」（微信公众号：principia1687）授权转载，禁止二次转载
科学并非枯燥的一成不变。很多科学中的理论都能用这些有趣的问题进行描述而引发讨论和思考。甚至有很多科学的理论都来自于看似天马行空的思想实验。今天我要跟大家分享的是计算机领域中的四个有趣问题，它们各自代表了不同领域的研究。希望读者能跟着这些问题一同探索、思考、发问。
我们的故事要从一位旅行家开始......
1. 旅行推销员问题
这位旅行家叫做奇奇，他的每一次出行都肩负着特殊的使命：推销产品。他的日记本里记录着一系列的目标城市和城市之间的距离。但他遇到了一个难题，为了提高推销的效率，他需要知道从起点出发，访问每一座城市一次并回到起始城市的最短路径。这个问题听起来很简单，但是想要得到一个优化的解法却相当困难。
奇奇能想到的最简单的方法是对所有可能性都尝试一遍，但他发现这是最难执行的解法，因为问题的复杂度是呈指数级增长的。当城市节点多了之后无疑使这种解法需要很长的时间。经历了一番智力搏斗后，奇奇决定求助于高级程序员小村师兄。
但是，这可真不是敲几个代码就能有效解决的问题啊！小村紧锁眉头说道：“我们并不一定要找到最短路径，为了节约时间，我们可以设定一个我们能够接受的路径长度，在遍历每个可能性的时候如果遇到路径恰好小于或等于我们能接受的路径长度时就停止遍历。”
小村师兄的思路在复杂度理论中被定为NPC问题（详见：《一个价值百万美金的问题》），这个问题在现在还没有找出一个可以在多项式级时间内解决的算法。
这类问题不仅在计算机的芯片制造中非常常见（该问题和半导体制造业中对打孔数量及顺序的求解异曲同工），在其他方面诸如物流，企划，DNA测序也都非常常见。甚至在天体观察中减少望远镜在星体中转向的次数也与该问题相关。只是现在还没有人能找出算法，在多项式级时间里有效解决该问题。
读者们如果有好的想法，欢迎在留言区中讨论，为这位旅行家指点迷津，也为自己拿下一百万美金。
2. 两个将军的问题
这个故事的主角依旧是奇奇和小村，不过他们不再是旅行家和程序员，而是两名威风凌凌的将军，他们都效忠于C军队。
C军队筹谋已久，准备出兵从东西两面夹攻宿敌O军队。东面军队由奇奇将军带领，而西面军队则由小村将军统领。现在，两位将军想要统一进攻的时间，需要相互通信，并由信使携带信息在东西两个军团来回传信。但问题是东西两个军团中间隔着O军队，信使有可能会在送信的途中被逮捕后枪毙。也就是说，奇奇将军的进攻信息有一定的概率是无法传到西面友军那里去。
现在问题来了，如果你是奇奇将军，并确定了次日早上8点两军团共同夹攻O军队，你要如何判定对面的友军能够跟你一起准时出兵协同作战呢？当然，或许你会想，如果你收到了小村将军的回复即确定攻击，如没收到回复则再派信使前往。这样真的就可以了吗？
现在试着站在小村将军的角度上想，即便是奇奇将军真的收到了他的回复，但他自己是无法确定奇奇将军是否真的收到了自己的回复，因为信使可能在途中被抓。如果小村将军不能确定奇奇将军是否收到自己的回信，他就会担心对方无法在约定好的时间里出兵。这就导致了小村将军自己可能也不在规定的时间内出兵。
如果此时奇奇将军收到了回信发动进攻，那么就会是孤军奋战。所以作为奇奇将军的你，如果站在小村将军的角度上考虑一下，就算你收到了小村将军的回复，你就能百分百确定对方会一同出兵进攻吗？同理，如果双方都站在对方的角度上多考虑一步，那么他们就需要无限次的得到对方回复，也就是说，这个仗根本就打不起来。
你心中已经有答案了么？
这个看似没完没了的顾虑，其实是计算机网络通讯问题的一个缩影。网络通讯过程中也是不稳定的，也就是说很多发出的信息也不一定会得到接收方的回复。
要想解决这个问题，网络通讯的设计者们只能通过容错这个概念最大程度的减小（但无法消除）通讯中的错误的发生。其中比较简单的办法可以是奇奇将军提出进攻时间，并派100个信使将这个信息带给小村将军。奇奇将军无论是否收到回复都会在约定时间内出兵进攻，而小村将军只要收到一个信使传来的信息，无论是否有收到奇奇将军的回复，都将在约定时间内出兵进攻。
同时，奇奇将军可以给每封信进行编号，小村将军作为接收方就可以通过编号来确定中间的O军队戒备是否森严。如果能收到很多连续编号的信，那么说明信使是可以相对安全的穿过O军队，那么小村将军就会更加有信心自己的回复可以安全到达奇奇将军的阵营，从而更有信心在约定时间内出兵进攻。这也是现在网络通信常用的信息交换的方式。当然也会有更好的通讯办法，欢迎读者在留言区里加以讨论。
3. 四份礼物的问题
奇奇从梦中醒来，发现已是早上九点，他不得不从刚才的将军梦中回到现实。他得以最快的速度洗漱赶往火车站，今天为了推销产品他特定筹划了一场活动。
抵达活动现场后，他告诉围观的人群：
“我在桌上放有四份礼物 A、B、C 和 D。A 和 B 是普通奖，C 和 D 是大奖。得奖的方式很简单。如果你做一个正确的声明（比如1 + 1 = 2）我就给你 A 或者 B 作为奖励。如果你做一个错误的声明（比如1 + 1 = 3）我就给你 C 或者 D 作为奖励。”
人群中有一个叫卡吹的女大学生，她恰好看到了奇奇在后台准备的四份礼物都是什么，她最想要得到礼物C，这是一支Dior秋季的刚出的玫红色口红。卡吹不假思索的掏出了手机，打给她的邻居若雨，并问道：“我到底要说什么才能确定自己能拿到这支口红呢？”
“其实答案很简单，如果你想赢得 C 的奖励，你只需要说‘我能得到礼物 D’。如果这句话是错误的，那么你能得到礼物 C 或 D，而正因为‘我能得到礼物D’这句话是错误的，那么奇奇就只能给你礼物 C。反之，如果‘我能得到礼物D’是正确的，按规则你只能得到礼物 A 或 B，但这又和‘我能得到礼物D’这句话相矛盾。所以在你说‘我能得到礼物D’这句话时，奇奇别无选择，只能给你想要的礼物C。”
卡吹显然有点被绕晕了，但准备按照若雨说的做。好胜心强烈的若雨继续说道：“其实，你只要说一句话，还能够打破奇奇刚刚自己定下的规则。你知道是什么吗？”
“........"
"答案也很简单，你只需要说‘我能得到大奖’或‘我能得到礼物 C 或 D’就可以了。如果这句话是真，按规定奇奇只能给你礼物 A 或 B，这便自相矛盾了。如果这句话是假，按规定我还必须按你所说给你礼物 C 或 D，这又会自相矛盾。所以当你说‘我能得到礼物 C 或 D’ 时，奇奇就会被自己的规则逼到死路。”
“感觉奇奇很可怜，幸好你不在现场。我只想要口红而已。”
这个问题和另一个有名的绞刑问题相似。说在一个城市的监狱里有这样一个规矩。上庭时如果被告做一个错误的声明，那么被告将会被绞死。反之如果上庭时被告做一个正确的声明，他将被判处无期徒刑。假如你是被告，你会说什么让法官根本无法执行他定下的法规呢？（这个问题就留给读者自己了，欢迎大家在留言区讨论。）
无论是四份礼物的问题，还是绞刑问题，解决的关键都在于巧妙的运用自洽这个概念。通俗讲，就是把规则制定者本身也套进规则里面。这个概念被图灵巧妙地用到了计算机理论里，并以此证明了著名的停机理论（详见：《一个无法证明的逻辑问题》），奠定了计算机理论的基础。
4. 哲学家就餐问题
如果有五个哲学家坐在圆桌旁就餐，那么可以想象到画面定是他们之间的唇枪舌战。但是，今天的圆桌上多了一个规定，坐下就餐的人只能做两件事情：吃饭或者思考，无法相互交流。两者必须交替进行。
每两个哲学家中间有一个叉子，而他们每个人必须用两个叉子吃饭，也就是说必须在左右两边的叉子都空闲，并且拿起来的时候才能开始吃饭。吃饭的哲学家必须在吃一段时间之后停下来思考，而没拿到叉子吃饭的哲学家则在思考的同时等待别人用完叉子。假设食物是无限量供应的，请问怎么做才能不让他们中任何一个人饿死？
没错，即便是无限供应食物，哲学家都会有饿死的可能。因为圆桌上总共只有五个叉子，不是所有哲学家在同一时间都能吃到东西。如果没有一个完整的解决方案，五个哲学家可能会遇到“死锁”或者“活锁”的现象。
试想，他们每人最开始的时候在思考。如果他们都计划当左边有叉子的时候拿起左边的叉子，之后如果右边有叉子再拿起右边的叉子开始吃饭，那么他们就没有一个能吃上饭。因为他们都在共同等待右边的叉子。也就是说 A 所等待的叉子会被他们右边的 B 拿着（如下图）。
由于是一张圆桌，那么就会产生以下的结果：
A在拿到左边的叉子时，必须等到右边的叉子才能吃饭，而且只有吃完饭才会放下两个叉子。
A如果要等到右边的叉子则必须将左手的叉子放下，等其他人吃完放下叉子之后才有机会吃上饭。
这就导致了每个人都在一个死锁里面，因为无法获得右边的叉子而饿死。当然死锁是有可能消除的，比如每位哲学家都会在等待另一只叉子超过五分钟之后放下自己左手的那只，并在等待5分钟进行下一次的尝试。然而这种情况可能会导致“活锁”现象，想象如果哲学家是同时入座，同时拿起左边的叉子并等待相同时间之后放下左手的叉子，那么依然没有任何一位可以同时获得两个叉子。
那么有什么方法可以解决这个问题呢？这里介绍两个比较简单的方法。
首先，最简单的就是引进第三方的解法。我们可以在餐桌旁引进一个服务生，哲学家必须得到他的同意才能够拿起叉子吃饭。而这个服务生的作用就是记住谁在什么时候吃东西，谁在等待，等待的人在什么时候拿叉子才能避免死锁现象。比如，整个圆桌按顺序排列着 A - E 五个人，如果 A 和 C 在吃东西，那么 D 和 E 之间会有一只空余的叉子。而此时如果 D 拿起叉子准备等待吃饭，就可能会发生死锁现象。而此时如果有服务生的存在，服务生会让他等待，从而保证每次有两把叉子空出来时，一定有一位哲学家能获得一对叉子，从而避免死锁。
第二个解法是资源分级法（如下图）。我们可以把桌上的资源（五把叉子）从一到五分级，并要求哲学家总是先拿起左右两边编号较低的叉子，再拿较高的，用完餐后总是先放下编号较高的叉子，再放下较低的。所以，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上。
这个过程必然导致两个哲学家争抢一个低编号的叉子，而没抢到的那一位则无法用餐，因为他另外一边的叉子会被在同一边的哲学家拿走。而此时只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。当然这个问题还可以有更多更好的解法，也欢迎读者们在留言区里讨论。
这个问题是用来演示并行计算中多线程同步中所产生的问题。多线程在并行计算中很多情况下一个线程会需要另一个线程的运行结果。（或者简单来讲，多核运算中很多情况下一个核的运算会需要另一个核的运算结果），这种情况下就会容易出现上述的死锁现象。需要在程序运行时加入更多的检查来消除这种现象。上述的引进第三方解法就是计算机中常用的用一个单独的线程（或单独的核）来充当服务生的角色，从总体上分配资源。而上述的资源分级法也被用在计算机中，通过分级资源指定的常量来强制获得资源。
上述的四个问题描述了计算机不同领域的研究。虽然只是冰山一角，希望读者能通过对这些问题的思考甚至提出更多的问题，对计算机各领域的理论有不一样的理解。
致谢：感谢奇奇、小村、卡吹、若雨的友情出场。
七夕 · 爱情匹配度测评
—— 3 分钟帮你揭开自己的爱情真相 ——
▼
长按二维码
开始你的甜蜜之旅