Skip to content

我为何中止DP系列文章的写作

前几天,在写作《动态规划中的线形模型》时,写到了讨论LIS问题的章节。顿悟一般,理解了LIS的数学本质。原来LIS问题就是这样一个问题:

一个有限集S,其中定义了两个全序关系<1和<2,用这两个全序关系定义一个偏序关系<:x<y当且仅当x<1y且x<2y。求偏序集(S,<)的最长链。

没错,这就是LIS问题的数学本质。知道了这个以后就可得出很多关于LIS及相关问题的结论。由于本篇文章并非教程,对这些结论不详加解释。

  1. 在原本的LIS问题中,第一个全序关系是“序列中x在y的前面”,第二个全序关系是“x小于y”。如果我们按照第二个全序关系对序列进行排序,可以得到原问题的一个对偶问题。即:对原序列进行排序,再把排序后序列的每个元素换成在原序列中的下标。两个对偶问题的答案是一样的,也就是说原序列中的LIS长度,肯定等于得到的新序列中的LIS长度。而对偶问题有一个非常好的性质:它的序列中的所有元素都在1..N中取值。这就带来了很多很多种O(NlogN)算法的思路,比如说可以用virtual binary tree。
  2. 既然LIS的本质是要求“偏序集的最长链”,那么就可以应用组合数学中有关的定理。例如熟悉的定理:最长链的长度等于反链的划分数;以及其对偶定 理:最长反链的长度等于链的划分数。所以LIS中那个让很多人不理解的结论就昭然若揭了。为何上升子序列的覆盖数等于最长不上升子序列的长度?因为上升子序列是链,不上升子序列是反链。
  3. 所有可以转化为LIS问题求解的OI题目一定满足LIS的数学本质。也就是说,需要用LIS的算法解决的题目,一定能找到两个全序关系,和由它们定义的偏序关系。例如那道经典的给定一些矩形造一座塔的问题,为什么按照矩形的长排序然后求宽的LIS。原因很简单,两个全序关系就是由矩形的长和宽定义的,而LIS就是要先按照其中一个全序关系排序以得到序列。
  4. 可以对LIS的数学本质进行扩展,也就是对LIS问题进行扩展,例如<1和<2不一定都得是全序关系,可以有一个是偏序关系,这个偏序关系也可能是另外两个全序关系定义的,等等……这样又可以解决更多题目,例如“三维导弹拦截”。
  5. ……

LIS问题其实只是线型动态规划中非常简单的一个模型,通过思考它的数学本质,竟然就可以得到如此多的结论,由这些结论就可以编制出无穷无尽的OI题……这让我欣喜异常。

然而,LIS的数学本质中涉及到的离散数学中的概念:全序、偏序、链,这都是我还非常非常陌生的概念。连这些概念都不敢说懂,我怎么敢说我懂了LIS问题?我怎么敢写出一份涉及它的教程?

是的,通过深入的思考,我充分理解到:动态规划的每一个模型,都可能有着深不见底的数学本质;不掌握足够多的数学工具,就不可能从本质上把握动态规划。

可我掌握的数学太少了,特别是用处特别大的离散数学,只是浅尝辄止。我深感现在的能力无法写出一份好的动态规划总结。更让我恐慌的是:竟然有那么多人,会那么仔细地,甚至带着崇拜的眼光,阅读我的总结。

由于数学能力不足,也为了避免误人子弟,我已经中止了DP系列文章的写作。今天发布的《背包问题九讲v1.1》是今年的最后一次发布。

我对期待着《动态规划中的线形模型》的所有人表示无比愧疚的歉意。你们高看了我,我目前的能力不足以从本质上把握诸多线形模型,更不足以写出好的总结。对不起,让你们失望了。

但是,要注意我说的是“中止”而非“终止”。那个雄心勃勃的计划没有夭折,只是暂时停顿了。在将来的某一天,在我自认为数学能力足够的时候,也许是在我加入某个ACM-ICPC队伍的时候,我会继续未完成的计划。动态规划的领域是如此迷人,哪怕需要再长的时间,我会将这个写作计划完成。

最后,再次向所有失望的人表示真诚的歉意。

5 Comments

  1. DD 的自省力让我折服了

    Thursday, November 15, 2007 at 12:48 | Permalink
  2. ZHL wrote:

    dd在学术领域仍然是渺小的,我们在dd面前更是渺小的。佩服,佩服。不仅是知识,还有人品。

    Thursday, November 15, 2007 at 14:13 | Permalink
  3. :) wrote:

    顶一下大牛~
    dp的确很多问题有深刻的数学本质…
    像状态压缩dp和棋盘多项式等~
    大家都会在不同时期写出不同水平的文章.
    写东西也算是自己的总结吧~
    有可能当您数学变强后写了总结.
    然后又发现更本质的东西…
    期待大牛变强后的文章.

    Thursday, November 15, 2007 at 14:17 | Permalink
  4. ce13169 wrote:

    建议您恢复写作
    理由如下:
    虽然您自认为自己在某些方面有欠缺,但是请注意您写这类文章的意义:帮助那些水平不够高的人,使他们有所提高.
    虽然有写东西您写了但是您也没有搞完全懂,但是如果您不写,那些水平不够高的人就更加难自己懂了.
    从您的文章在网上的反响来看,很多人都一褒扬有嘉的.虽然可能有的人只是跟风ORZ之类的,但是更多的人应该都是从您的文章中确确实实学到了东西,而这正是符合您写作这类文章的本意的.
    因此,建议您继续.

    Thursday, November 15, 2007 at 18:58 | Permalink
  5. Canvas wrote:

    呃,大牛你可以分部写啊,比如分成基础篇和提高篇。。
    顺便orz大牛。。。

    Friday, November 20, 2009 at 20:20 | Permalink

3 Trackbacks/Pingbacks

  1. [...] 刚刚休息了下眼睛回来。感觉BOI的题比COCI要难… 赛前心里想,这几天也AC了不少暴力的题目了,这个,比赛的时候应该不会太被虐吧… 实际的情况是第一题感觉是要离散化以后再动态规划,可是准备写的时候发现数据并不局限在第一象限… 结果接下来就混乱掉了… 第一题最后放弃。第二题是乐高积木的计数题,嗯,就是给定正视图和侧视图要求计算总数,我的思路是先预处理出一层的情况,然后再反复通过它计算出答案,可是这个算法不仅受限于内存,而且很难处理“漂浮”的情况,最后的想硬写暴搜可是仍然感到很难,(这应该用搜索辅助组合计数的题… 哎… 心里想题设中的问题以前还思考过…) 所以最后也只是交了第三题… (第三题也是以前读过这篇才会做的…) [...]

  2. [...] 四年前,我曾经有过一个写一系列DP相关文章的宏伟计划,但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了。 [...]

  3. [...] 四年前,我曾经有过一个写一系列DP相关文章的宏伟计划,但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了。 [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*