演算法導論之線上找女朋友問題

問題：假設你需要找一個女朋友。你先前的尋找嘗試都以失敗告終，所以你決定找一個相親代理。相親代理每天給你推薦一個女孩紙。你會面談此人，然後決定要不要與她交往。你必須付給相親代理一小筆費用來面談。要真正地找到一個女朋友則要花更多的錢，因為你必須和目前的女朋友分手，還要付一大筆中介費給相親代理。你的諾言是在任何時候，都要找到最佳人選來成為你的女朋友。因此，你決定在面談完每個應邀的女孩紙後，如果這個女孩紙比目前的女朋友更有資格，你就會和目前的女朋友分手，然後和這個新的女朋友交往。你願意為這種策略而付出費用，但希望能夠預測這種費用會是多少。

現在我們來考慮這個問題的一個變形。假設現在我們不希望面談所有的應邀的女孩紙來找到最好的一個，也不希望因為不斷有更好的申請者出現而不停地和新人交往與舊人分手。我們願意交往接近最好的應邀的女孩紙，只交往一次。我們必須遵守的一個要求：在每次面談後，必須或者立即和應邀者交往，或者告訴應邀者他們將無法得到這個交往的機會。在最小化面談次數和最大化和應邀者交往的質量兩方面如何取得平衡？

解答：

可以通過以下方式來對這個問題建模。在面談一個應邀者之後，我們能夠給他一個分數；令score(i)表示給第i位應邀者的分數，並且假設沒有兩個應邀者的分數相同。在面談j個應邀者之後，我們知道其中哪一個分數最高，但是不知道在剩餘的n-j個應邀者中會不會有更高分數的應邀者。我們決定採用這樣一個策略：選擇一個正整數k<n，面談前k個應邀者然後拒絕他們，再交往其後比前面的應邀者有更高分數的第一個應邀者。如果結果是最好的應邀者在前k個面談的之中，那麼我們將交往第n個應邀者。這個策略形式化地表示在如下所示的過程ONLINEMAXIMUM(k,n)中，該過程返回的是我們希望交往的應邀者的下標值。

/**
* 
* @param k 前k個被拒絕的應邀者
* @param n 總共n個應邀者
* @return
*/
int ONLINEMAXIMUM(int k, int n){
	int[] score = new int[n];
1	int bestscore = -999999;
2	for(int i = 1; i < k; i++){
3		if(score[i] > bestscore){
4			bestscore = score[i];
		}
	}
5	for (int i = k+1; i < n; i++) {
6		if(score[i] > bestscore){
7			return i;
		}
	}
8	return n;
}

對每一個可能的k值，我們希望確定交往到最好的應邀者的概率。然後選擇最佳的k值，並用此值來實現這個策略。先假設k是固定的。令M(j)=max_a<=i<=b{score(i)}表示應邀者a到b中的最高分數。令S表示我們成功選擇最好的應邀者的事件，S_i表示當最好的應邀者是第i個面談者時成功的事件。由於不同的S_i不相交，有。註意到當最好的應邀者是前k個應邀者中的一個時，我們不會成功，有

Pr{S_i}=0,i=1,2,...,k。於是得到

   （公式2）

現在我們來計算Pr{S_i}。為了當第i個應邀者是最好的時成功，有兩件事情必鬚髮生。首先，最好的應邀者必須在位置i上，用事件B_i表示。其次，演算法不能選擇在位置k+1到i-1中的任何一個應邀者，而這個選擇僅發生在當j滿足k+1<=j<=i-1時，程式第6行有score[j]<bestscore。（因為分數是唯一的，可以忽略score[j]=bestscore的可能性。）換言之，所有score[k+1]到score[i-1]的值都必須小於M(k)；如果其中有大於M(k)的數，將返回第一個大於M(k)的數的下標。用O_i表示在位置k+1到i-1中沒有任何應邀者被選取的事件。幸運的是，事件B_i和O_i是獨立的。事件O_i只依賴於位置1到i-1中數值的相對次序，而B_i只依賴於位置i的數值是否大於所有其他位置的數值。位置1到i-1中各數值的相對次序如何，並不應影響位置i的值是否大於位置1到i-1中的所有數值，而且位置i的值也不會影響位置1到i-1中值的次序。因此，應用公式1得

Pr{S_i}=Pr{B_i∩O_i}=Pr{B_i}Pr{O_i}

Pr{B_i}的概率顯然是1/n，因為最大值等可能地是n個位置中的任何一個。如果事件O_i要發生，在位置1到i-1中的最大值必須在前k個位置的一個，而且最大值等可能地是i-1個位置中的任何一個。因此，Pr{O_i}=k/(i-1)，Pr{S_i}=k/(n(i-1))。利用公式2有

我們利用積分來近似約束這個和數的上界和下界。根據不等式公式3，有

解這些定積分可以得到下麵的界：

這提供了Pr{S}的一個相當緊確的界。由於我們希望最大化成功的概率，因而主要關註如何選取k的值，使其能夠最大化Pr{S}的下界。（除此之外，下界表達式比上界表達式容易最大化。）將表達式(k/n)(lnn-lnk)對k求導，得

令此導數等於0，我們看到當lnk=lnn-1=ln(n/e)，或等價地，當k=n/e時，概率的下界最大化。因此，如果用k=n/e來實現我們的策略，則可以以至少為1/e的概率，成功地交往到最有資格的應邀者。

公式1：Pr{A∩B}=Pr{A}Pr{B}

公式3：當f(k)單調遞減時，可以使用積分來計算界