huojia

1.最长公共子序列的结构

解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2^m个不同子序列，从而穷举搜索法需要指数时间。

事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：

定理: LCS的最优子结构性质

设序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的一个最长公共子序列Z=<z₁, z₂, …, z_k>，则：

1. 若x_m=y_n，则z_k=x_m=y_n且Z_k-1是X_m-1和Y_n-1的最长公共子序列；
2. 若x_m≠y_n且z_k≠x_{m ，}则Z是X_m-1和Y的最长公共子序列；
3. 若x_m≠y_n且z_k≠y_n ，则Z是X和Y_n-1的最长公共子序列。

其中X_m-1=<x₁, x₂, …, x_m-1>，Y_n-1=<y₁, y₂, …, y_n-1>，Z_k-1=<z₁, z₂, …, z_k-1>。

证明

1. 用反证法。若z_k≠x_m，则<z₁, z₂, …, z_k ,x_m >是X和Y的长度为k十1的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。因此，必有z_k=x_m=y_n。由此可知Z_k-1是X_m-1和Y_n-1的一个长度为k-1的公共子序列。若X_m-1和Y_n-1有一个长度大于k-1的公共子序列W，则将x_m加在其尾部将产生X和Y的一个长度大于k的公共子序列。此为矛盾。故Z_k-1是X_m-1和Y_n-1的一个最长公共子序列。
2. 由于z_k≠x_m，Z是X_m-1和Y的一个公共子序列。若X_m-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是X_m-1和Y的一个最长公共子序列。
3. 与 2.类似。

这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

2.子问题的递归结构

由最长公共子序列问题的最优子结构性质可知，要找出X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最长公共子序列，可按以下方式递归地进行：当x_m=y_n时，找出X_m-1和Y_n-1的最长公共子序列，然后在其尾部加上x_m(=y_n)即可得X和Y的一个最长公共子序列。当x_m≠y_n时，必须解两个子问题，即找出X_m-1和Y的一个最长公共子序列及X和Y_n-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Y_n-1及X_m-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算X_m-1和Y_n-1的最长公共子序列。

与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列X_i和Y_j的最长公共子序列的长度。其中X_i=<x₁, x₂, …, x_i>，Y_j=<y₁, y₂, …, y_j>。当i=0或j=0时，空序列是X_i和Y_j的最长公共子序列，故c[i,j]=0。其他情况下，由定理可建立递归关系如下：

3.计算最优值

直接利用(2.2)式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储X_i与Y_j的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。

Procedure LCS_LENGTH(X,Y);begin  m:=length[X];  n:=length[Y];  for i:=1 to m do c[i,j]:=0;  for j:=1 to n do c[0,j]:=0;  for i:=1 to m do    for j:=1 to n do      if x[i]=y[j] then        begin          c[i,j]:=c[i-1,j-1]+1;          b[i,j]:="↖";        end      else if c[i-1,j]≥c[i,j-1] then        begin          c[i,j]:=c[i-1,j];          b[i,j]:="↑";        end      else        begin          c[i,j]:=c[i,j-1];          b[i,j]:="←"        end;  return(c,b);end;

由于每个数组单元的计算耗费Ο(1)时间，算法LCS_LENGTH耗时Ο(mn)。

4.构造最长公共子序列

由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到"↖"时，表示X_i与Y_j的最长公共子序列是由X_i-1与Y_j-1的最长公共子序列在尾部加上x_i得到的子序列；当b[i,j]中遇到"↑"时，表示X_i与Y_j的最长公共子序列和X_i-1与Y_j的最长公共子序列相同；当b[i,j]中遇到"←"时，表示X_i与Y_j的最长公共子序列和X_i与Y_j-1的最长公共子序列相同。

下面的算法LCS(b,X,i,j)实现根据b的内容打印出X_i与Y_j的最长公共子序列。通过算法的调用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。

Procedure LCS(b,X,i,j);begin  if i=0 or j=0 then return;  if b[i,j]="↖" then    begin      LCS(b,X,i-1,j-1);      print(x[i]); {打印x[i]}    end  else if b[i,j]="↑" then LCS(b,X,i-1,j)
                      else LCS(b,X,i,j-1);end; 

在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。

例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS计算出的结果如图2所示。

图2   算法LCS的计算结果

5.算法的改进

对于一个具体问题，按照一般的算法设计策略设计出的算法，往往在算法的时间和空间需求上还可以改进。这种改进，通常是利用具体问题的一些特殊性。

例如，在算法LCS_LENGTH和LCS中，可进一步将数组b省去。事实上，数组元素c[i,j]的值仅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三个值之一确定，而数组元素b[i,j]也只是用来指示c[i,j]究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一个数值元素所确定，代价是Ο(1)时间。既然b对于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。这一来，可节省θ(mn)的空间，而LCS_LENGTH和LCS所需要的时间分别仍然是Ο(mn)和Ο(m+n)。不过，由于数组c仍需要Ο(mn)的空间，因此这里所作的改进，只是在空间复杂性的常数因子上的改进。

另外，如果只需要计算最长公共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算c[i,j]时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m, n)。

     前天来电话说，上次面的是intern，问我愿不愿意去。

     询问了很多，然后也没说清楚。就说周五去面一下。昨天收到ibm 的 ss 面试通知后，本来想今天就不去了。毕竟做intern意义不大，而且时间紧迫啊。

     10点多msra的电话打来说，如果合适可以提供msra的正式职位。于是欣然前往。

     到msra已经11点多，要面的researcer忙碌中，于是一个北大的哥们出来让我写了几个程序。

     难度并不高，可能昨天晚上睡觉太晚加上今天本来就不想去，一进ms就热的要命。所以程序写的不好。写了一会儿，那哥们儿说就到这儿。偶心里凉啊。怎么这就cut了？

     被告之等招人的researcher面我。

     漫长的等待。。。

     到12点多，面我的大哥进来说，先让我跟他们去吃饭，下午再面，于是跟几个intern一起到sigema B1 吃饭。吃的时候就听他们三个说话了。我也插不上嘴。：（

     回到F5的lab，面试大哥迟迟不回来。上午面我那个哥们(北大的学生也是03 的硕士)＆旁边几个intern聊天，期间给我一听cola，没心情啊。

     好不容易等到面试大哥来，于是跟着进入reseracher  room。这位大哥真的很kind，让我一下不是那么紧张。问研究生作的东西的情况。问细节。问数字图像处理算法。然后问了问本科学啥，一听数学，兴奋的不得了。然后我跟他说上午答题不好，没什么好解释的。谁知大哥跟我说，我一看就太紧张。没有发挥出来。ft。。。也许？

      大哥跟我约定让我参加lunch interview。希望我好好准备，放松自己，进入msra。

      表达谢意。大哥送我出门。并再次嘱咐我要自信。

      进电梯，一到家就收到大哥来信，告之我准备好面试就告诉他。

      天底下有这么好的人。真是让我不敢相信。废话很多，努力准备，msra，我来了。

《MIT人工智能实验室：如何做研究？》，转载至此，共勉之。

【摘要 本文的主旨是解释如何做研究。我们提供的这些建议，对做研究本身（阅读、写作和程序设计），理解研究过程以及开始热爱研究（方法论、选题、选导师和情感因素），都是极具价值的。

备注 人工智能实验室的Working Papers用于内部交流，包含的信息由于过于初步或者过于详细而无法发表。不像正式论文那样，会列出所有的参考文献。】

 昨天约好今天电话过来，偶等的心急，打给ms，被接线mm训斥，马上就接到电面电话。
    我以为是某个认识到大哥，就问是不是，然后说不是：（
    首先问项目经历，一个一个问，主要问创新点，算法实现过程，自己的工作职责。问的不算特别细致，中间我回答一个大时候，面官说让我简短介绍自己的东西（
我的表达太差？），于是简单介绍。
    中间问了一个实习时期写的测试工具的事情。对方说这是个小工具，不是平台。
被训斥。：（看来确实要实事求是。
    然后问了问自己简历上面的东西，com。atl等。
    最后面官说等通知。电面结束。