随机牌组执行两次交换得到最小总方差的求解方法问询
两次swap实现扑克牌组最小总方差求解方案
问题背景
现有一副顺序随机的完整扑克牌,目标是仅执行两次卡牌swap操作,找到最优的4张牌交换位置,使牌组的总方差最小。
牌组总方差定义:牌组内所有相邻卡牌的距离之和,距离指卡牌牌面等级的差值,例如黑桃A(等级为1)和梅花9的距离为9-1=8,总方差为第1与第2张、第2与第3张……直到最后两张卡牌的距离累加值。
swap操作定义:交换数组/列表中两张卡牌的位置。
该需求为作业第二部分内容,第一部分要求求解单次swap后的最小总方差,已通过双层for循环暴力遍历所有交换位置、对比交换后牌组总方差得到结果,单次swap的参考代码如下:
for i, first_card in enumerate(data): new_deck = data TV= 600 for j, second_card in enumerate(data): old_card = new_deck[i] new_deck[i] = second_card new_deck[j]= old_card new_TV = distance_cal(new_deck) if new_TV <TV: TV = new_TV TV_arr[i] = new_TV first_card = new_deck[i] second_card = new_deck[j] dict_list[i]= {"first_card":first_card,"second_card":second_card} new_deck = data
注:上述参考代码中直接对new_deck赋值为data属于引用传递,修改new_deck会同步修改原data数组,实际运行时建议改为深拷贝避免原数据被篡改。
上述暴力方案不适用于两次swap的场景,可采用以下优化方案实现:
可行求解方案
方案1:增量计算+分步最优搜索(可得到精确全局最优解)
直接暴力遍历所有两次swap的组合复杂度为O(n⁴),结合n=52的牌组规模,再叠加每次O(n)的总方差计算,运算量过高,可通过两步优化降低运算量:
- 优化总方差计算逻辑:交换位置i和j的两张牌时,仅会影响
i-1与i、i与i+1、j-1与j、j与j+1共4对(i、j相邻时为3对)相邻卡牌的距离,其余相邻对的距离完全不变。因此不需要每次交换都重新计算整个牌组的总方差,只需要减去旧的相邻对距离、加上新的相邻对距离即可快速得到新总方差,将单次交换后的总方差计算复杂度从O(n)降到O(1)。 - 分步剪枝搜索:先遍历所有单次swap的结果,保存总方差最小的前200~500个交换后的牌组状态,再对每一个保存的状态,再遍历做一次单次swap找最优结果。该方案的总运算量仅为O(n² + K*n²),K取200的情况下总运算量也不到60万次,完全可以在普通设备上快速跑完,且大概率能覆盖到全局最优解。如果需要完全确定全局最优,也可以直接用增量计算优化后的逻辑跑全量两次swap组合,总运算量约700万次,也能在秒级跑完。
方案2:断点贪心搜索(适合更快得到近似最优解)
先统计当前牌组中所有相邻对的距离,筛选出距离最大的10~20个断点位置,两次swap仅选择断点附近的卡牌作为交换对象,不需要遍历所有52张牌的位置,搜索范围可以缩小一个数量级以上,适合对运算速度要求更高的场景。
内容的提问来源于stack exchange,提问作者Snoopy_loops
相关产品推荐
相关产品推荐

