从《天行九歌》到海盗问题

本文主要是介绍从《天行九歌》到海盗问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阅读本篇文章大约花费您8分钟！

今天和大家一起思考一道博弈题：海盗问题。

提出海盗问题

在国产动画《天行九歌》中，有这样一个场景：在鬼兵盗窃军饷后，公子韩非深入将军府，与大将军姬无夜展开了一场精彩绝伦的对弈，其中涉及到一个分金币的游戏，游戏规则如下：

图片中提到的游戏实际上是一道博弈题：海盗问题。分金币是一种变种而已，本质是不变的。题目的一种解法已经在图片中显示出来了。关于海盗问题如何体现在《天行九歌》中，大家可以自行去看正片（我本身是国漫迷，所以我在这里推荐大家有空去看一看，再有这一段确实非常精彩，对于理解海盗问题有很大的帮助）。

下面我们就来分析一下海盗问题。

海盗问题的描述

有5个海盗，获得了100枚金币，于是他们商量一个方法来分配金币，分配的方法如下：

由5个海盗轮流提出分配方案
如果超过半数（包括提出者）的海盗同意方案，按照此方案分配
否则，则提出者被扔到海里喂鱼，剩下的海盗继续商量
海盗绝对理性，即以自己尽可能多获得金币为目的，但是在收益相同的情况下，会有倾向的把提出者喂鱼

提问：第一个海盗应该如何提出分配方法，才能保证自己不被喂鱼并且利益最大化？

海盗问题的解决方案

假设有5个海盗A,B,C,D,E

假设A提出方案：A(100),B(0),C(0),D(0),E(0)，这种情况下，B,C,D,E毫无疑问会一致反对，反对人数超过半，A会被喂鱼。然后继续分配。

假设B提出方案：B(1),C(33),D(33),E(33),假设此时C反对，其他都同意，此时同意人数超半数，会按照这个方法分配。

下面我们回到问题本身，第一个海盗A应该如何提出方案？

如果方案是A(0),B(25),C(25),D(25),E(25)，这样A是安全的，但是并没有达到利益最大化。

如果方案是A(20),B(20),C(20),D(20),E(20)，这样A仍然没有达到利益最大化。

……

对于海盗问题，我们可以使用递归的思想进行分析,前一个海盗的分配方案需要参考后一个海盗的最优情况，只需要在后一个海盗的基础上增加一点点金币就可以了。因此A在分配时会考虑如果没有A，B的最优情况。B在分配时会考虑如果没有B，C的最优情况…以此类推，通过递归的思想，我们需要首先分析只有DE两个海盗时D的分配方案：

对于D而言，无论D提出什么样的方案，E都可以不同意，由于只有两人，只要E不同意，D一定会被喂鱼，所以对D来说，没有任何选择。

对于C而言，由于D没有任何选择，所以无论C提出什么方案，D一定会同意（否则D被喂鱼），E一定不同意。此时C(100),D(0),E(0)。

对于B而言，C的最优策略是100个金币，因此C为了获得100金币，一定不会同意B的方案，这是B只需要给DE各1个金币，这比C提出的方案要多一个金币，所以DE一定会同意，此时3人同意，B(98),C(0),D(1),E(1)。

对于A而言，B的最优策略是98个金币，B为了获得98个金币，必然不会同意A的任何方案，此时有5人，最直接的方式是A需要再说服两人同意他的方案。C再B方案下是0个金币，因此A只需要给C1个金币，C一定会同意，原来DE各1各金币，A只需要获得其中一人的支持给他2个金币即可，因此，A的方案有两个：A(97),B(0),C(1),D(2),E(0)或者A(97),B(0),C(1),D(0),E(2)。这就是海盗问题的答案，A提出这两种方案时，不会被喂鱼并且利益最大化。