[弱智向] Maximum anti-chain in a poset

标题起名弱智向,是因为这个确实太弱智了。几年不练习,思维退化了?

Dilworth’s theorem 告诉我们,一个偏序集S上做chain partition,所含的最少partition数目就是S的最大anti-chain的大小。那么我们怎么求这个大小呢。

还记得相当远古的时候,ACM/OI界流传着一个名为“DAG最小路径覆盖”的问题,今天revise一下,果然是细思恐极啊。这玩意不就是来求上面说的这道题的么。

然后呢?然后就没有然后了。

Leave a comment

Lecture Collection

看来有必要把我认为比较神的lectures收藏一下,要不然丢了都没地方找。

Submodular Optimization:

http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/

Combinatorial Optimization:

http://www.cs.illinois.edu/class/sp10/cs598csc/

Leave a comment

关于3维球面上n点共半球的概率

题目意思很简单。一个3维球面上,均匀随机的投n个点(这里的随机是指任何n个点的组合,出现的概率都是相同的)。问存在一个半球面,使得这n个点同时在该半球面的概率。

这题有点意思,先是xiaodao在soso上搜出来了个几乎没什么解释的结论,然后在xreborner神的提示下才想明白。首先我们对每个点p_i,做其相对于圆心O的镜像q_i。这样,每个点选取其原像p_i与镜像q_i,总共有2^n种组合。我们查看这2^n个组合中有多少个是共半球的,假设组合数为F(n),显然该题的结果便是F(n)/2^n。

下面我们考虑如何算出F(n)。对每个点p_i,我们将其对应到一个半球面SS(p_i)上,这个对应方式就是先做p_i相对于原点的镜像q_i,然后p_i与q_i连线的中垂面会将整个球分成两个半球面,其中p_i所在的半球面就是SS(p_i)。我们可以发现,某点v所对应的SS(v)包含点p_i,当且仅当v在SS(p_i)这个半球面上。这样,如果n个点可以被同一个半球面所包含,那么这n个点对应的半球面SS(p_i)的交集应该非空,且这个交集中的每一个点v对应的SS(v)都可以称为包含它们的半球。

对于每一个点p_i,都对应球面上的一个大圆C(p_i),它是SS(p_i)的边界,这n个大圆会将整个球面划分成数个小面,你会发现每一个小面和上述的一个交集存在一一对应,于是n个大圆对球面的分割数就等于可以共半圆的组合数F(n)。不难发现n个圆的总分割数共有2+\sum_{i=1}^{n-1}2i = n^2-n+2,故这道题的答案就是(n^2-n+2)/2^n。注意,在这里我们不需要考虑任何边界情况,比如是否有多个大圆共点甚至重合等,因为满足这些条件点的组合数相对n个点的总组合数来说,不在同一个数量级,也就是被选中的概率为0。

—-

上半部分是原题,下面开始推广,也就是将公式推广到高维情况。就不妨说4维吧。

事实上如果按照上面的思路推广,可以发现交集个数等于大圆分割数的结论是仍然是成立的,只是4维的时候圆变成了球,也就是我们要求n个3维球体在4维超球面上的分割数。这个是很难计算的(当然,神如xreborner神随手就将这个分割数算出来了,拜啊),所以在这里我们换一个角度考虑问题。事实上我们发现,我们根本没必要考虑3维球体的交,因为实际上3维球体是4维超球和一个过球心的超平面的交集。而这些3维球体对4维超球的分割数,实际上和这些过球心的超平面对整个4维空间的划分数是一一对应的。所以我们只需要计算n个共点(即球心)的3维超平面会将4维空间划分成多少部分就行了。

其实到了这里,问题还是没有什么头绪,所以我们要考虑先解决低维情况,然后看看其解决方法是否可以向高维进行推广。不妨拿容易理解的3维出手。假设3维空间中目前已经有了k个共点2维平面,然后我们向其中加入一个新的2维平面,看看会分割出多少新的小空间出来。你会发现,新平面和每个2维平面的交集都是一条直线(所谓“1维平面”),而新出现的空间数就是这些共点的“1维平面”将这个新加入的“2维平面”划分的子平面个数。

到了这里相信就很明白了,其实这个式子就是一个标准的递推式。我们设F(n, k)为n维空间内k个共点的n-1维超平面对其的划分数。这样根据上面的推导,不难列式F(n, k) = 2 + \sum_{i=1}^{k-1} F(n-1, i)。

Leave a comment

An interview problem

这是一道很有意思的题目。题目是说有三个turing machine,然后我们有一个oracle,可以对任意TM返回它是否会halt,但是它最多只能被查询2次。现在要你设计一个方法,对每个TM判断出它会不会halt。

好了。这道题其实一开始描述得不太清晰,原题是说“有3个TM和1个可以判 halt的oracle,问如何查询2次判断出每个TM是否halt”。这种描述容易让人产生误会,以为只能查询两次,得到两个bit。其实不是这样,因为你可以不调用oracle,自己做一个必停的TM来得到更多的bit。厘清了这个之后,就不难想了。

事实上很显然,如果只查询两次oracle,最多只能得到2个bit,只利用它们是绝对不可能区分8种不同情况的,所以我们必须要利用这两个bit得到一些关键信息,然后利用这个来构造TM去判断。事实上,如果还记得定理“若L与L补均为RE,则L与L补均为R”的证明,这个事情很容易理解。该定理中我们将每个TM拆分成单步,然后构造一个元图灵机去模拟之,这样可以模拟出每个TM的每一步。同样,我们也可以用这种方法,模拟出这三个TM的每一步。所以如果某一个TM必停,则一定能模拟到它停的那一步。

故我们可以构造一个TM,计数有多少个TM会halt,如果halt的TM个数达到X则halt,否则就继续执行。这样我们可以通过查询该TM是否halt,来得到halt的TM的个数是否多于X。由于halt的TM个数只有4种可能,所以它完全可以通过2个bit的查询,用二分的方法得到。有了halt的TM的个数,一切就很简单了。我们再构造类似的UTM,模拟每个TM的每一步,并且记录下有哪些TM已停。如果停机的TM个数到达了总个数,则该UTM停机,此时输出第k个TM是否已经停机即可。

1 Comment

Gale-Ryser Theorem

好久不做脑力劳动,感觉脑子都生锈了。这么简单的一个问题居然还要看proof才意识到——当然也是我自己没认真想,看到有theorem就直接去查了。不过还是有点小气馁啊。

好了,这是一个很简单——描述和证明都简单的小问题。首先给你n的两个分割c和r,然后判断是否存在一个0-1矩阵,使得这个矩阵的每行和为r,每列和为c。

嗯。事实上这是那本网络流砖头书的书后习题一道——如果没有那个“0-1矩阵”的条件的话。事实上不考虑0-1矩阵的条件,这就是一个裸得不能再裸的网络流。不过对于0-1矩阵显然有更好的方法,也就是题目的Gale-Ryser theorem。

这个定理的意思就是说,我们基于r定义n的另一个分割c*。这个c*的值这么确定:假想一个矩阵A,它的每一行都是前面一大堆1后面一大堆0的形态,并且由于行和是r,所以每一行前面多少个是1就确定了。这样一个矩阵,它的列加和出来的分割就是c*。然后Gale-Ryser theorem的内容很简单:存在这样一个0-1的矩阵,当且仅当c*支配c。这里c*支配c的含义是指,任意一个整数k,c*的前k个元素之和都不小于c的前k各元素之和。

好了,其实这里面的必要性已经不用证了,几乎是显然的。因为c*已经是把所有的1都尽可能的放到最前面了,当然不可能会有比它还大的。下面证明一下必要性。我们找到两个数a和b,满足a是第一个c*[a] > c[a]的下标,b是第一个c*[b] < c[b]的下标。首先观察可知必然有a > b,否则的话c*前b项和必然会比c的要小。此时我们将c*[a]减1,c*[b]加1。显然修改过后的c*中的每个分量都更加接近c,只要我们能证明修改过后的c*仍然支配c,那么我们就可以通过不断的修改最终达到c,相应的在矩阵的操作就是不断的将a列的某个1与另一列的某个0交换,进而得证命题。

而这个支配的性质其实非常好证,因为b是第一个c*[b] < c[b]的下标,也就是说它前面的下标都是c*[i] >= c[i],并且确实存在一个a使得等号不成立,所以此时将c*[a]减掉1之后绝对不会使得该和变得比c小,于是证明完毕。

Leave a comment

CodeChef January 2012 Challenge, GAPFILL

题目就是给一个n*m的方格阵,每个格子都有两种颜色可供选择:黑、白。然后你每次可以对任意一个格子(a, b)做一个操作,该操作将第a行的所有方格、第b列的所有方格、(a, b)本身的颜色都调换一次(也就是黑变白,白变黑)。我们的目标是将所有的格子都变成黑色。显然在共计2^{nm}种初始状态中,并不是所有的初始状态都可以达到这一目标,问其中到底有多少初始状态可以达到。

嗯,先说结论,因为在观察小数据之后结论很好猜测出来:(1) 若n, m均为偶数,结果是2^{nm} (2) 若n, m均为奇数,结果是2^{(n-1)(m-1)+1} (3) 若n, m是一奇一偶,结果是2^{n(m-1)+1}(m为奇)或2^{(n-1)(m)+1}(n为奇)。下面就看怎么证明。
如果给定初始状态,问到底有没有解,你会发现这个问题实际上就是模2意义下线性方程组是否有解的问题,这里我们吧变量x_{(a, b)}定义为(a, b)这个格子到底被按了几次,然后Ax = b (mod 2)中的b就是初始状态。如果这么看的话,那么能让该方程组有解的b的个数其实就很显然了,因为我们只需要在A的行向量中找到模2意义下的极大线性无关向量组,这个组内向量的个数关于2的幂就是结果。所以我们实际上要求的就是这个极大线性无关向量组的基数。在这里我们令黑色为0白色为1。为了简便,下文直接用0/1来代表黑/白。

我们将这个过程形象化一下。考虑一个方格阵,其格子初始都是0。我们如果我们在线性组合内选择了(a, b)这个格子对应的向量,实际上就相当于是在这个方格阵内按下了(a, b)这个格子。这样一些向量线性组合(在模2意义下,下文略)的结果,实际上就相当于是在一个全0的方格阵内,连续按下这些向量所对应的格子之后的局面情况。我们下面的证明中就用这种连续操作的结果来代替线性组合的结果论述。

一、n, m均为偶数

此时我们要证明A中任何一个向量都无法通过其与向量的线性组合获得。根据对称性,我们只需要证明右下角的(n, m)无法通过其余格子获得就可以了,因为我们想证明任意格子,只需要将这个证明中相应的行列改换一下即可,没有本质区别。也就是说,我们要证明,其余格子无论怎么按,都无法获得与按下(n, m)同样的效果。为此我们将这个方格阵分为四块。(1) 坐标为(i, j)的格子,其中1 <= i <= n-1, 1 <= j <= m-1。也就是左上角的(n-1)*(m-1)方块,下文简称“左上角方块”。 (2) (n, m)这个单独的格子,也就是最右下角的格子。 (3) 坐标为(1, m), …., (n-1, m)的格子,也就是最后一列除掉最右下之外的格子,下文简称“最后一列”。(4) 坐标为(n, 1), …, (n, m-1)的格子,也就是最后一行除去最右下角的格子,下文简称“最后一行”。(注意这里面最后一行和最后一列都不包括最右下的格子)。

首先我们观察(n, m)这个格子被按下后(也就是我们需要达到的最终结果)有什么特点。可以发现它就是最后一行、最后一列、最右下角的格子全部为1的情况。我们想通过按下其它的格子达到同样的效果。不难想到,如果想让(n, m)为1,无论左上角方块中的格子怎么按都不会影响右下角,所以只能通过按下最后一行和最后一列达到这个效果。而最后一行与最后一列显然总共被按下了奇数次。不失一般性,我们不妨设最后一行的格子被按下了奇数次,最后一列被按下了偶数次。在这么按完后,我们发现由于最后一行被按下奇数次,导致最后一行全为1,同理最后一列全为0,并且右下角为1。下面我们就需要通过调节左上角方块来使得最后一行与最后一列全为1。而这是不可能实现的,因为左上角每个格子都会改变最后一行与最后一列中恰好一个方格的状态,这使得最后一行与最后一列1的总个数的奇偶性不会发生变化。显然初始状态中1是偶数个(因为n,m都是偶数),而目标状态中1是奇数个。故得证。

二、n, m一奇一偶

不妨设n为偶m为奇。此时我们观察除去最后一列外那n(m-1)个格子。因为这个子阵是行列全偶的阵,根据上面的结论,显然它们之间线性无关。下面我们考虑,这n(m-1)个格子可以用于表示最后一列的格子么?答案是否定的,证明方式同上一节中的证明类似。比如我们要证明这n(m-1)个格子不能用于表示最右下角的(n, m)。首先可以发现若能表示,则最后一行的格子必然被按下了奇数次(注意最后一列不能按,因为我们是要用前n(m-1)个来表示(n, m)),这使得最后一行所有格子都是1,最后一列的格子都是0,总数是奇数个1,目标是偶数个1。然后通过调节左上角同样会保持最后一行与最后一列总体的奇偶性,所以得证。

由于上面证明了n(m-1)个格子是不够的,所以我们势必要增加最后一列中某个新的格子来扩张。增加几个就足够了呢?答案是一个。因为我们增加了一个之后,就会使得某一行中的所有格子的取值都被固定了。我们考虑把这一行所有格子对应的向量相加——相当于是在全0阵中按下这一行中的所有格子一次。此时我们发现,除了这一行之外的所有格子必然都是1,因为每一列正好有一个格子被按下了。而这一行呢?也是全1,因为列是奇数。所以此时我们随便选取一行,将这一行内所有格子对应的向量相加,总和必然是所有变量取值的加和,。这是一个定值,因为有一行已经完全固定了。故因此可以轻易计算出每一行未被确定的那一个格子对应的取值。

故总体来说,可供自由选择取值的线性无关向量组有n(m-1)+1个向量。

三、n, m均为奇数

其实这一节的结论就已经是显然的了。首先易证左上角(n-1)(m-1)线性无关,并且是不够的。然后多加了一个之后,就可以确定出每行每列剩余的那个格子的取值(因为行列均为奇数,你对行求和与对列求和的结果都是所有变量的和)。所以此时结论显然是(n-1)(m-1)+1。

Leave a comment

A technique to analyze pairwise independent variables

之前对概率方面的演算一直不够,导致对很多技巧都非常的不熟悉。这次在“Randomized Algorithms”第三章的习题里面才见识到一些技巧,觉得非常不错。所以写出来一下。

首先要说明一点的就是两两独立(pairwise independent)和完全独立之间有着很大的区别,具体区别不再细说。所以在两两独立的情况下,我们一般很难分析出某种组合出现的确切概率。在这种随机变量间有复杂关系的情况下,我们一般的手段都是用一些技巧越过这些的复杂关系,应用一些对随机变量关系没有任何要求的公式进行变换。比如说期望的线性可加性就是一个非常好的技巧,E[X+Y] = E[X] + E[Y]无论在任何时候都成立,很多有关期望的结论都可以应用这个公式美妙的推导出来。还有一个就是下面需要用到的技巧,\sum_i Pr[e_i] – \sum_{i, j} Pr[e_i \intersect e_j] <=  Pr[\union_i e_i] <= \sum_i Pr[e_i]也是无论e_i之间是什么关系都成立的公式。这个公式有一个非常美妙的扩展,名叫boole-bonferroni inequality。本质上就是公理化概率论结合容斥原理之后,所得出的非常易于理解但是有用的不等式。

还是拿习题说话吧,这是“Randomized Algorithms”的作者Rajeev Motwani的一篇论文里的一个结论,后来被他出到了该书第三章的习题里。有两个集合S和T,满足|S| = |T| = n,全集为U。现在需要你在U中随机选择一个子集R,并且R中每个元素出现的概率都是p,并且任何两个元素出现的概率两两独立。如果满足:(1) R \intersect S = \emptyset (2) R \intersect T != \emptyset,那么我们就说R是一个“好集合”。现在需要你选择一个合适的p,使得这个随机选择出的R是“好集合”的概率不小于某个确定的常数。

我们首先将U中的元素编号,从0编号到2n-1。对每个元素,我们定义随机事件M_i为第i号元素被选择的事件;~M_i便为M_i的补。另外对每一个T中的元素,定义随机事件F_i为第i号元素(必须是 T中的元素)被选中,并且集合S中的所有元素都没有被选择的事件。我们已知的是M两两独立。明显有R是“好集合”的概率可以被形式化表示成Pr[\union_{i \in T} S_i]。下面我们来分析它的下界。

首先我们根据上面的不等式,可得Pr[\union_{i \in T} S_i] >= \sum_{i \in T} Pr[S_i] – \sum{i, j \in T} Pr[S_i \intersect S_j]。所以我们要分析Pr[S_i]的下界和Pr[S_i \intersect S_j]的上界。事件S_i可以表示成\intersect_{j \in S} ~M_j \intersect M_i,所以Pr[S_i] = Pr[M_i] * Pr[\intersect_{j \in S} ~M_j | M_i] = Pr[M_i] * (1 – Pr[\union_{j \in S} M_j | M_i]) >= Pr[M_i] * (1 – \sum_{j \in S} Pr[M_j | M_i])。这里应用到了上面那个不等式的右半部分,它的结果就是很巧妙的将多事件共同出现的概率拆分成了两个事件间的条件概率。而我们又知道这些事件之间是两两相互独立的,所以Pr[M_j | M_i] = Pr[M_j] = p。这样我们就分析出了Pr[S_i] >= p(1-np)。

而对于第二部分Pr[S_i \intersect S_j]的概率分析更为简单,形式化写一下就是Pr[S_i \intersect S_j] = Pr[M_i \ intersect M_j \intersect  \intersect_{k \in S} ~M_k]。如果我们将后面那些\intersect_{k \in S} ~M_k的事件忽略的话,可知Pr[S_i \intersect S_j]  <= Pr[M_i \ intersect M_j] = p^2。综合上面两部分,我们可以得到原问题概率的下界为np(1-np) – (np)^2。如果我们取p = 1/(3n),便可以得到概率的下界为1/9。

, , ,

1 Comment

Lower bound of randomized sorting algorithm

今天吃饭的时候无聊,于是思维莫明奇妙的就转到了randomized sorting的下界分析上了。于是就发现有一些不对劲。思维的起因很简单,我分析出了下界是随机快排的期望运行时间2H_n-n,然后随机快排的期望正好是2H_n-n,而这正好吻合,一丝不差。这说明那个如此简单的选择分割元素的算法,在我的分析结果中竟然已经达到了实际意义上的最优值!这显然让我产生了很大的怀疑。然后才突然意识到,我那个简单的证明其实有严重的漏洞。我在那个证明中假设排序算法一定是选择分割元素后进行划分的模式,而这个显然无法代表全部的排序算法。而且中间我也默认它是选择某个固定位置,而完全没有考虑那个位置可能是某种通过计算得来的方式(这种情况下分割元素的分布会改变)。总而言之,可以肯定我那个证明已经是完完全全的错了。

所以我应该还是要回归到Decision Tree上来。我们对数据还是应该选择均匀分布,这里没有问题,不过计算下界的方法,则是应该去计算Decision Tree叶子节点加权平均长度的最优值。由于数据是均匀分布,所以每个叶子节点的权值都相同,这样我们只要找到所有叶子节点深度和的最小值就好了。

很容易可以猜到这个Decision Tree应该是一个满二叉树的形状,也就是叶子节点的最大深度和最小深度的差值不能大于1。证明是显然的,因为如果这个差值大于1,那么我们只要把长的那条路上的两个叶子全部转移到短的路径的叶子上,就可以让深度总和减小。而这个时候Decision Tree叶子节点的加权平均深度显然是O(log(n!)) = O(nlogn),于是得证。

, , ,

Leave a comment

About Las Vegas Algorithm and Yao’s Technique

最近的读书会一直在看Rajeev Motwani那本<Randomized Algorithms>。虽然以前看过一阵子,不过从来没有做过习题,想留着以后做的。所以趁这次的机会也就把后面的题目清理了一遍,倒真是做出了不少感觉,比光看书是强不少。这篇文章也正是因此才写。本来只是被后面的一道习题难住了,结果让xreborner神轻松秒杀,大为震惊之下决定一定要写出来膜拜+体会一番。结果想着想着就觉得那个还是多写一些自己的想法在里面比较好。

这次的文章主要和RAs第二章的内容相关,主要就是介绍分析随机算法计算复杂度下界的Yao’s Technique(没错,这里的Yao就是姚期智)。负责的江敏老师说第二章是很理论的东西,他们看的时候就直接略过了,不过看过之后我觉得相当具有启发性。

首先还是稍微说下Las Vegas算法。LV是一类随机算法,它的运行时间是一个随机变量,但是它的正确性永远保证为100%。也就是说我们无法说清楚LV算法的一次运行会在什么时候终止,但是当它终止时,所得到的答案必定是正确答案。比如说大家都很熟悉的Pollard-Rho就是运行时间的期望为O(n^0.25)的LV算法。当然随机算法还包括Monte-Carlo,它和Las Vegas不太相同,不过现在不去考虑它。下文所说的“随机算法”,实际上默认都是指Las Vegas算法。

对于确定性算法而言,它对每一组规模为n的合法输入,都会有一个确定不变运行时间——或者我们用计算次数来衡量。所以确定性算法的最坏时间复杂度很好定义,就是在所有规模为n的合法输入中,找到计算次数最多的那个输入,把它的复杂度称为该算法最坏情况下的时间复杂度,也就是worst-case time complexity。相对来说,随机算法也可以定义最坏时间复杂度,只是由于算法的运行时间是一个随机变量而不是确定数值,所以我们只能用它的期望运行时间来衡量。具体来说,对于每一个规模为n的合法输入,LV算法都有一个期望计算次数。我们在所有规模为n的合法输入中,找到期望最大的那一组数据,用它的期望来衡量这个LV算法的效率,也就是expected worst-time complexity。

在这里就有两个很容易搞混的概念出现。就是说确定性算法和随机算法实际上都是有“期望时间复杂度”这个概念的,可是确定性算法的期望时间复杂度,它的随机性体现在数据的随机分布上;而随机算法的期望时间复杂度,它的随机性却体现在算法本身而不是数据上。也就是说,确定性算法的期望时间复杂度会随着输入数据分布的改变而改变,但是随机算法的期望时间复杂度却和数据的分布完全无关。在这里我们用到了一个思想,就是任何一个随机算法,其本质上就是“在所有正确的确定性算法上的一个概率分布”。也就是说,一个随机算法,其本质就是在每次运行开始时,以某个概率分布随机的选择一个正确的确定性算法,然后用这个确定性算法去产生本次输入的输出。所以我们可以说,随机算法就是将数据的随机性转变成了算法本身的随机性。数据的随机性可能会受到很多因素的影响,但是算法的随机性却不受任何人控制。所以如果用一个ACMer / OIer比较容易理解的话说,虽然一个确定性算法的期望运行时间会很好,但是我们却仍然可以人工构造worst-case数据把它干掉(也就是说你输入的分布集中在该算法的worst-case附近);但是随机算法你是没什么办法去把它卡掉的,除非你预先知道它的实现,然后故意构造数据(其实这样也很难)。

所以这里就是提出一个问题:我们有很多种方法去分析一个问题的确定性算法运行时间的下界,但是我们如何去分析它的随机算法的期望运行时间下界?举个具体的例子,我们如何说明随机快排的期望O(nlgn)运行时间是渐近最优的?你会发现这时算法本身的随机性会使很多确定性算法的分析方法完全失效。比如随机快排,这种情况下决策树是没用的,因为对于每组不同的输入,算法最开始会随机的选择一个决策树,你也不好说他到底会以多大的概率选择到了一个正好是好或坏的树来判定。

而Yao’s Technique却很好地解决了这个问题。它用博弈论的方法,在“随机算法对任意数据的期望运行时间”和“确定性算法对随机数据的期望运行时间”之间建立了一种联系,使得你可以通过分析确定性算法的复杂度,来得到随机算法的期望复杂度下界。而且这个方法最美妙的一点,就是“确定性算法对随机数据的期望运行时间”中,那个随机数据的分布,竟然并不固定,而是可以由你自己来选择的。你完全可以选择一个很容易分析出结果的分布,在这种分布下计算确定算法的复杂度,得到结果就是一个随机算法的复杂性下界。当然,这个分析出的结果是不是紧的,取决于你所选择的分布到底是不是恰当。

我们稍微谈论一下细节。我们现在来进行一个双人零和博弈。你是算法设计者,我是数据设计者。对于某个问题,你可以在所有正确的确定性算法中选择一个,而我可以在所有输入规模为n的输入数据中选择一个。双方同时进行选择,互相不知道对方的策略。在你我都作出选择之后,你选择出的算法在我选择出的数据上会有一个运行时间,这个运行时间的数值就是你要付给我的钱数。所以你的目标就是要让这个运行时间越小越好,而我的目标就是让这个运行时间越大越好。对于双人零和博弈,最经典的结论莫过于那个混合博弈策略的Nash均衡。我们令T(A, I)表示确定算法A在数据I上的运行时间,p是一个所有确定性算法A上的分布,q是一个所有数据上的分布,A_p表示遵循随机分布p选择的出来一个A的实例,I_q类似。那么我们有:\max_q\min_A E[T(A, I_q)] = \min_p\max_I E[T(A_p, I)]。进行一下简单的数学变换,我们就有:对于任何一个数据的分布q和任何的一个算法分布p,永远有 \min_A E[T(A, I_q)] <= \max_I E[T(A_p, I)]。右面的式子其实是“任意一个随机算法在其最差数据下的期望运行时间”,而左面的式子其实是“任意一个数据分布下最优算法的期望运行时间”。而这里面算法的分布和数据的分布都是任意的,你可以任意选择。对随机算法的任意性,可以解释成是随机算法的下界;而对数据随机性,使得你可以选择一个你算起来方便的分布,在这组分布下计算最优算法的期望运行时间。

所以这里就又产生了一个问题:就算你选择了一组“看起来很和谐”的分布,你又如何来找到这组分布下期望最小的算法呢?或者说你如何证明选择的某个算法就是最优的呢?这也不是一件容易的事情,对于随机快排来说,你就可以分析出:如果数据是均匀分布,那么任何一个确定性算法的期望运行时间都是O(nlgn),所以每一个都是最优的,没有区别。但是对于其他的问题,你很难每个都能找出这样简单的结论出来。于是很多时候只能退而求其次,我们不去计算出那个最优算法的具体期望是多少——因为基本很难算出来——而是构造出一个分布,然后证明任何的确定性算法,在这组数据分布上的运行时间是存在下界的。也就是说,“确定算法的期望运行时间”是随机算法的下界,我们对这个下界本身用别的方法再去找一个下界,然后让这个“下下界”来作为我们分析的结果。

比如书后的这道练习题:给定一个长度为n的字符串,保证串中只含有0和1。我们的目标是判断这个字符串中是否含有三个连续的1,你每次能做的操作就是你可以任意选择一个位置,查询该位置上的数值。问该问题随机算法查询次数的下界是多少。

直觉告诉我们这个问题的答案是\Omega(n),所以根据Yao’s Technique,我们要选择一组分布,让任何确定性算法在这组分布上都是\Omega(n)的。选择分布就是:对所有输出结果为Yes的数据,其出现概率为0;对输出结果为No的数据,其出现概率不做约束。对于任何一个确定性算法,下面证明其在任何一个结果为No的数据中都要至少查询n/3次方能作出回答。采用反证法,我们将该字符串3个3个一组,也就是位置为{1, 2, 3}的一组,{4, 5, 6}一组,{7, 8, 9}一组,等等。显然组数是n/3。如果某一个确定性算法查询次数少于n/3次,那么必然存在一组,该算法没有对这一组中的任何一个数字进行过查询。那么我们应该可以得出结论,就是这三个数字无论如何变化,对算法的输出都不会产生任何影响,也就是应该输出No。而这显然是不可能的,因为当这三个数均为1时,该算法应该输出Yes而不是输出No,所以这样的算法必然不可能是正确的。所以我们就证明了该问题的下界是\Omega(n)。而O(n)的算法很容易设计,所以该问题的随机算法是\Theta(n)的。

最后就是这篇文章的起源,也就是我问xreborner神的那个问题:对于任何一个无向图G,我们要设计一个随机算法,用于检测G中是否含有完美匹配,你每次能做的操作就是查询该图中的两点间是否存在边。要求证明该问题随机算法的下界是\Omega(n^2)。

同样直觉告诉我,应该只需要关注二分图就好,因为一般图的匹配实在是太复杂了。所以现在的问题就是,我们如何设计出一个二分图,使得任何一个完美匹配的算法,都至少要在这组数据上运行\Omega(n^2)次方能确定答案?这个就是xreborner神的神构造。我们做一个n*n的二分图邻接矩阵,也就是左右各n个点,其中n必须是奇数。然后这个邻接矩阵中,最上方(n-1)/2行和最左方(n-1)/2列的值都是1,而其余的值都是0。显然,最下方(n+1)/2的点只对应到了另一侧(n-1)/2的点,所以根据Hall定理,该图不存在完美匹配。但是右下方(n+1)/2 * (n+1)/2的全0矩阵中,只要任何一个数字是1,都会使得该图存在完美匹配。所以任何确定性算法,都必须要将下\Theta(n^2)个0全部检测到,才能给出No的回答,所以便证明了\Omega(n^2)的下界。

, , ,

2 Comments

TCO 2011 Round 1 Level 2 Muddy Road

一条路上有n(n <= 50)个点,每个点都有一定的概率有泥巴,不同的点概率不同,设为road[i]。你从最左侧的点出发,希望到达最右侧的点,每次当你在i号格子时,你可以选择走到i+1或者i+2号格子。对每一个确定的地图,你都一定要选择踩到泥巴数最小的走法。现在问这个踩到的最小泥巴数的期望。

嗯。这道题还是很不错的。我不太清楚如果我是在比赛中碰到这道题,我会怎么做,因为我在场外只想了5分钟就去看别人的做法了。不过对于我这种算期望还不够多的人来说,这次算是让我想通了一些关键部分。说句题外话,百度之星贴吧里有人鄙视大量练习是“做题机器”,表示对这样的言论已经没有围观的兴趣了,只想鄙视。

首先说一下O(n)的方法。其实想一想就会知道,最优策略的话,肯定要在右侧的两个格子中选择一个没有泥巴的走,如果两个都有的话那就一定要走得越远越好(也就是要跨过一个泥巴踏上第二块泥巴)。所以我们就可以据此做一个DP了。我们从最后一个格子往前推。对于位置i,如果位置i+1没有泥巴(概率为road[i+1]),那么我们应该选择走到i+1,此时期望就是dp[i+1];否则的话,我们一定要选择i+2,再讨论一下i+2位置的情况分别求和就好了。

不过这么做实际上就没有什么启发了,最多也不过就是个普通的算法问题。下面我们以概率的角度求解。首先我们发现,整个地图被划分成了一些无泥巴的路和一些有泥巴的路交错出现的情况,而最终的结果一定是:对每段连续的泥巴路,对其长度除以2向下取整,再求和。我们令X_{i, j}表示[i, j]区间中i与j无泥巴,而i < x < j的x都是有泥巴时这一段需要踩到的次数(也就是上文所说的length/2)。而最终的答案就是E[\sum_{i < j} X_{i, j}] = \sum_{i, j} E[X_{i, j}],而对任意的(i, j), E[X_{i, j}]显然是很好算的。于是我们就可以得到一个写起来很简单的O(n^3)的算法。

Leave a comment

Follow

Get every new post delivered to your Inbox.