CS106B作业3中的一个疑问

这个题目是第三次关于递归的作业,链接地址为:CS106B Voting Power
题目中指出了这题可以用exclude/include pattern来完成,但同时也说这个方法(递归穷举)的时间复杂度太高了,并给出了一个优化思路(下文绿色部分),这里直接复制过来,如下:

Efficiency . The exhaustive recursion to try all subsets is computationally expensive. Here are a few things to tame its resource-hungry nature:

  • As soon as it is apparent that a coalition is going to win regardless of whether or not the target block participates, there is no need to further explore that path. The target block cannot be a critical vote in this coalition.

但在分析过程中发现不能简单地因为当前选举联盟的票数已经过半数,已经确定赢了的情况下,就可以不管后面的情况。举例如下:

对于图中由ABCD四个人参加的选举活动,其中可能组成的一些选举联盟如图:

当AB组成联盟时,票数为97票,已经严格过了半数,此时已经确定赢了,接下来对于已经赢了的组合确定其中的关键参选人是谁,关键参选人是指如果这个选举联盟中的某个人离开该联盟,该联盟的票数不过半,无法赢下选举,只有这个参选人加入后才可以赢下选举,则说明这个参选人是关键参选人。

按照题目给的优化思路,当票数过半数时,已经确定赢了,就不用管后面的情况了。但是实际上,后面因为其他参选人的加入,会使得某些前面已经确定的关键参选人变成非关键参选人。所以个人认为这个优化思路有一些问题,有没有人已经做了这题,来这里说一下你的思路。

先选出一个人,再将剩下的人进行组合,从中找到失败的组合进行操作,这样处理会更快。
如果不先选一个人,直接将所有人进行组合,从中找到获胜的组合进行操作,会慢很多。
第一种解法的速度会更快,我的电脑上通过压力测试大概要50s左右,而第二种解法会慢很多,同样的压力测试要238s左右才能算完。