Lecture 13 | Randomized Algorithms

:material-circle-edit-outline: 约 733 个字 :fontawesome-solid-code: 56 行代码 :material-clock-time-two-outline: 预计阅读时间 3 分钟

最后一次课进行答疑

The Hiring Problem

通过面试从n个人招聘一些人，计算n次面试Ci+工资Ch的成本最小值，且保证能找出最优秀的人

最简单的算法就是遍历

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;
}

这套算法面试成本固定，我们设招X人，计算X的数学期望\(E[X] = \sum_{j=1}^{N}j\cdot Pr[X=j]\)

但是这太无厘头了，不知道怎么算，我们就换种思路

设 \(X_i\) 记录第 \(i\) 个人是否被录取，就可以用此计算X的期望

我们有一个大前提，因为我们没有提前调查，故这n个人在面试前对于我们是一样优秀的

第 \(i\) 个人被录取的条件只需是他在前 \(i\) 个人里面最优秀，所以是 1/i

?????

得到调和级数，渐进上届为 \(lnN\)

但是我们需要做到的是保证这n个人来面试的顺序是随机的

不能让他们串通，毕竟从弱到强来就会几乎全部录取了

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;

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

加入了这一步，这个算法就变成了随机算法

好处是不再要求输入的数据一定是随机的，可以输入有序数据

我们这里讲一种随机的方法，很简单，就是给他们random值，然后从小到大排序，搞定

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

PermuteBySorting produces a uniform random permutation of the input, assuming all priorities are distinct.

Online Hiring Algorithm – hire only once

每面试一个人，不仅决定要不要马上雇佣这个人，而且我们一共只能雇佣一个人

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;
}