在线算法(online algorithm) - fll

时间:2024-03-12 17:20:44

在线算法(online algorithm)

看到一道有趣的题目,具体题目请看这里

由于对问题的结果抱求知态度,于是算了一把。在此写出详细分析过程。

按照思路,我们先假设选取固定的K值,然后计算能够找到最好的概率。最后确定如何选取最佳的K值,从而使得概率最大。

先定义几个符号:令M(j)表示从第一个到第j个人中的最高分数,令S表示我们成功选择了最好的人的事件,那么S就表示了最佳的人是第i个的事件。显然不同的S是不相交的,于是P{S}=P{S1}+P{S2}+...+P{Sn}。注意到我们假设最好的人为第K个,那么K之前的人都不会成功,因此P{Si}=0,i=1,2,...k。于是P{S}=P{Sk+1}+P{Sk+2}+...+P{Sn}

现在的工作是计算P{Si},i=k+1,...,n,也就是说第i个人会成功,那么这种情况下有两种事情是一定要发生的:首先是最好的人必须在位置i上,如果最好的人都不是第i个,那还有什么意思呢?用事件Ai表示最好的人出现在位置i上,由于人分布的随机性,显然Ai=1/n。第二件事情就是我们不能选择位置k+1到i-1中的任何一个人,而这个要发生就必须要这些人的分数必须小于M(k),否则按照我们的策略就会选取其中的任何一个分数大于M(k)的人。令Bi表示排在k+1到i-1的人没有人被选取的事件。那么P{Si}=P{AiBi}。看看A和B两个事件之间的关系,A表示第i个人的分数是最高的,而B表示从第一个到第i-1个人的分数都不能超过第i个人的分数,而至于前面i-1个人的相对次序如何,则对B没有任何影响,也就是说前面1到i-1个人的相对次序如果,并不影响第i个人分数是否大于1到i-1中的所有数值,这样好办了,两个事件是相互独立的。

如果B事件要发生的话,那么从第1个人到第i-1个人的最大值必须出现在第k个人之前,否则就肯定会选取了k到i-1中的某个人。而这个最大值则可以是1到i-1的任何一个数值,因此P{Bi}=k/(i-1)

现在可以计算了,由于A和B独立,那么P{Si}=P{AiBi}=P{Ai}*P{Bi}=k/(n*(i-1))

面的那个求和公式看起来比较眼熟不?可惜本人的高等数学忘得太多了,在一阵猛算后发现算不出来,网上找了很久,才想起来这是著名的调和级数,该级数是发散的,无法算出其精确值。在郁闷了一阵后找到利用积分来求其上下界的办法。利用下面的公式:

那么求和转化为:

这两个积分套用公式就可以得出结果为lnn-lnk

那么最终结果为:

现在我们已经知道了P{S}的上下界,即最大值和最小值,现在就是选取正确的k值使得下界取最大值,对对k求导得到(ln n - ln k - 1)/n,令导数为0得到ln k = ln n - 1,即k=n/e,其中e为自然数即2.71828......,那么k约等于0.37n。

由此看出,在线算法只能得到一个最好的概率,没有办法去选取一定是最好的值。其实人生就是这样的一个在线算法,由于你永远不知道下一步会怎样,只能根据过去来猜测。一旦走错了,就无法再重来,你永远也没有“如果一切可以重来,我会选择......”的机会,希望我们都按照在线算法一样做出了最好的选择。智者曾说过“30岁前不要怕,30岁之后就不要悔”,一旦做出了决定就不要后悔,因为即使后悔也没有重来的机会了。

PS:说下在线算法(online algorithm)和离线(offline algorithm)算法,离线算法也就是知道了所有的输入,根据某些条件来选取最佳策略,而在线算法就是无法预知到后面的输入,只能按照目前的状况来做出下一步的最好决策,在线算法追求的是与离线算法一样的好结果。关于在线算法的详细信息可以看维基。写到后面想起了suit同学的口头禅“人一辈子就不能做错事”,呵呵。