随机算法¶

约 1631 个字 54 行代码预计阅读时间 6 分钟

确定性算法是指在给定相同输入的情况下，算法总是产生相同的结果。

随机算法是指在给定相同输入的情况下，算法可能产生不同的结果。

对于一些复杂的计算问题，确定性算法可能需要耗费大量的时间和资源，而随机算法可以在合理的时间内提供一个近似解。例如，蒙特卡罗方法在计算高维积分时表现出色。

在某些情况下，输入数据可能具有不确定性或噪声，随机算法可以更好地处理这些不确定性。例如，随机森林算法在处理有噪声的数据时表现良好。

有些问题的确定性算法设计非常复杂，而随机算法可以提供一种更为简单和直接的解决方案。例如，拉斯维加斯算法在找到正确解之前会不断尝试，设计相对简单。

在分布式计算环境中，随机算法可以有效地分配任务，减少通信开销，提高计算效率。例如，哈希算法在分布式系统中的负载均衡中起到了重要作用。

随机算法分为以下两种

随机算法

拉斯维加斯算法(Las Vegas Algorithm): 这种算法在每次运行时都会使用随机性，但它保证最终会找到一个正确的解。也就是说，拉斯维加斯算法的输出总是正确的，但运行时间可能会有所不同。一个典型的例子是快速排序算法的随机化版本，它通过随机选择枢轴来提高平均性能。 (randomized algorithms that are always correct, and run efficiently in expectation)
蒙特卡罗算法(Monte Carlo Algorithm): 这种算法在每次运行时都会使用随机性，但它不一定能找到一个正确的解。也就是说，蒙特卡罗算法的输出可能不正确，但运行时间通常是固定的。一个典型的例子是蒙特卡罗方法在计算高维积分时表现出色。(efficient randomized algorithms that only need to yield the correct answer with high probability)

雇佣问题(The Hiring Problem)¶

从猎头公司雇佣一名办公室助理
每天面试不同的申请者，持续 \(N\) 天
面试成本 \(C_i\) 远小于雇佣成本 \(C_h\)
分析面试和雇佣成本而不是运行时间

假设雇佣了 \(M\) 个人。总成本：\(O(NC_i + MC_h)\)

Naive solution:

int Hiring ( EventType C[ ], int N )
{   /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;
    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }
    return Best;
}

最坏情况是面试者始终比前一个面试者优秀，那么需要面试 \(N\) 次，雇佣 \(N\) 次，总成本为 \(O(NC_h)\)。

假设\(N\)个面试者以随机顺序被试，前\(i\)个候选人中的任何一个都同样有可能是迄今为止最合格的。

即第\(i\)个人被选中的概率相当于\(i\)个球的盒子中随机抽取一个球，抽到最好球的概率，为\(\frac{1}{i}\)。

定义随机变量\(X_i\)

定义随机变量 \(X_i\) 如下：

\[ X_i = \begin{cases} 1, & \text{如果第 } i \text{ 个候选人被雇佣} \\ 0, & \text{如果第 } i \text{ 个候选人未被雇佣} \end{cases} \]

候选人 \(i\) 被雇佣的概率为 \(\frac{1}{i}\)。

总的雇佣次数 \(X\) 为：

\[ X = \sum_{i=1}^{N} X_i \]

期望值为：

\[ E[X_i] = \Pr[\text{候选人 } i \text{ 被雇佣}] \]

因此，期望总雇佣次数为：

\[ E[X] = E\left[\sum_{i=1}^{N} X_i\right] = \sum_{i=1}^{N} E[X_i] = \sum_{i=1}^{N} \frac{1}{i} = \ln N + O(1) \]

总成本为 \(O(C_h \ln N + NC_i)\)。

int RandomizedHiring ( EventType C[ ], int N )
{   /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;

    randomly permute the list of candidates;//takes time

    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }
}

算法的关键在于生成随机排列。

Assign each element A[ i ] a random priority P[ i ],and sort

void PermuteBySorting ( ElemType A[ ], int N )
{
    for ( i=1; i<=N; i++ )
        A[i].P = 1 + rand()%(N^3); 
        /* makes it more likely that all priorities are unique */
    Sort A, using P as the sort keys;
}

如果只Hire一个：

int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = -  ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;
}

先随机挑选k个面试，取出其中最好的，然后从第k+1个开始，如果比最好的还好的话，就雇佣。

\( S_i \): 第 \( i \) 个申请者是最好的

要使 \( S_i \) 成立，需要满足：

\( A \): 最好的申请者在位置 \( i \);概率为 \(\frac{1}{N}\)
\( B \): 在位置 \( k+1 \) 到 \( i-1 \) 没有人被雇佣，也就是说，1到 \( i-1 \) 中没有比挑出的 \( k \) 个更好的(前 \( i-1 \) 个中最好的在\(k\)个中)，概率为 \(\frac{k}{(i-1)}\)

概率计算：

\[ \Pr[S_i] = \Pr[A \cap B] = \Pr[A] \cdot \Pr[B] = \frac{1}{N} \cdot \frac{k}{(i-1)} = \frac{k}{N(i-1)} \]

\[ \Pr[S]= \sum_{i=k+1}^{N} \Pr[S_i] =\frac{k}{N} \sum_{i=k}^{N-1} \frac{1}{i} \]

其被以下这个积分式子bound住

\[ \int_{k}^{N} \frac{1}{x} \, dx \leqslant \sum_{i=k}^{N-1} \frac{1}{i} \leqslant \int_{k-1}^{N-1} \frac{1}{x} \, dx \]

对于给定的 \( k \)，雇佣到最优候选人的概率满足：

\[ \frac{k}{N} \ln\left(\frac{N}{k}\right) \leqslant \Pr[S] \leqslant \frac{k}{N} \ln\left(\frac{N-1}{k-1}\right) \]

为了最大化这个概率，我们需要找到最佳的 \( k \) 值：

通过求导并设导数为零，我们得到：

\[ \frac{d}{dk} \left[ \frac{k}{N} \ln\left(\frac{N}{k}\right) \right] = \frac{1}{N} \left( \ln N - \ln k - 1 \right) = 0 \]

这意味着：

\[ \ln k = \ln N - 1 \quad \Rightarrow \quad k = \frac{N}{e} \]

带入

\[ f(k) = \frac{k}{N} \ln\left(\frac{N}{k}\right) \Rightarrow max(f(k)) = \frac{1}{e} \]

随机化快速排序¶

对于传统的快速排序，最坏情况是每次选择的pivot都是最小或最大值，导致每次划分都只能减少一个元素，导致时间复杂度为\(O(N^2)\)。

其平均时间复杂度为\(O(N\log N)\)。

如果我们随机选择pivot，并希望这个pivot满足：

中心分割:= 选择一个枢轴，使得每一侧至少包含 \(\frac{n}{4}\) 个元素

改进快速排序:= 在递归之前总是选择一个中心分割

期望意义下两次选中

The expected number of iterations needed until we find a central splitter is at most 2.

每一次，选中的概率是\(\frac{1}{2}\)，需要选一个中心分割，所以n次伯努利试验期望意义下需要选两次，n=2。或者，以几何分布的眼光来看，成功的概率是\(\frac{1}{2}\)，所以期望意义下需要选两次。

定义：

Type \( j \): the subproblem \( S \) is of type \( j \) if \( N \left( \frac{3}{4} \right)^{j+1} \leq |S| \leq N \left( \frac{3}{4} \right)^j \)

推出: There are at most \( \left( \frac{4}{3} \right)^{j+1} \) subproblems of type \( j \).

因为下界要小于\(N\)

一个typej的期望成本为

\[ E[T_{\text{type } j}] = O\left(N \left( \frac{3}{4} \right)^j \right) \times \left( \frac{4}{3} \right)^{j+1} = O(N) \]

不同的type的个数为

Number of different types = \( \log_{4/3} N = O(\log N) \)

This results in a total complexity of \( O(N \log N) \).