卡牌翻转最大化不同数值问题：随机算法期望与优化方案问询

给定n张卡牌，每张卡牌有正面和背面，f_i表示卡牌i的正面数值，b_i表示其背面数值，所有数值均为正整数。初始状态下所有卡牌正面朝上，可选择翻转任意卡牌，目标是最大化顶面的不同数值数量。例如n=3时，f1=1、f2=2、f3=2，b1=3、b2=2、b3=3，翻转卡牌3后顶面数值为1、2、3，不同数值数量达最大值3。

提问者尝试用DP求解，但不确定该问题是否属于P问题，因此考虑采用随机算法：以1/2的概率随机翻转每张卡牌。为验证该随机算法的合理性，提出两个问题：

1. 如何计算该随机算法单次翻转的期望？
2. 是否存在更优的解决方案？

问题1：计算随机算法的期望 #

利用线性期望的性质可以简化计算，无需考虑事件间的相关性：

• 对每个数值x，定义指示变量X_x：当x出现在最终顶面集合中时，X_x=1，否则X_x=0。最终的不同数值数量就是所有X_x的和，即X = sum_{x} X_x。
• 根据线性期望，E[X] = sum_{x} E[X_x]，而E[X_x]等于x出现在顶面的概率。
• 计算x出现在顶面的概率：等于1减去所有卡牌都不展示x的概率。对每张卡牌i：
  • 若f_i≠x且b_i≠x：无论翻不翻转，都不会展示x，贡献因子1；
  • 若f_i=x且b_i=x：无论翻不翻转，都会展示x，贡献因子0（这种卡牌不可能不展示x，因此不展示的概率乘子为0）；
  • 若f_i=x但b_i≠x：不展示x的概率是1/2（仅翻转这张牌时不会展示x）；
  • 若f_i≠x但b_i=x：不展示x的概率是1/2（仅不翻转这张牌时不会展示x）。
• 将所有卡牌对应的不展示x的概率因子相乘，得到所有卡牌都不展示x的概率P(no x)，则E[X_x] = 1 - P(no x)。
• 遍历所有可能的x（即所有f_i和b_i中的数值），计算每个E[X_x]并求和，就是最终的期望。

举个例子：用题目中的n=3卡牌，数值有1、2、3。

• x=1：仅卡牌1能展示1，它不展示1的概率是1/2（翻转卡牌1），所以P(no 1)=1/2，E[X_1]=1-1/2=1/2；
• x=2：卡牌2无论翻不翻都展示2，卡牌1不涉及2，卡牌3不展示2的概率是1/2（翻转卡牌3），所以P(no 2)=0*1*1/2=0，E[X_2]=1-0=1；
• x=3：卡牌1不展示3的概率是1/2（不翻转），卡牌3不展示3的概率是1/2（不翻转），卡牌2不涉及3，所以P(no 3)=1/2 * 1 * 1/2=1/4，E[X_3]=1-1/4=3/4；
• 总期望E[X] = 1/2 +1 +3/4 = 9/4=2.25。

问题2：更优的解决方案 #

这个问题属于P问题，可以用多项式时间算法求解，比随机算法更优：

解法思路：转化为二分图最大匹配 #

1. 构建二分图：
   • 左侧节点：所有不同的正面/背面数值；
   • 右侧节点：每张卡牌；
   • 对卡牌i，建立两条边：一条从f_i到卡牌i，另一条从b_i到卡牌i。
2. 求最大匹配：该二分图的最大匹配数，就是能得到的最大不同数值数量。
   • 原理：每个卡牌最多“对应”一个数值（一张牌只能展示一个数值），每个数值最多被一个卡牌“选中”（只要有一张卡牌展示它，就算计入不同数量）。最大匹配保证能选出最多的数值，每个数值对应至少一张卡牌来展示它，且卡牌不重复使用。

具体实现 #

可以用经典的匈牙利算法求解二分图的最大匹配，时间复杂度为O(√V * E)，其中V是节点数（数值数+卡牌数），E是边数（最多2n条），对于n张卡牌来说是多项式时间。

贪心策略可作为辅助，但二分图匹配的方法能保证得到全局最优解，比随机算法的期望结果更可靠，尤其是当n较大时。

内容的提问来源于stack exchange，提问作者JOSH