Matrix67: My Blog

正多边形的滚动与旋轮线下方的面积

Matrix67 — Fri, 06 Apr 2012 19:44:08 +0800

想像一个圆盘在地面上滚动一周，那么圆周上一点所形成的轨迹就叫做旋轮线（或者摆线）。旋轮线下方的面积是多少，这是一个非常有趣的问题。据说， Galileo 曾经用一种非常流氓的方法，推测出了旋轮线下方的面积。他在金属板上切出一块圆片，再在金属板边缘剪下这个圆形所对应的旋轮线，把它们拿到秤上一称，发现后者的重量正好是前者的三倍。于是，他推测，半径为 r 的滚轮所产生的旋轮线，其下方的面积就是 3πr² 。

不过，今天我第一次知道，这个结论对于正多边形是同样成立的。

考虑一个正三角形在平地上滚动一周，则原来的顶点 A₁ 将会先后转到 A₂ 和 A₃ 的位置。容易看出， A₁ 、 A₂ 、 A₃ 的连线与地面构成的面积正好是正三角形的三倍。

类似地，让正方形在平地上滚动一周，则原来的顶点 A₁ 将会先后转到 A₂ 、 A₃ 和 A₄ ，这四个点的连线下方的面积也正好是这个正方形的三倍。

另外两个比较简单的情形则是正六边形和正八边形，大家也可以自行验证一下。看来，这里面一定有一个深刻的原因，能够解释为何结论对于任意正 n 边形都成立。

让我们先来看另一个看似无关，但仍然非常神奇的结论：假设正多边形的外接圆半径为 r ，从外接圆上任意一点出发，依次与该多边形的 n 个顶点相连，则这 n 条连线的长度的平方和等于 2n · r² 。我们来证明这个结论。

把正多边形的中心放在平面直角坐标系的原点处，把外接圆上的那个点记作 (u, v) ，再假设多边形 n 个顶点的位置分别是 (a₁, b₁), (a₂, b₂), …, (a_n, b_n) ，则这 n 条连线的平方和为

         Σ((u - a_i)² + (v - b_i)²)
      = Σ(u - a_i)² + Σ(v - b_i)²
      = n · u² - 2u · Σa_i + Σa_i² + n · v² - 2v · Σb_i + Σb_i²
      = n · (u² + v²) - 2u · Σa_i - 2v · Σb_i + Σ(a_i² + b_i²)

显然， u² + v² 以及所有的 a_i² + b_i² 都等于 r² ，因此上面的式子也就等于了 2n · r² - 2u · Σa_i - 2v · Σb_i 。接下来，我们只需要说明 Σa_i 和 Σb_i 都为 0 即可。其实这是显然的：因为正多边形 n 个顶点的重心在中心 (0, 0) 处，说明这 n 个顶点的所有横坐标之和就是 0 ，所有纵坐标之和也为 0 。

特别地，把外接圆上的那个点取成正多边形的顶点，于是我们得到，从正 n 边形的某个顶点出发，连接其他 n - 1 个顶点，如果把这 n - 1 条连线分别记作 d₁, d₂, …, d_n-1 ，则有：

d₁² + d₂² + … + d_n-1² = 2n · r²

我们利用这个结论来说明，连接正多边形滚动一周后某个顶点依次所达的位置，所得折线段下方的面积恰为该正多边形的三倍。

现在，假设正多边形的外接圆半径为 r ，把这个正多边形的面积记作 A 。如图，折线段下方的面积可以被分成 n - 2 个蓝色三角形和 n - 1 个红色三角形（图中所示的是 n = 9 的情况）。这 n - 2 个蓝色三角形恰好能拼成一个原多边形，它们的面积和为 A 。下面，我们来看一下剩下的 n - 1 个红色三角形都是怎么形成的。正多边形一共转动了 n - 1 次，每一次都是绕着一个新的顶点在转动，这 n - 1 个红色三角形就是在这 n - 1 次转动中产生的。容易看出，每个红色三角形都是等腰三角形，它们的腰长分别为 d₁, d₂, …, d_n-1。同时，由于 n 次转动后正多边形将回到原来的方向，因此每一次正多边形都转过了 (360/n)° 。因此，每个红色等腰三角形的顶角也都是 (360/n)° 。于是你会发现，第 i 个红色三角形的形状与正多边形的其中 1/n 块完全一样，只不过有一个 d_i : r 的相似比！注意到面积比是相似比的平方，于是所有红色三角形的面积之和为：

         (A/n) · d₁² / r² + (A/n) · d₂² / r² + … + (A/n) · d_n-1² / r²
      = (A/n) · (d₁² + d₂² + … + d_n-1²) / r²
      = (A/n) · 2n · r² / r²
      = 2A

因此，折线下方的面积是 3A ，即原正多边形面积的三倍。当 n 趋于无穷的时候，我们便又回到了 Galileo 所发现的那个结论。

Turing机、人工智能以及我们的世界

Matrix67 — Tue, 06 Mar 2012 12:33:11 +0800

昨天终于读完了《The Annotated Turing》一书，第一次完整地阅读了 Turing 最经典的那篇论文，理解了 Turing 机提出的动机和由此带来的一系列结论。不过，这本书的最大价值，则是让我开始重新认识和思考这个世界。在这里，我想把我以前积累的哲学观点和最近一些新的思考记下来，与大家一同分享。《The Annotated Turing》一书中的一些学术内容，留待以后几篇日志与大家分享。今年是 Alan Turing 诞辰 100 周年，图灵公司将推出这本书的中译本《图灵的秘密》，现在正在紧张的编辑排版中，不久之后就能和大家见面。

1928 年， David Hilbert 提出了一个著名的问题：是否存在一系列有限的步骤，它能判定任意一个给定的数学命题的真假？这个问题就叫做 Entscheidungsproblem ，德语“判定性问题”的意思。大家普遍认为，这样的一套步骤是不存在的，也就是说我们没有一种判断一个数学命题是否为真的通用方法。为了证明这一点，真正的难题是将问题形式化：什么叫做“一系列有限的步骤”？当然，现在大家知道，这里所说的“有限的步骤”指的就是由条件语句、循环语句等元素搭建而成的一个机械过程，也就是我们常说的“算法”。不过，在没有计算机的时代，人们只能模模糊糊地体会“一个机械过程”的意思。 1936 年，Alan Turing 在著名的论文《On computable numbers, with an application to the Entscheidungsproblem》中提出了一种假想的机器，第一次给了“机械过程”一个确凿的含义。

    Turing 提出的机器非常简单。假设有一张无穷向右延伸的纸条，从左至右分成一个一个的小格子。每一个小格子里都可以填写一个字符（通常是单个数字或者字母）。纸条下方有一个用来标识“当前格子”的箭头，在机器运行过程中，箭头的位置会不断移动，颜色也会不断变化。不妨假设初始时所有格子都是空白，箭头的颜色是红色，并且指向左起第一个格子。为了让机器实现不同的功能，我们需要给它制定一大堆指令。每条指令都是由五个参数构成，格式非常单一，只能形如“如果当前箭头是红色，箭头所在格子写的是字符 A ，则把这个格子里的字符改为 B ，箭头变为绿色并且向右移动一格”，其中最后箭头的移动只能是“左移一格”、“右移一格”、“不动”中的一个。
    精心设计不同的指令集合，我们就能得到功能不同的 Turing 机。你可以设计一个生成自然数序列的 Turing 机，或者是计算根号 2 的 Turing 机，甚至是打印圆周率的 Turing 机。 Turing 本人甚至在论文中实现了这么一种特殊的 Turing 机叫做通用 Turing 机，它可以模拟别的 Turing 机的运行。具体地说，如果把任意一个 Turing 机的指令集用 Turing 自己提出的一种规范方式编码并预存在纸条上，那么通用 Turing 机就能够根据纸条上已有的信息，在纸条的空白处模拟那台 Turing 机的运作，输出那台 Turing 机应该输出的东西。
    但是， Turing 机并不是无所不能的。 Turing 证明了一个看似有些惊人的事实：不存在这样的一个 Turing 机，它能读取任意一个 Turing 机的指令集，并判断该 Turing 机是否将会在纸条上打印出至少一个 0 。注意，简单地用通用 Turing 机做模拟并不是一个可行的方案，因为模拟到现在还没有打出 0 ，不意味着今后也就永远不会打出 0 。这个定理有一个更深刻的含义，即没有一种通用的方法可以预测一台 Turing 机无穷远后的将来（后人把这个结论简化为了著名的停机问题）。正如《The Annotated Turing》封底上的一段文字所说：在没有计算机的时代， Turing 不但探索了计算机能做的事，还指出了计算机永远不能做到的事。
    在论文的最后一章， Turing 给出了一种 Turing 机指令集和一阶逻辑表达式的转换规则，使得这个 Turing 机将会打出 0 来，当且仅当对应的一阶逻辑表达式为真。然而，我们没有一种判断 Turing 机是否会输出 0 的算法，因此我们也就没有一种判断数学命题是否为真的通用办法。于是， Entscheidungsproblem 有了一个完美的解答。

有趣的是，Turing 机本身的提出比 Entscheidungsproblem 的解决意义更大。计算机诞生以后，出现了五花八门的高级编程语言，一个比一个帅气，但它们的表达能力实际上都没有超过 Turing 机。事实上，再庞大的流程图，再复杂的数学关系，再怪异的语法规则，最终都可以用 Turing 机来描述。 Turing 机似乎是一个终极工具，它似乎能够表达一切形式的计算方法，可以描述一切事物背后的规律。在同一时代，美国数学家 Alonzo Church 创立了 λ 算子（λ-calculus），用数学的方法去阐释“机械过程”的含义。后来人们发现， Turing 机和 λ 算子是等价的，它们具有相同的表达能力，是描述“可计算性”的两种不同的模型。 Turing 机和 λ 算子真的能够描述所有直观意义上的“可计算数”、“可计算数列”、“可计算函数”吗？有没有什么东西超出了它们的表达能力？这个深刻的哲学问题就叫做 Church–Turing thesis 。当然，我们没法用形式化的方法对其进行论证，不过大家普遍认为， Turing 机和 λ 算子确实已经具有描述世间一切复杂关系的能力了。人们曾经提出过一些 hypercomputer ，即超出 Turing 机范围的假想机器，比如能在有限时间里运行无穷多步的机器，能真正处理实数的机器，等等。不过这在理论上都是不可能实现的。

事实上， Turing 在他的论文中就已经指出，人的思维也没有跳出 Turing 机的范围。对此， Turing 有一段非常漂亮的论证：人在思考过程中，总能在任意时刻停下来，把当前进度记录在一张纸上，然后彻底走开并把它完全抛之脑后，过一会儿再回来，并完全凭借纸上的内容拾起记忆，读取进度，继续演算。也就是说，人的每一帧思维，都可以完全由上一帧思维推过来，不依赖于历史的思维过程。而 Turing 机所做的，也就是把人的思维步骤拆分到最细罢了。

没错，这意味着，或许一个人的语言、计算甚至学习能力，完全等价于一个 Turing 机，只不过这个 Turing 机的指令集可能异常庞大。1950 年， Turing 的另2一篇经典论文《Computing Machinery and Intelligence》中正式把人和机器放到了相同的高度：让一个真2人 C 先后与一台计算机 A 和另一个真人 B 进行聊天，但事先不告诉他 A 和 B 哪个是机器哪个是人；如果 C 无法通过聊天内容分辨出谁是机器谁是人，我们就认为计算机 A 具有了所谓的人工智能。这就是 Turing 测试。

计算机拥有智能？这岂不意味着计算机也能学习，也能思考，也拥有喜怒哀乐？人类似乎瞬间失去了不少优越感，于是不少科学家都旗帜鲜明地提出了反对意见。其中最为经典的恐怕要数美国哲学家 John Searle 在 1980 年提出的“中文屋子”思想实验了。把一个不懂汉语的老外关在一个屋子里，屋子里放有足够多的草稿纸和铅笔，以及一本汉语机器聊天程序的源代码。屋子外面则坐着一个地地道道的中国人。屋里屋外只能通过纸条传递信息。老外可以用人工模拟程序运行的方式，与屋外的人进行文字聊天，但这能说明老外就懂中文了吗？显然不能。每次讲到中文屋子时，我往往会换一种更具戏剧效果的说法。一群微软研究员在小屋子里研究代码研究了半天，最后某人指着草稿纸一角的某个数字一拍大腿说，哦，原来屋外的人传进来的是一段笑话！于是，研究员们派一个代表到屋子外面捧腹大笑——但是，显然这个研究员是在装笑，他完全不懂笑点在哪儿。这个例子非常有力地说明了，机器虽然能通过 Turing 测试，但它并不具有真正的智能。

    当然，有反方必有正方。另一派观点则认为，计算机拥有智能是一件理所当然的事。这涉及到一个更为根本的问题：究竟什么是智能？
    记得我曾经看过一本科幻小说，书名不记得了，情节内容也完全不记得了，只记得当我看完小说第一页时的那种震撼。在小说的开头，作者发问，什么是自我意识？作者继续写到，草履虫、蚯蚓之类的小动物，通常是谈不上自我意识的。猫猫狗狗之类的动物，或许会有一些自我意识吧。至于人呢，其实我只敢保证我自己有自我意识，其他人有没有自我意识我就不知道了。看到这里我被吓得毛骨悚然：完全有可能整个世界就只有我一个人有自我意识，其他所有人都是装出一副有意识的样子的无生命物！
    有一次做汉语语义识别的演讲时，讲到利用语义角色模型结合内置的知识库，计算机就能区别出“我吃完了”和“苹果吃完了”的不同，可以推出“孩子吃完了”多半指的是什么。一位听众举手说，难道计算机真的“理解”句子的意思了？我的回答是，没有冒犯的意思，你认为你能理解一个汉语句子的意思对吧，那你怎样证明这一点呢？听众朋友立即明白了。你怎样证明，你真的懂了某一句话？你或许会说，我能对其进行扩句缩句啊，我能换一种句型表达同样的意思啊，我能顺着这句话讲下去，讲出与这句话有关的故事、笑话或者典故，我甚至还能在纸上画出句子里的场景来呢！那好，现在某台电脑也能做到这样的事情了，怎么办？
    这就是所谓的“功能主义”：只要它的输入输出表现得和人一样，不管它是什么，不管它是怎么工作的，哪怕它只是一块石头，我们也认为它是有智能的。永远不要觉得规则化、机械化的东西就没有智能。你觉得你能一拍脑袋想一个随机数，并且嘲笑计算机永远无法生成真正的随机数。但是，你凭什么认为你想的数真的就是随机的呢？事实上，你想的数究竟是什么，这也是由你的大脑机器一步一步产生的。你的大脑逃不出 Turing 机。

事实上，整个世界也逃不出 Turing 机的范围。 Newton 系统地总结了物体运动规律后，人类豁然开朗，原来世界万事万物都是由“力”来支配的，扔出一个东西后，这个东西将以怎样的路线做怎样的运动，会撞击到哪些其他的物体，它们分别又会受到怎样的影响，这都是可以算出来的。这便是所谓的机械唯物主义：我们的世界是一个简单的、确定的、线性的、无生的世界。 1814 年，法国数学家 Laplace 给出一个更加漂亮的诠释：如果有一个妖精，它知道宇宙某个时刻所有基本粒子的位置和动量，那么它就能够根据物理规律，计算出今后每一时刻整个宇宙的状态，从而预测未来。刘慈欣在科幻小说《镜子》中更加极端地把初始状态取到宇宙大爆炸的时刻，因为宇宙诞生之初的状态极其简单，调整到正确的参数就可以生成我们所处的这个宇宙。这就是所谓的决定论。
我特别相信这些说法。我的拖延症有一个非常怪异的缘由，那就是我会告诉自己，截止的那一天总会到来的，这堆破事儿总会被我做完的。遇上纠结的问题，我不会做过多的思考，而会让一切顺其自然。其实，结果已经是确定的了，我真正需要做的不过是亲自把这个过程经历一遍。就仿佛我没有自由意志了一样。

不过，现代物理学的观念，尤其是量子理论的诞生，开始质疑上帝究竟会不会掷骰子了。然而，上帝会不会掷骰子，对于我们来说其实并不重要。 Turing 的结论告诉我们，即使未来是注定的，我们也没有一种算法去预测它，除非模拟它运行一遍。但是，要想模拟这个宇宙的运行，需要的计算量必然超出了这个宇宙自身的所有资源。运行这个宇宙的唯一方式，就是运行这个宇宙本身。 Seth Lloyd 在《Programming the Universe》里说到，“我们体会到的自由意志很像 Turing 的停机问题：一旦把某个想法付诸实践，我们完全不知道它会通向一个怎样的结局，除非我们亲身经历这一切，目睹结局的到来。”

未来很可能是既定的，但是谁也不知道未来究竟是什么样。每个人的将来依旧充满了未知数，依旧充满了不确定性。所以，努力吧，未来仍然是属于你的。

趣题：填写两个声母互相颠倒的词

Matrix67 — Thu, 01 Mar 2012 10:26:26 +0800

英语当中有一种笑话类型。第一次看到的是：

- What's the difference between a girl in church and a girl in the bathtub?
- One has hope in her soul, one has soap in her hole.

把我给笑坏了。在说这种笑话的时候，只说一半的效果往往更好。又比如：

- What's the difference between a midget magician and a female jogger?
- One is a cunning runt...

我想，汉语当中应该也有不少这样的词语对吧。于是，我找来了一份汉语常用词拼音的数据，从中搜索出了一大堆声母颠倒的词语对。喜欢给别人出谜题的我自然没有放过这一机会。请你在下面每句话的两个空格中分别填入两个声母颠倒的双字词，使得整个句子通顺完整。每个小题都有至少一个由常用词构成的解。比如，第一小题的答案就是“宝地”和“倒闭”。

      1. 虽然公司位于一块 _____ ，但最后还是 _____ 了。
      2. 魔术师熟练地从 _____ 里变出了一只 _____ 。
      3. 他知道好几种 _____ 翻新机的 _____ 方法。
      4. 为了磨炼意志，他常常赤身睡在 _____ 铁钉的 _____ 上。
      5. 这种机械化的 _____ 严重 _____ 了学生的创造思维。
      6. 《阿凡达》电影票一票难求，排队买票的 _____ _____ 超过了春运。
      7. 使用过期的 _____ 会 _____ 检测结果有误差。
      8. 前线发来 _____ 称他们已经发现了敌方 _____ 部队。
      9. _____ 的领导者不应该与员工之间有任何 _____ 。
      10. 各个主要 _____ 都有专职护林防火人员 _____ 。
      11. _____ 功能衰退不影响学生正常 _____ 。
      12. 目前，各地塑料 _____ 市场现状一片 _____ 。
      13. 服用戒烟 _____ 药物最好听从医师的 _____ 。
      14. 人体内脏 _____ 业正在美国悄悄 _____ 。
      15. 与 _____ 关系不融洽终会让你逐渐 _____ 对工作的热情。
      16. “民工潮” _____ 的人口 _____ 将不断推进户籍制度的改革。
      17. 表盘上的 6 点钟位置附有非常 ______ 的 _____ 显示。
      18. 她那半月形的银质发箍卡在金色的头发上，远远看去就像是 _____ 时期的 _____ 。
      19. _____ 设计的一个重要应用就是 _____ 设计。
      20. 人们在工地里挖出了那次 _____ 中留下来的一颗 _____ 。

    答案：
      1. 虽然公司位于一块 _____ ，但最后还是 _____ 了。（宝地，倒闭）
      2. 魔术师熟练地从 _____ 里变出了一只 _____ 。（台布，白兔）
      3. 他知道好几种 _____ 翻新机的 _____ 方法。（鉴别，便捷）
      4. 为了磨炼意志，他常常赤身睡在 _____ 铁钉的 _____ 上。（布满，木板）
      5. 这种机械化的 _____ 严重 _____ 了学生的创造思维。（复述，束缚）
      6. 《阿凡达》电影票一票难求，排队买票的 _____ _____ 超过了春运。（阵势，甚至）
      7. 使用过期的 _____ 会 _____ 检测结果有误差。（试纸，致使）
      8. 前线发来 _____ 称他们已经发现了敌方 _____ 部队。（密电，地面）
      9. _____ 的领导者不应该与员工之间有任何 _____ 。（合格，隔阂）
      10. 各个主要 _____ 都有专职护林防火人员 _____ 。（山口，看守）
      11. _____ 功能衰退不影响学生正常 _____ 。（嗅觉，就学）
      12. 目前，各地塑料 _____ 市场现状一片 _____ 。（板材，惨白）
      13. 服用戒烟 _____ 药物最好听从医师的 _____ 。（辅助，嘱咐）
      14. 人体内脏 _____ 业正在美国悄悄 _____ 。（清洗，兴起）
      15. 与 _____ 关系不融洽终会让你逐渐 _____ 对工作的热情。（上司，丧失）
      16. “民工潮” _____ 的人口 _____ 将不断推进户籍制度的改革。（掀起，迁徙）
      17. 表盘上的 6 点钟位置附有非常 ______ 的 _____ 显示。（清晰，星期）
      18. 她那半月形的银质发箍卡在金色的头发上，远远看去就像是 _____ 时期的 _____ 。（中古，公主）
      19. _____ 设计的一个重要应用就是 _____ 设计。（平面，名片）
      20. 人们在工地里挖出了那次 _____ 中留下来的一颗 _____ 。（大战，炸弹）

2月14日：送给你的礼物

Matrix67 — Tue, 14 Feb 2012 00:01:16 +0800

经典证明：星际争霸是NP-hard的

Matrix67 — Sat, 28 Jan 2012 03:07:21 +0800

今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

假设初始时有 A 、 B 两位玩家，他们分别位于两个孤岛上。玩家 B 有非常多的地面兵力，但没有空中单位，并且已有资源为 0 ，而且还没有任何经济来源。他只能坐等玩家 A 来攻打他。玩家 A 一开始则完全没有兵力，但他有不少可以生产作战单位的建筑，也有一定的经济来源，理论上有获胜的希望。地图上还有第三个孤岛，孤岛周边放满 B 的对空防御，玩家 A 即使派遣空中部队也无法进入该孤岛。

初始时，玩家 A 的资源刚好够造一个农民，玩家 A 还需要收集额外的 x 个单位的资源才足以消灭玩家 B 。但是，玩家 A 的所有可采集资源都在第三个孤岛上。这个孤岛上有 n 个采矿点，每个采矿点都配备有一个基地，以及 x/n 个单位的矿石资源。每个采矿点也都还预先配备了一个农民，只不过这个农民被矿石围在里面出不来了。采矿点与采矿点之间靠一些小路连接，每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，但是两个农民走过去恰好能活一个。

游戏开始后，玩家 A 唯一获胜的途径便是，在某个采矿点建造一个农民，采完这个采矿点的矿，把被困的农民救出来，然后选择某条小路走到下一个采矿点（途中死掉一个农民），继续采矿并解救农民，以此类推，直到走遍每一个采矿点，采完所有的矿。很容易看到，玩家 A 相当于要解决一个 Hamilton 路的问题（注意，即使平面图的 Hamilton 路问题也是 NP-complete 的）。因此，星际争霸是 NP-hard 的。

Fibonacci数列性质的组合证明

Matrix67 — Fri, 27 Jan 2012 20:44:04 +0800

数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 F_n ，那么有：

F_n+1 · F_n+1 - F_n · F_n+2 = (-1)ⁿ

今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。

Fibonacci 数有很多组合数学上的意义。比如说，用 1 × 1 和 1 × 2 的积木覆盖一个 1 × n 的棋盘，总的方案数恰好是 F_n+1 。下图显示的就是 n 较小时的一些实例：

这个规律背后的原因其实很简单：给出一个长度为 n 的棋盘后，它的覆盖方案可以分成两类，最后边放的是一个 1 × 1 的积木，或者最后边放的是一个 1 × 2 的积木。前一类情况下的方案数也就完全取决于前 n - 1 个格子的覆盖方案数，后一类情况下的方案数则等于前 n - 2 个格子的覆盖方案数。因此，如果用 f(n) 来表示 1 × n 棋盘的覆盖方案数，那么正好就有 f(n) = f(n - 1) + f(n - 2) 。另外，由于 f(1) = 1 ， f(2) = 2 ，因而接下来的数 f(3), f(4), f(5), … 也就恰好构成了 Fibonacci 数列。

既然这样，那么用积木覆盖两个独立的 1 × n 棋盘，总方案数就是 F_n+1 · F_n+1 。我们有意把这两个独立的棋盘像左图那样摆放。类似地，用积木覆盖一个 1 × (n+1) 棋盘加上另一个 1 × (n-1) 棋盘的总方案数则为 F_n · F_n+2 ，我们把这两个棋盘放成右图所示的样子。左图的覆盖方案和右图的覆盖方案之间有一种非常巧妙的一一对应关系。

对于左图中的任意一种覆盖方案，我们找出上下两块棋盘中所有位置重合的“公共分割线”，选出最右边的那条公共分割线，然后交换此分割线右侧的部分。这样，左图棋盘的每个覆盖方案就能变成右图棋盘的一个覆盖方案。根据同样的方法，右图棋盘的每个覆盖方案也能变回左图棋盘的覆盖方案，这就说明了 F_n+1 · F_n+1 和 F_n · F_n+2 是相当的。

等等，那为什么当 n 为偶数时， F_n+1 · F_n+1 比 F_n · F_n+2 要大 1 ，而 n 为奇数时， F_n+1 · F_n+1 会比 F_n · F_n+2 小 1 呢？神就神在这里。这是因为，刚才所说的一一对应关系并不是真的完全一一对应的。当 n 为偶数时，左图棋盘有一例极其特殊的覆盖方案无法对应到右图的棋盘——因为这种方案中根本没有公共分割线。当 n 为奇数时，左图的棋盘就不再有如此特殊的覆盖方案了，但右图棋盘中却又多出了一例没有公共分割线的情况。这就证明了 F_n+1 · F_n+1 - F_n · F_n+2 = (-1)ⁿ 。

12个经典的行程问题

Matrix67 — Sat, 21 Jan 2012 23:54:53 +0800

无论是小学奥数，还是公务员考试，还是公司的笔试面试题，似乎都少不了行程问题——题目门槛低，人人都能看懂；但思路奇巧，的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中，我收集到很多简单有趣而又颇具启发性的行程问题，在这里整理成一篇文章，和大家一同分享。这些题目都已经非常经典了，绝大多数可能大家都见过；希望这里能有至少一个你没见过的题目，也欢迎大家来信提供更多类似的问题。

让我们先从一些最经典最经典的问题说起吧。选中空白部分显示答案。

甲、乙两人分别从相距 100 米的 A 、B 两地出发，相向而行，其中甲的速度是 2 米每秒，乙的速度是 3 米每秒。一只狗从 A 地出发，先以 6 米每秒的速度奔向乙，碰到乙后再掉头冲向甲，碰到甲之后再跑向乙，如此反复，直到甲、乙两人相遇。问在此过程中狗一共跑了多少米？

这可以说是最经典的行程问题了。不用分析小狗具体跑过哪些路程，只需要注意到甲、乙两人从出发到相遇需要 20 秒，在这 20 秒的时间里小狗一直在跑，因此它跑过的路程就是 120 米。
说到这个经典问题，故事可就多了。下面引用某个经典的数学家八卦帖子： John von Neumann 曾被问起一个中国小学生都很熟的问题：两个人相向而行，中间一只狗跑来跑去，问两个人相遇后狗走了多少路。诀窍无非是先求出相遇的时间再乘以狗的速度。 Neumann 当然瞬间给出了答案。提问的人失望地说你以前一定听说过这个诀窍吧。 Neumann 惊讶道：“什么诀窍？我就是把狗每次跑的都算出来，然后计算无穷级数⋯⋯”

某人上午八点从山脚出发，沿山路步行上山，晚上八点到达山顶。不过，他并不是匀速前进的，有时慢，有时快，有时甚至会停下来。第二天，他早晨八点从山顶出发，沿着原路下山，途中也是有时快有时慢，最终在晚上八点到达山脚。试着说明：此人一定在这两天的某个相同的时刻经过了山路上的同一个点。

这个题目也是经典中的经典了。把这个人两天的行程重叠到一天去，换句话说想像有一个人从山脚走到了山顶，同一天还有另一个人从山顶走到了山脚。这两个人一定会在途中的某个地点相遇。这就说明了，这个人在两天的同一时刻都经过了这里。

甲从 A 地前往 B 地，乙从 B 地前往 A 地，两人同时出发，各自匀速地前进，每个人到达目的地后都立即以原速度返回。两人首次在距离 A 地 700 米处相遇，后来又在距离 B 地 400 米处相遇。求 A 、 B 两地间的距离。

答案： 1700 米。第一次相遇时，甲、乙共同走完一个 AB 的距离；第二次相遇时，甲、乙共同走完三个 AB 的距离。可见，从第一次相遇到第二次相遇的过程花了两个从出发到第一次相遇这么多的时间。既然第一次相遇时甲走了 700 米，说明后来甲又走了 1400 米，因此甲一共走了 2100 米。从中减去 400 米，正好就是 A 、 B 之间的距离了。

甲、乙、丙三人百米赛跑，每次都是甲胜乙 10 米，乙胜丙 10 米。则甲胜丙多少米？

答案是 19 米。“乙胜丙 10 米”的意思就是，等乙到了终点处时，丙只到了 90 米处。“甲胜乙 10 米”的意思就是，甲到了终点处时，乙只到了 90 米处，而此时丙应该还在 81 米处。所以甲胜了丙 19 米。

哥哥弟弟百米赛跑，哥哥赢了弟弟 1 米。第二次，哥哥在起跑线处退后 1 米与弟弟比赛，那么谁会获胜？

答案是，哥哥还是获胜了。哥哥跑 100 米需要的时间等于弟弟跑 99 米需要的时间。第二次，哥哥在 -1 米处起跑，弟弟在 0 米处起跑，两人将在第 99 米处追平。在剩下的 1 米里，哥哥超过了弟弟并获得胜利。

如果你上山的速度是 2 米每秒，下山的速度是 6 米每秒（假设上山和下山走的是同一条山路）。那么，你全程的平均速度是多少？

这是小学行程问题中最容易错的题之一，是小孩子们死活也搞不明白的问题。答案不是 4 米每秒，而是 3 米每秒。不妨假设全程是 S 米，那么上山的时间就是 S/2 ，下山的时间就是 S/6 ，往返的总路程为 2S ，往返的总时间为 S/2 + S/6 ，因而全程的平均速度为 2S / (S/2 + S/6) = 3 。
其实，我们很容易看出，如果前一半路程的速度为 a ，后一半路程的速度为 b ，那么总的平均速度应该小于 (a + b) / 2 。这是因为，你会把更多的时间花在速度慢的那一半路程上，从而把平均速度拖慢了。事实上，总的平均速度应该是 a 和 b 的调和平均数，即 2 / (1/a + 1/b) ，很容易证明调和平均数总是小于等于算术平均数的。

接下来的两个问题与流水行船有关。假设顺水时实际船速等于静水中的船速加上水流速度，逆水时实际船速等于静水中的船速减去水流速度。

船在静水中往返 A 、 B 两地和在流水中往返 A 、 B 两地相比，哪种情况下更快？

这是一个经典问题了。答案是，船在静水中更快一些。注意船在顺水中的实际速度与在逆水中的实际速度的平均值就是它的静水速度，但由前一个问题的结论，实际的总平均速度会小于这个平均值。因此，船在流水中往返需要的总时间更久。
考虑一种极端情况可以让问题的答案变得异常显然，颇有一种荒谬的喜剧效果。假设船刚开始在上游。如果水速等于船速的话，它将以原速度的两倍飞速到达折返点。但它永远也回不来了⋯⋯

船在流水中逆水前进，途中一个救生圈不小心掉入水中，一小时后船员才发现并调头追赶。则追上救生圈所需的时间会大于一个小时，还是小于一个小时，还是等于一个小时？

这也是一个经典问题了。中学物理竞赛中曾出现过此题，《编程之美》上也有一个完全相同的问题。答案是等于一个小时。原因很简单：反正船和救生圈都被加上了一个水流的速度，我们就可以直接抛开流水的影响不看了。换句话说，我们若以流水为参照系，一切就都如同没有流水了。我们直接可以想像船在静水当中丢掉了一个救生圈并继续前行一个小时，回去捡救生圈当然也还需要一个小时。
每当有人还是没想通时，我很愿意举这么一个例子。假如有一列匀速疾驰的火车，你在火车车厢里，从车头往车尾方向步行。途中你掉了一个钱包，但继续往前走了一分钟后才发现。显然，你回去捡钱包需要的时间也是一分钟。但是，钱包不是正被火车载着自动地往远方走吗？其实，既然你们都在火车上，自然就可以无视火车的速度了。前面的救生圈问题也是一样的道理。

下面这个问题也很类似：假设人在传送带上的实际行走速度等于人在平地上的行走速度加上一个传送带的速度。

你需要从机场的一号航站楼走到二号航站楼。路途分为两段，一段是平地，一段是自动传送带。假设你的步行速度是一定的，因而在传送带上步行的实际速度就是你在平地上的速度加上传送带的速度。如果在整个过程中，你必须花两秒钟的时间停下来做一件事情（比如蹲下来系鞋带），那么为了更快到达目的地，你应该把这两秒钟的时间花在哪里更好？

这个漂亮的问题出自 Terence Tao 的 Blog （http://terrytao.wordpress.com/2008/12/09/an-airport-inspired-puzzle）。很多人可能会认为，两种方案是一样的吧？然而，真正的答案却是，把这两秒花在传送带上会更快一些。这是因为，传送带能给你提供一些额外的速度，因而你会希望在传送带上停留更久的时间，更充分地利用传送带的好处。因此，如果你必须停下来一会儿的话，你应该在传送带上多停一会儿。

假设你站在甲、乙两地之间的某个位置，想乘坐出租车到乙地去。你看见一辆空车远远地从甲地驶来，而此时整条路上并没有别人与你争抢空车。我们假定车的行驶速度和人的步行速度都是固定不变的，并且车速大于人速。为了更快地到达目的地，你应该迎着车走过去，还是顺着车的方向往前走一点？

    这是我在打车时想到的一个问题。我喜欢在各种人多的场合下提出这个问题，此时大家的观点往往会立即分为鲜明的两派，并且各有各的道理。有人说，由于车速大于人速，我应该尽可能早地上车，充分利用汽车的速度优势，因此应该迎着空车走上去，提前与车相遇嘛。另一派人则说，为了尽早到达目的地，我应该充分利用时间，马不停蹄地赶往目的地。因此，我应该自己先朝目的地走一段路，再让出租车载我走完剩下的路程。
    其实答案出人意料的简单，两种方案花费的时间显然是一样的。只要站在出租车的角度上想一想，问题就变得很显然了：不管人在哪儿上车，出租车反正都要驶完甲地到乙地的全部路程，因此你到达乙地的时间总等于出租车驶完全程的时间，加上途中接人上车可能耽误的时间。从省事儿的角度来讲，站在原地不动是最好的方案！
    我曾经把这个有趣的问题搬上了《新知客》杂志 2010 年第 9 期的趣题专栏（http://www.matrix67.com/blog/archives/3677）。不少人都找到了这个题的一个 bug ：在某些极端情况下，顺着车的方向往前走可能会更好一些，因为你或许会直接走到终点，而此时出租车根本还没追上你！

某工厂每天早晨都派小车按时接总工程师上班。有一天，总工程师为了早些到工厂，比平日提前一小时出发步行去工厂。走了一段时间后，遇到来接他的小车才上车继续前进。进入工厂大门后，他发现只比平时早到 10 分钟。总工程师在路上步行了多长时间才遇到来接他的汽车？设人和汽车都做匀速直线运动。

据说，这是一道初中物理竞赛题（初中物理有“运动”一章）。答案是 55 分钟。首先，让我们站在车的角度去想（正如前一题那样）。车从工厂出发，到半途中就遇上了总工程师并掉头往回走，结果只比原来早到 10 分钟。这说明，它比原来少走了 10 分钟的车程，这也就是从相遇点到总工程师家再到相遇点的路程。这就说明，从相遇点到总工程师家需要 5 分钟车程。
现在，让我们把视角重新放回总工程师那里。让我们假设总工程师遇上了来接他的车并坐上去之后，并没有下令汽车立即掉头，而是让车像平日那样继续开到他家再返回工厂，那么他到工厂的时间应该和原来一样。这说明，他提前出发的那一个小时完全浪费了。这一个小时浪费在哪儿了呢？浪费在了他步行到相遇点的过程，以及乘车又回到家的过程。既然乘车又回到家需要 5 分钟，因此步行的时间就是 55 分钟了。

有一位隐居在深山老林的哲学家。一天，他忘记给家里唯一的时钟上发条了。由于他家里没有电话、电视、网络、收音机等任何能获知时间的设备，因此他彻底不知道现在的时间是多少了。于是，他徒步来到了他朋友家里坐了一会儿，然后又徒步回到自己家中。此时，他便知道了应该怎样重新设定自己的时钟。他是怎么做的？
很多人的第一想法或许是观察日出日落。在此，我们也假设通过太阳位置判断时间是不可靠的。 Update: 不少网友找到了此题的一个 bug 。在此我们假设，时钟是固定在墙上的，或者由于太重，无法直接带走。

传统意义上说，这个问题不算行程问题。不过，在写这篇文章时，这个问题立即跳入我的脑海，我也就把它放进来了。
答案：别忘了，他家里的时钟并不是不走了，只是不准了而已。因此，他可以借助自己家里的时钟，判断他此次出行一共花了多久。假设往返所花时间一样，再结合在朋友那儿看到的正确时间，他便能算出应该怎样调整自己的时钟了。

还有几个不太相关的经典问题这里没有提到，不过你或许会感兴趣：
汽车穿越沙漠问题：http://en.wikipedia.org/wiki/Jeep_problem
木杆上的蚂蚁：http://www.matrix67.com/blog/archives/3791 计算题1

漫话中文自动分词和语义识别（下）：句法结构和语义结构

Matrix67 — Thu, 05 Jan 2012 16:25:55 +0800

这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。

什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是唯一的，但也会产生不同的意思呢？有。比如“门没有锁”，它可能是指的“门没有被锁上”，也有可能是指的“门上根本就没有挂锁”。这个句子虽然只能切分成“门／没有／锁”，但由于“锁”这个词既有可能是动词，也有可能是名词，因而让整句话产生了不同的意思。有没有什么句子，它的分词方案是唯一的，并且每个词的词义也都不再变化，但整个句子仍然有歧义呢？有可能。看看这句话：“咬死了猎人的狗”。这句话有可能指的是“把猎人的狗咬死了”，也有可能指的是“一只咬死了猎人的狗”。这个歧义是怎么产生的呢？仔细体会两种不同的意思后，你会发现，句子中最底层的成分可以以不同的顺序组合起来，歧义由此产生。

在前一篇文章中，我们看到了，利用概率转移的方法，我们可以有效地给一句话分词。事实上，利用相同的模型，我们也能给每一个词标注词性。更好的做法则是，我们直接把同一个词不同词性的用法当作是不同的词，从而把分词和词性标注的工作统一起来。但是，所有这样的工作都是对句子进行从左至右线性的分析，而句子结构实际上比这要复杂多了，它是这些词有顺序有层次地组合在一起的。计算机要想正确地解析一个句子，在分词和标注词性后，接下来该做的就是分析句法结构的层次。

在计算机中，怎样描述一个句子的句法结构呢？ 1957 年， Noam Chomsky 出版了《句法结构》一书，把这种语言的层次化结构用形式化的方式清晰地描述了出来，这也就是所谓的“生成语法”模型。这本书是 20 世纪为数不多的几本真正的著作之一，文字非常简练，思路非常明晰，震撼了包括语言学、计算机理论在内的多个领域。记得 Quora 上曾经有人问 Who are the best minds of the world today ，投出来的答案就是 Noam Chomsky 。

随便取一句很长很复杂的话，比如“汽车被开车的师傅修好了”，我们总能至顶向下地一层层分析出它的结构。这个句子最顶层的结构就是“汽车修好了”。汽车怎么修好了呢？汽车被师傅修好了。汽车被什么样的师傅修好了呢？哦，汽车被开车的师傅修好了。当然，我们还可以无限地扩展下去，继续把句子中的每一个最底层的成分替换成更详细更复杂的描述，就好像小学语文中的扩句练习那样。这就是生成语法的核心思想。

熟悉编译原理的朋友们可能知道“上下文无关文法”。其实，上面提到的扩展规则本质上就是一种上下文无关文法。例如，一个句子可以是“什么怎么样”的形式，我们就把这条规则记作

句子 → 名词性短语＋动词性短语

其中，“名词性短语”指的是一个具有名词功能的成分，它有可能就是一个名词，也有可能还有它自己的内部结构。例如，它有可能是一个形容词性短语加上“的”再加上另一个名词性短语构成的，比如“便宜的汽车”；它还有可能是由“动词性短语＋的＋名词性短语”构成的，比如“抛锚了的汽车”；它甚至可能是由“名词性短语＋的＋名词性短语”构成的，比如“老师的汽车”。我们把名词性短语的生成规则也都记下来：

      名词性短语 → 名词
      名词性短语 → 形容词性短语＋的＋名词性短语
      名词性短语 → 动词性短语＋的＋名词性短语
      名词性短语 → 名词性短语＋的＋名词性短语
      ⋯⋯

类似地，动词性短语也有诸多具体的形式：

      动词性短语 → 动词
      动词性短语 → 动词性短语＋了
      动词性短语 → 介词短语＋动词性短语
      ⋯⋯

上面我们涉及到了介词短语，它也有自己的生成规则：

介词短语 → 介词＋名词性短语
⋯⋯

我们构造句子的任务，也就是从“句子”这个初始结点出发，不断调用规则，产生越来越复杂的句型框架，然后从词库中选择相应词性的单词，填进这个框架里：

而分析句法结构的任务，则是已知一个句子从左到右各词的词性，要反过来求出一棵满足要求的“句法结构树”。这可以用 Earley parser 来实现。

这样看来，句法结构的问题似乎就已经完美的解决了。其实，我们还差得很远。生成语法有两个大问题。首先，句法结构正确的句子不见得都是好句子。 Chomsky 本人给出了一个经典的例子： Colorless green ideas sleep furiously 。形容词加形容词加名词加动词加副词，这是一个完全符合句法要求的序列，但随便拼凑会闹出很多笑话——什么叫做“无色的绿色的想法在狂暴地睡觉”？顺便插播个广告，如果你还挺喜欢这句话的意境的，欢迎去我以前做的 IdeaGenerator 玩玩。不过，如果我们不涉及句子的生成，只关心句子的结构分析，这个缺陷对我们来说影响似乎并不大。生成语法的第二个问题就比较麻烦了：从同一个词性序列出发，可能会构建出不同的句法结构树。比较下面两个例子：

老师被迟到的学生逗乐了
电话被窃听的房间找到了

它们都是“名词＋介词＋动词＋的＋名词＋动词＋了”，但它们的结构并不一样，前者是老师被逗乐了，“迟到”是修饰“学生”的，后者是房间找到了，“电话被窃听”是一起来修饰房间的。但是，纯粹运用前面的模型，我们无法区分出哪句话应该是哪个句法结构树。如何强化句法分析的模型和算法，让计算机构建出一棵正确的句法树，这成了一个大问题。

让我们来看一个更简单的例子吧。同样是“动词＋形容词＋名词”，我们有两种构建句法结构树的方案：

未经过汉语语法训练的朋友可能会问，“点亮蜡烛”和“踢新皮球”的句法结构真的不同吗？我们能证明，这里面真的存在不同。我们造一个句子“踢破皮球”，你会发现对于这个句子来说，两种句法结构都是成立的，于是出现了歧义：把皮球踢破了（结构和“点亮蜡烛”一致），或者是，踢一个破的皮球（结构和“踢新皮球”一致）。

但为什么“点亮蜡烛”只有一种理解方式呢？这是因为我们通常不会把“亮”字直接放在名词前做定语，我们一般不说“一根亮蜡烛”、“一颗亮星星”等等。为什么“踢新皮球”也只有一种理解方式呢？这是因为我们通常不会把“新”直接放在动词后面作补语，不会说“皮球踢新了”，“衣服洗新了”等等。但是“破”既能作定语又能作补语，于是“踢破皮球”就产生了两种不同的意思。如果我们把每个形容词能否作定语，能否作补语都记下来，然后在生成规则中添加限制条件，不就能完美解决这个问题了吗？

基于规则的句法分析器就是这么做的。汉语语言学家们已经列出了所有词的各种特征：

      亮：词性 = 形容词，能作补语 = True ，能作定语 = False ⋯⋯
      新：词性 = 形容词，能作补语 = False ，能作定语 = True ⋯⋯
      ⋯⋯

当然，每个动词也有一大堆属性：

      点：词性 = 动词，能带宾语 = True ，能带补语 = True ⋯⋯
      踢：词性 = 动词，能带宾语 = True ，能带补语 = True ⋯⋯
      污染：词性 = 动词，能带宾语 = True ，能带补语 = False ⋯⋯
      排队：词性 = 动词，能带宾语 = False ，能带补语 = False ⋯⋯
      ⋯⋯

名词也不例外：

      蜡烛：词性 = 名词，能作主语 = True ，能作宾语 = True ，能受数量词修饰 = True ⋯⋯
      皮球：词性 = 名词，能作主语 = True ，能作宾语 = True ，能受数量词修饰 = True ⋯⋯
      ⋯⋯

有人估计会觉得奇怪了：“能作主语”也是一个属性，莫非有些名词不能做主语？哈哈，这样的名词不但有，而且还真不少：剧毒、看头、厉害、正轨、存亡⋯⋯这些词都不放在动词前面。难道有些名词不能做宾语吗？这样的词也有不少：享年、芳龄、心术、浑身、家丑⋯⋯这些词都不放在动词后面。这样说来，存在不受数量词修饰的词也就不奇怪了，事实上上面这些怪异的名词前面基本上都不能加数量词。

另外一个至关重要的就是，这些性质可以“向上传递”。比方说，我们规定，套用规则

名词性短语 → 形容词性短语＋名词性短语

后，整个名词性短语能否作主语、能否作宾语、能否受数量词修饰，这将取决于它的第二个构成成分。通俗地讲就是，如果“皮球”能够作主语，那么“新皮球”也能够作主语。有了“词语知识库”，又确保了这些知识能够在更高层次得到保留，我们就能给语法生成规则添加限制条件了。例如，我们可以规定，套用规则

动词性短语 → 动词性短语＋名词性短语

的前提条件就是，那个动词性短语的“能带宾语”属性为 True ，并且那个名词性短语“能作宾语”的属性为 True 。另外，我们规定

动词性短语 → 动词性短语＋形容词性短语

必须满足动词性短语的“能带补语”属性为 True ，并且形容词性短语“能作补语”属性为 True 。这样便阻止了“踢新皮球”中的“踢”和“新”先结合起来，因为“新”不能作补语。

最后我们规定，套用规则

名词性短语 → 形容词性短语＋名词性短语

时，形容词性短语必须要能作定语。这就避免了“点亮蜡烛”中的“亮”和“蜡烛”先组合起来，因为“亮”通常不作定语。这样，我们便解决了“动词＋形容词＋名词”的结构分析问题。

当然，这只是一个很简单的例子。在这里的问题 6 、 7 、 8 中你可以看到，一条语法生成规则往往有很多限制条件，这些限制条件不光是简单的“功能相符”和“前后一致”，有些复杂的限制条件甚至需要用 IF … THEN … 的方式来描述。你可以在这里看到，汉语中词与词之间还有各种怪异的区别特征，并且哪个词拥有哪些性质纯粹是知识库的问题，完全没有规律可循。一个实用的句法结构分析系统，往往拥有上百种属性标签。北京大学计算语言所编写了《现代汉语语法信息词典》，它里面包含了 579 种属性。我们的理想目标就是，找到汉语中每一种可能会影响句法结构的因素，并据此为词库里的每一个词打上标签；再列出汉语语法中的每一条生成规则，找到每一条生成规则的应用条件，以及应用这条规则之后，整个成分将会以怎样的方式继承哪些子成分的哪些属性，又会在什么样的情况下产生哪些新的属性。按照生成语言学的观点，计算机就应该能正确解析所有的汉语句子了。

那么，这样一来，计算机是否就已经能从句子中获取到理解语义需要的所有信息了呢？答案是否定的。还有这么一些句子，它从分词到词义到结构都没有两可的情况，但整个句子仍然有歧义。考虑这句话“鸡不吃了”，它有两种意思：鸡不吃东西了，或者我们不吃鸡了。但是，这种歧义并不是由分词或者词义或者结构导致的，两种意思所对应的语法结构完全相同，都是“鸡”加上“不吃了”。但为什么歧义仍然产生了呢？这是因为，在句法结构内部，还有更深层次的语义结构，两者并不相同。

汉语就是这么奇怪，位于主语位置上的事物既有可能是动作的发出者，也有可能是动作的承受者。“我吃完了”可以说，“苹果吃完了”也能讲。然而，“鸡”这个东西既能吃，也能被吃，歧义由此产生。

位于宾语位置上的事物也不一定就是动作的承受者，“来客人了”、“住了一个人”都是属于宾语反而是动作发出者的情况。记得某次数理逻辑课上老师感叹，汉语的谓词非常不规范，明明是太阳在晒我，为什么要说成是“我晒太阳”呢？事实上，汉语的动宾搭配范围极其广泛，还有很多更怪异的例子：“写字”是我们真正在写的东西，“写书”是写的结果，“写毛笔”是写的工具，“写楷体”是写的方式，“写地上”是写的场所，“写一只狗”，等等，什么叫做“写一只狗”啊？我们能说“写一只狗”吗？当然可以，这是写的内容嘛，“同学们这周作文写什么啊”，“我写一只狗”。大家可以想像，学中文的老外看了这个会是什么表情。虽然通过句法分析，我们能够判断出句子中的每样东西都和哪个动词相关联，但从语义层面上看这个关联是什么，我们还需要新的模型。

汉语语言学家把事物与动词的语义关系分为了 17 种，叫做 17 种“语义角色”，它们是施事、感事、当事、动力、受事、结果、系事、工具、材料、方式、内容、与事、对象、场所、目标、起点、时间。你可以看到，语义角色的划分非常详细。同样是动作的发出者，施事指的是真正意义上的发出动作，比如“他吃饭”中的“他”；感事则是指某种感知活动的经验者，比如“他知道这件事了”中的“他”；当事则是指性质状态的主体，比如“他病了”中的“他”；动力则是自然力量的发出者，比如“洪水淹没了村庄”中的“洪水”。语义角色的具体划分以及 17 这个数目是有争议的，不过不管怎样，这个模型本身能够非常贴切地回答“什么是语义”这个问题。

汉语有一种“投射理论”，即一个句子的结构是由这个句子中的谓语投射出来的。给定一个动词后，这个动词能够带多少个语义角色，这几个语义角色都是什么，基本上都已经确定了。因而，完整的句子所应有的结构实际上也就已经确定了。比如，说到“休息”这个动词，你就会觉得它缺少一个施事，而且也不缺别的了。我们只会说“老王休息”，不会说“老王休息手”或者“老王休息沙发”。因而我们认为，“休息”只有一个“论元”。它的“论元结构”是：

休息 <施事>

因此，一旦在句子中看到“休息”这个词，我们就需要在句内或者句外寻找“休息”所需要的施事。这个过程有一个很帅的名字，叫做“配价”。“休息”就是一个典型的“一价动词”。我们平时接触的比较多的则是二价动词。不过，它们具体的论元有可能不一样：

      吃 <施事，受事>
      去 <施事，目标>
      淹没 <动力，受事>

三价动词也是有的，例如

送 <施事，受事，与事>

甚至还有零价动词，例如

下雨 <Ф>

下面我们要教计算机做的，就是怎样给动词配价。之前，我们已经给出了解析句法结构的方法，这样计算机便能判断出每个动词究竟在和哪些词发生关系。语义分析的实质，就是确定出它们具体是什么关系。因此，语义识别的问题，也就转化为了“语义角色标注”的问题。然而，语义角色出现的位置并不固定，施事也能出现在动词后面，受事也能出现在动词前面，怎样让计算机识别语义角色呢？在回答这个问题之前，我们不妨问问自己：我们是怎么知道，“我吃完了”中的“我”是“吃”的施事，“苹果吃完了”中的“苹果”是“吃”的受事的呢？大家肯定会说，废话，“我”当然只能是“吃”的施事，因为我显然不会“被吃”；“苹果”当然只能是“吃”的受事，因为苹果显然不能发出“吃”动作。也就是说，“吃”的两个论元都有语义类的要求。我们把“吃”的论元结构写得更详细一些：

吃 <施事[语义类：人|动物]，受事[语义类：食物|药物]>

而“淹没”一词的论元结构则可以补充为：

淹没 <动力[语义类：自然事物]，受事[语义类：建筑物|空间]>

所以，为了完成计算机自动标注语义角色的任务，我们需要人肉建立两个庞大的数据库：语义类词典和论元结构词典。这样的人肉工程早就已经做过了。北京语言大学 1990 年 5 月启动的“九〇五语义工程”就是人工构建的一棵规模相当大的语义树。它把词语分成了事物、运动、时空、属性四大类，其中事物类分为事类和物类，物类又分为具体物和抽象物，具体物则再分为生物和非生物，生物之下则分了人类、动物、植物、微生物、生物构件五类，非生物之下则分了天然物、人工物、遗弃物、几何图形和非生物构件五类，其中人工物之下又包括设施物、运载物、器具物、原材料、耗散物、信息物、钱财七类。整棵语义树有 414 个结点，其中叶子结点 309 个，深度最大的地方达到了 9 层。论元结构方面则有清华大学和人民大学共同完成的《现代汉语述语动词机器词典》，词典中包括了各种动词的拼音、释义、分类、论元数、论元的语义角色、论元的语义限制等语法和语义信息。

说到语义工程，不得不提到董振东先生的知网。这是一个综合了语义分类和语义关系的知识库，不但通过语义树反映了词与词的共性，还通过语义关系反映了每个词的个性。它不但能告诉你“医生”和“病人”都是人，还告诉了你“医生”可以对“病人”发出一个“医治”的动作。知网的理念和 WordNet 工程很相似，后者是 Princeton 在 1985 年就已经开始构建的英文单词语义关系词典，背后也是一个语义关系网的概念，词与词的关系涉及同义词、反义词、上下位词、整体与部分、子集与超集、材料与成品等等。如果你装了 Mathematica，你可以通过 WordData 函数获取到 WordNet 的数据。至于前面说的那几个中文知识库嘛，别问我，我也不知道上哪儿取去。

看到这里，想必大家会欢呼，啊，这下子，在中文信息处理领域，从语法到语义都已经漂亮的解决了吧。其实并没有。上面的论元语义角色的模型有很多问题。其中一个很容易想到的就是隐喻的问题，比如“信息淹没了我”、“悲伤淹没了我”。一旦出现动词的新用法，我们只能更新论元结构：

淹没 <动力[语义类：自然事物|抽象事物]，受事[语义类：建筑物|空间|人类]>

但更麻烦的则是下面这些违背语义规则的情况。一个是否定句，比如“张三不可能吃思想”。一个是疑问句，比如“张三怎么可能吃思想”。更麻烦的就是超常现象。随便在新闻网站上一搜，你就会发现各种不符合语义规则的情形。我搜了一个“吃金属”，立即看到某新闻标题《法国一位老人以吃金属为生》。要想解决这些问题，需要给配价模型打上不少补丁。

然而，配价模型也仅仅解决了动词的语义问题。其他词呢？好在，我们也可以为名词发展一套类似的配价理论。我们通常认为“教师”是一个零价名词，而“老师”则是一个一价名词，因为说到“老师”时，我们通常会说“谁的老师”。“态度”则是一个二价的名词，因为我们通常要说“谁对谁的态度”才算完整。事实上，形容词也有配价，“优秀”就是一个一价形容词，“友好”则是一个二价形容词，原因也是类似的。配价理论还有很多更复杂的内容，这里我们就不再详说了。

但还有很多配价理论完全无法解决的问题。比如，语义有指向的问题。“砍光了”、“砍累了”、“砍钝了”、“砍快了”，都是动词后面跟形容词作补语，但实际意义各不相同。“砍光了”指的是“树砍光了”，“砍累了”指的是“人砍累了”，“砍钝了”指的是“斧子砍钝了”，“砍快了”指的是“砍砍快了”。看来，一个动词的每个论元不但有语义类的限制，还有“评价方式”的限制。

两个动词连用，也有语义关系的问题。“抓住不放”中，“抓住”和“不放”这两个动作构成一种反复的关系，抓住就等于不放。“说起来气人”中，“说起来”和“气人”这两个动作构成了一种条件关系，即每次发生了“说起来”这个事件后，都会产生“气人”这个结果。大家或许又会说，这两种情况真的有区别吗？是的，而且我能证明这一点。让我们造一个句子“留着没用”，你会发现它出现了歧义：既可以像“抓住不放”一样理解为反复关系，一直把它留着一直没有使用；又可以像“说起来气人”一样理解为条件关系，留着的话是不会有用的。因此，动词与动词连用确实会产生不同的语义关系，这需要另一套模型来处理。

虚词的语义更麻烦。别以为“了”就是表示完成，“这本书看了三天”表示这本书看完了，“这本书看了三天了”反而表示这本书没看完。“了”到底有多少个义项，现在也没有一个定论。副词也算虚词，副词的语义同样捉摸不定。比较“张三和李四结婚了”与“张三和李四都结婚了”，你会发现描述“都”字的语义没那么简单。

不过，在实际的产品应用中，前面所说的这些问题都不大。这篇文章中讲到的基本上都是基于规则的语言学处理方法。目前更实用的，则是对大规模真实语料的概率统计分析与机器学习算法，这条路子可以无视很多具体的语言学问题，并且效果也相当理想。最大熵模型和条件随机场都是目前非常常用的自然语言处理手段，感兴趣的朋友可以深入研究一下。但是，这些方法也有它们自己的缺点，就是它们的不可预测性。不管哪条路，似乎都离目标还有很远的一段距离。期待在未来的某一日，自然语言处理领域会迎来一套全新的语言模型，一举解决前面提到的所有难题。

趣题：这些词有什么共同点？

Matrix67 — Thu, 29 Dec 2011 20:07:40 +0800

据说，爱出题也是 Geek 的一种特征。这几天在做语言工程课的期末大作业时，再一次见识了汉语里各种诡异的语法规则，然后突然想到了这样一种好玩的题型，于是竟然暂时放下手中的作业，花时间编了几个这样的题目来（感谢 Geek 小美女 localhost_8080 的帮助）。
下面的每一组词中，前五个词都具有某种共同的性质，这种性质是后面五个词都不具有的。你能猜出每组词所对应的那个性质吗？

答案：(1) 可以 AABB 式重叠 (2) 量词是“条” (3) 可兼类作动词 (4) 可以儿化 (5) 可以在前面加“一”作临时量词
如果你喜欢这几个小问题，你或许会喜欢这里的第一题。

趣题：用最少的点挡住所有可能的反射路径

Matrix67 — Wed, 14 Dec 2011 00:20:46 +0800

有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为自己挡住激光（守卫实际上也是一个个点）。当然，天使可以在自己周围密密麻麻地放一圈守卫，围成一个封闭的圆形，从而让恶魔不管朝什么方向发射激光，最终都无法击中天使。我们的问题是，能把守卫的数量减少到可数个点吗？能把守卫的数量减少到有限个点吗？

这是一个非常经典的问题，我已经见过不止一次了。它可以重新叙述为很多更有趣的实际问题。去年的这个时候，网友 Spark 发来邮件，分享了他在看台球比赛时想到的一个问题：最少需要摆放多少个球，才能挡住白球到目标球的所有可能的路线，迫使对手犯规？如果我们把台球也抽象成一个一个的点，问题就和前面提到的情况一样了。

今天，我终于看到了这个问题的答案，颇为激动，在此和大家分享。

解决这类问题的一个常用技巧便是利用多次翻折把反射路线变为直线。现在，把这个房间不断地翻折，让它平铺整个平面；各种复杂的反射路径，就变成了一条一条的直线段。这样，我们便可认为恶魔的激光并不是在反射，而是径直穿过镜面射入房间的“虚像”。恶魔的目标，便是直接对准某个天使的虚像射击。由于天使的虚像只有可数个，因此天使可以在恶魔周围摆放可数个守卫，一一挡住射向每一个天使虚像的激光（有觉得下图中的网格线弯曲得异常严重吗？那是你的错觉）。

守卫的数量还能进一步减少到有限个点吗？注意到，即使只有有限的守卫，经过翻折之后也将会产生无穷多个守卫的虚像，每一个虚像都可以帮忙挡住激光。因此，只使用有限的守卫是完全有可能的。事实上，不管天使的位置 (a, b) 和恶魔的位置 (c, d) 在哪儿，摆放 16 个守卫总是足够的。下面我们给出一个具体的方案。

容易看出，所有天使虚像的坐标都形如 (2m ± a, 2n ± b) ，其中 m 和 n 都是整数（可以为负）。我们先来考察其中一类虚像，即所有形如 (2m - a, 2n + b) 的点。对于任意确定的 m 和 n ，恶魔 (c, d) 和天使虚像 (2m - a, 2n + b) 的连线都会经过 (m - a/2 + c/2, n + b/2 + d/2) 这个点，因为这个点其实是前两个点的连线的中点。也就是说，在每个格子里的 (- a/2 + c/2, b/2 + d/2) 处都放一个点，就能够挡住所有射向这类虚像的激光了（注意，当 a > c 时，横坐标是负的，因而这些点实际上将位于各个房间的 (1 - a/2 + c/2, b/2 + d/2) 处）：

等等，等等，这些黑点都是从哪儿来的？别忘了，我们只能通过翻折建立虚像，不能通过平移建立虚像。因此，事实上，我们需要在初始的房间里对称地放置四个守卫，才能让所有“虚房间”的 (- a/2 + c/2, b/2 + d/2) 处都有一个点：

类似地，天使的虚像坐标还有 (2m + a, 2n + b) 、 (2m + a, 2n - b) 、 (2m - a, 2n - b) 三类，它们又需要另外四组守卫。因此，总共 16 个守卫便能挡住所有可能的激光。

问题来源： http://www.cs.cmu.edu/puzzle/puzzle23.html