公平分割问题

来自计算思维百科
跳转至: 导航搜索
公平分割问题1.jpg

大家或许都知道经典的两人分饼问题—为了实现公平性,只能一个人切,另一个人只能选。如果切的人偏心,切得一大一小,选的人就把大的选走,这样只能逼得切的人切得一样大。不过在现实生活中,情况并没有那么理想,如果分蛋糕的人不止两个,分蛋糕的人对蛋糕各部分的价值看法不同,还能实现公平分割吗?

解决方案

方案1---你来分我来选

解决方法:一种简单的办法是每个已经分到蛋糕的人都把自己手中的蛋糕分成更小的等份,让下一个没有分到蛋糕的人来挑选。具体来说就是先让两个人用你来分我来选的办法,把蛋糕分成两块,然后这两个人把自己手中的蛋糕分成三份,让第三个人从这两个人手中各自挑选一份来;然后每个人都把自己手中的蛋糕分成四份,让第四个人选,以此类推,知道最后一个人选定自己的蛋糕为止。只要每个人在切蛋糕的时候做到均分,虽然蛋糕可能被分得零零碎碎,就能保证每个人手中的蛋糕在他自己看来都是不小于蛋糕总价值的1/n;

假设有四个人(甲乙丙丁)分一个蛋糕,那么分蛋糕的过程可以是:

1.最开始的一个蛋糕:

公平分割问题2.png

2.甲和乙先分:

公平分割问题3.png

3.甲把自己的分成三份,乙的也把自己分成三份:

公平分割问题4.png

4.丙从甲的三份里面选一份,丙从乙的三份里面选一份,现在甲乙丙三人各两份;

5.甲乙丙三人再把自己分得的蛋糕分成四份,这样一共有12分蛋糕:

6.丁再从他们三人中各选一份,这样分蛋糕就完成了;

不过分蛋糕只是举个例子,真正分蛋糕的时候当然不需要这么费脑筋,何必呢,最多吃少点就是了。

方案2—最后削减人算法

解决方法:设总人数为N]],第一个人从蛋糕中切出他所认为的1/N,然后把这一块传给第二个人,第二个人可以选择直接把这块蛋糕递给第三个人,也可以选择从中切除一小块(如果在他看来这块蛋糕的价值比1/N大了),然后再交给第三个人;以此类推,每个人拿到蛋糕后都有一次修剪机会,然后移交给下一个人。规定最后一个修剪的人获得这块蛋糕,余下的N-1个人则从头开始重复刚才的流程。在此游戏规则下,每个人都会自觉地从手中的蛋糕修剪成自认为的1/N,否则得到这块蛋糕的人就有可能是他;而如果他把一块大于1/N的蛋糕拱手交给别人,在他眼里看来,剩下的蛋糕 就不够分了,他最终分到的很可能远不及1/N。

所以,分蛋糕结束后,每个人也可以得到在他自己看来都是不小于蛋糕总价值的1/N的蛋糕。

涉及的计算思维

这是典型的资源分配问题,前面我们提到死锁的时候可以按照优先级的方法来进行资源分配,可是对于分蛋糕问题来说,分蛋糕的人的优先级是一样的,所以问题来了。在公平分割问题中,有一个最为根本的公平原则就是均衡分割,它的意思是如果有n个人分蛋糕,则每个人认为自己得到了整个蛋糕至少1/n的价值。它体现的是一种计算思维的优化特点。