一些可能有点用的算法

Published: December 17, 2022 by Daltao

• Categories:
• algorithm 101

• Tags:

• 随机数组合选取问题
• 红包算法
• 桌游rating算法
• 数值信息压缩问题

写这篇博客是为了介绍一些有趣的与现实生活息息相关的算法问题，以及解决方案。其中大部分都是我自己亲身经历过，并且自己独立求解的。这里写出分享给大家。

随机数组合选取问题

考虑这样一个问题，要求你设计一个函数random_set(N, K)，其中$N\geq K$。要求你从$0,\ldots,N-1$的所有$2^N$种可能的组合中，只考虑其中包含$K$个元素的组合（总共有$N\choose K$种），并以等概率返回其中任意一个。

这个问题挑战点在于，我们希望最小化理论上的时间复杂度，由于至少要返回一个大小为$K$的集合，因此时间复杂度的下界是$O(K)$。

算法1：利用洗牌算法，把$0$到$N-1$共$N$个数先打乱并挑选前$K$个数，这样可以直接保证得到的结果是等概率的。算法的时间复杂度显然是$O(N)$的。

接下来考虑另外一个很简单的算法。

算法2：我们维护一个空集合。之后每次随机枚举一个值，如果值不在集合中，就加入，否则丢弃。重复这个过程直到集合大小达到$K$。

这个算法找到第$i$数的期望步数是$\frac{N}{N+1-i}$，如果我们用哈希表来维护这个集合，则时间复杂度为$O(N\sum_{i=1}^K\frac{1}{N+1-i})$，其结果大致为$O(N\ln \frac{N}{N-K})$。

这两个算法看上去都不太行，但是一旦结合在一起，就会产生非常有趣的效果。

• 当$2K\leq N$时，我们采用算法2，这时候找到其中任意数的期望步数都不超过$2$，因此时间复杂度为$O(K)$。
• 当$2K>N$时，我们采用算法1，可以发现时间复杂度为$O(N)=O(K)$。

红包算法

考虑这样一个问题，你要把$N$元红包平均分给$K$个人，最小精度单位为分，设第$i$个人分到了$x_i$分（必须为整数），要求返回$x_1,\ldots,x_N$，且在所有满足$\sum_{i=1}^Kx_i=N$且$0\leq x_1,\ldots,x_N$的可能的组合中，每种组合返回的概率相同。其中$1\leq N\leq 10^8$，$1\leq K\leq 10^4$

由于单位不同，我们可以把$N$先乘上$100$，这样我们就是用的分为单位。

这个问题实际上它的组合解释是：有$N+K-1$个不同的球，从中选择$K-1$个不同的球，每种选法的概率相等。

这实际上就回到了随机数组合选取问题了。因此我们可以直接得到一个$O(K)$时间复杂度的算法。

桌游rating算法

这个问题是我当时在设计一个桌游rating板块的时候遇到的。这里我们需要根据玩家每一轮的胜负，来实时计算他的rating。一个好的rating算法应该满足下面要求

1. 最近比赛对用户rating的影响更大，这样才能鼓励用户参加比赛
2. 很早以前的比赛对用户的rating的影响，因为rating体现的是用户在不断训练后的新的强度
3. 用户最近一场比赛胜利，总rating一定不降；最近一场比赛失败，总rating一定不升。

一个简单的方式是设计一组权重$w_1,\ldots,w_N$，其中$w_i$表示最近第$i$场比赛结果的权重，记$x_i$表示用户第$i$场比赛的胜负，胜利为$1$，失败为$-1$。总分为$\sum_{i=1}^Nw_ix_i$。

为了满足前面的要求，我们希望$w_1\geq w_2\geq \cdots \geq w_N\geq 0$。一个简单的选择就是$w_i=\frac{1}{T+i}$。其中$T$为一个固定常数。

设计是完成了，但是很显然它目前只满足要求1和2，下面我们证明它同时还满足要求3。

非常简单，假如$x_1=1$，设$I$为失败的场次的下标集合，那么新的总分为$\sum_{i=1}^Nw_i-2\sum_{i\in I}w_i$，而原先的总分为$\sum_{i=1}^{N-1}w_i-2\sum_{i\in I}w_{i-1}$。计算新老总分的差值可以得到

$$w_N+2\sum_{i\in I}w_{i-1}-w_i$$

很显然上面式子的结果非负，因此新分一定不低于老分。对于$x_1=-1$的情况证明类似。

数值信息压缩问题

考虑我们现在有一副$H\times W$的灰度图，每一个点的灰度用$Q$位来表示。

现在我们希望压缩这个图像。具体的压缩算法非常简单，我们用调色板的方式，只支持特点的$K$种深度（从$2^Q$中选择），这样每个颜色只需要用$\log K$个bit来表示即可。设原来的灰度为$x$，则我们选择调色板中灰度最接近的那个颜色替代它。

但是提高了压缩效率，我们也不能过度失真。令$A_i$表示灰度图的第$i$个像素的灰度，$B_i$表示匹配的调色板颜色的灰度。共$N=HW$个像素。对于$i\geq 0$，我们定义如下惩罚函数

$$L_i=\|A-B\|^i$$

下面我们考虑如何找到最合适的$K$个颜色，从小到大排列为$c_1,\ldots,c_K$。

我们不难用动态规划来求解。首先我们将所有颜色离散化（很显然只有颜色出现次数会影响损失函数的结果），设不同的颜色数为$C$。令$cost(l,r)$表示将灰度$l$到$r$之间的灰度映射到同一颜色的最少惩罚值。令$dp(i,j)$表示仅考虑前$j$小的颜色，用$i$个不同的颜色去替代，最少的惩罚函数值。很显然我们的结果是$dp(K,C)$，用回溯法可以找到最优解时所有选择的颜色。

$$dp(i,j)=\min_{k<j} dp(i-1,k)+cost(k+1,j)$$

这个公式暴力求解的时间复杂度是$O(KC^2)$。在$C$比较大的时候求解难度很高。

我们可以用决策单调性来优化这一步骤，这样可以将时间复杂度降低到$O(KC\log C)$。

下面我们证明决策单调性的必要条件满足，即对于任意$P$范数惩罚函数，下面公式对于所有$k<j<i$满足

$$cost(k,i+1)-cost(k,i)\geq cost(j,i+1)-cost(j,i)$$

我们记$opt(l,r)$表示让$cost(l,r)$最小化所采用的颜色。很显然有$opt(k,i)\leq opt(k,i+1)$和$opt(j,i)\leq opt(j,i+1)$，同时还有$opt(k,i)\leq opt(j,i)$和$opt(k,i+1)\leq opt(j,i+1)$。

实际上，我们仅考虑公式左边代表的增量的时候，且仅考虑颜色$k$到$i$，第一步从$opt(k,i)$到$opt(k,i+1)$带来的变化，我们记增量为$D_1$，之后再加入颜色$i+1$，带来的新的增量为$D_2$。

同理，我们考虑公式右边代表的增量的时候，且仅考虑颜色$j$到$i$，第一步从$opt(j,i)$到$\max(opt(k,i+1),opt(j,i))$带来的增量变化，记作$D'_1$，同理加入颜色$i+1$后带来的新的增量为$D'_2$。

很显然有$D'_1\leq D_1$且$D'_2\leq D_2$，因此我们有

$$cost(k,i+1)-cost(k,i)\geq cost'(j,i+1)-cost(j,i)\geq cost(j,i+1)-cost(j,i)$$