等高线模式:解决极大极小问题的另类策略

    最近在看Pólya的《数学与猜想》,读到了一些很有意思的东西,在这里和大家分享。
    我们首先来看一道很火星的题目:A、B两点在已知直线的同侧,请在直线上找出一点C使得∠ACB最大。可能大家都知道这个该怎么做,但这个解法到底是怎么想到的呢?《数学与猜想》提到了这样一种看法:
      
    首先,我们需要确定,这条直线上的确存在一点,使得这个角度达到最大。我们很容易观察到,这个动点往左移(可以一直移动到BA的延长线与直线的交点),这个角度会慢慢变小;同时,动点不断往右移时角度也会慢慢变小(在无穷远处角度为0)。可以想到,角度大小的变化可以用一个凸函数来表示,这段函数上一定存在一个最大点。现在任意在直线上取一点C,你怎么才能说明∠ACB是最大或者不是最大?一个比较直观的方法是,如果你取的C点不能使角度达到最大,那么这条直线上一定存在另一个点C',使得∠ACB=∠AC'B。分析到这一步,问题终于有了眉目,因为有一个大家都很熟悉的东西恰好与角度相等有关——同一段弧所对的圆周角总是相等。过点AB作一系列的圆,那么同一个圆周上的所有点对AB的张角都是一样大的。我们看到,这些蓝色的线条与直线的交点都是成对出现,换句话说ABC三点确定的圆与直线的另一个交点就是那个C'。但有那么一个点非常例外:在这无穷多个圆中,有一个圆恰好与直线相切。这个切点只出现了一次,它就是角度大小的极大值。

    真正的数学家会从这个简单的题目里看到一些更深的思想。我们可以把这个图任意的扭曲,从而得到这样一个有趣的结论。假设我和MM在野外探险,地形是任意给定的,我们的行动路线也是任意给定的。现在我有一张非常精确的等高线地图,我把我们的路线画在地图上,那么整个旅途中所到达的最高点和最低点在地图上的什么位置?仔细思考等高线的定义,我们立即想到:路径穿过等高线的地方肯定不会是最高点或最低点,因为穿过一条等高线即表明你正在爬上爬下。因此,达到最高点或最低点的地方只能是等高线与我的路线相切的地方。这给我们一个启发:我们可以用这种模式来解决很多极大极小问题。我们把所有可能的结果的分布情况用等高线表示,而实际允许的初始条件则被限制在了一条路径上,那么最优解必然是这条路径与某条等高线的切点。用等高线模式来解释刚才的问题将变得非常简单:图中的蓝色线条就是角度大小的“等高线”,在直线上取得极值的时候,等高线恰与直线相切,其它情况下角度大小都在“变化进行时”。
    我们再来看三个有趣的例子。在第一个例子中我们将解释为什么点到直线的距离以垂线段最短,第二个例子则将探究为什么所有的圆内接n边形以正n边形最大。在第三个例子里我们将提到一个与椭圆有关的神奇性质。

      

    上面这个图就是到定点距离大小的等高线图。我们可以立即看到,等高线就是一个个的同心圆。与已知直线相切的那个同心圆确定了直线到给定点距离最短的位置,而圆的半径与对应位置上的切线垂直,这就说明了点到直线的距离以垂线段最短。

      
    下面我们考虑圆内接多边形的某个顶点X。这个顶点两旁的点分别是A和B。那么整个多边形被分成了两部分:三角形AXB,和剩下的那一大块多边形。如果我们只移动点X,这只会影响三角形AXB的面积,对剩下的部分没有影响。X在不同位置所得到的三角形面积不同,在图中我们用蓝色的等高线来表示这个面积值的分布情况。由于等底等高的三角形面积相同,因此我们的等高线是一系列互相平行的直线。点X只能在一段圆弧上取,当△AXB达到最大时X必然落在圆弧与某条直线相切的地方,显然此时AX=BX。换句话说,只要圆内接多边形里有长度不等的邻边,那么这个多边形的面积一定可以变得更大。再换句话说,只有所有边都相等了,面积才可能达到最大。这就说明了,所有的圆内接n边形以正n边形最大。

    我相信你已经对这个方法非常熟悉了,因此最后这个例子我就不画图了。在第三个例子中,我们将考虑一个和光学有关的性质。给定一条直线和直线同侧的两点A、B,那么直线上一定有一点C使得AC+BC达到最小。这个点C是一个以A、B为焦点的椭圆形等高线与直线的切点。固定点A和点B,适当调整直线的位置,结论始终成立。还记得Fermat原理吗,光从一点到另一点总是沿着光程最短的路径来传播。仅考虑反射定律,这个结论很显然。也就是说,A->C->B这样的光线传播路径完全遵循光的反射规律。嘿!我证明了这样一个富有传奇色彩的结论:椭圆形从一个焦点发射出来的光线总会反射到另一个焦点。

做人要厚道
转贴请注明出处

趣题:Anagram辅助程序的数据结构

    Anagram是一个比较流行的英文文字游戏,本Blog之前曾经介绍过,这里我再提一下。Anagram就是把一个词或者一句话里的字母重新排列,组成一个新的单词或句子,通常前后两者有一种讽刺的意味。比如,Dormitory = Dirty Room,或者Desperation = A Rope Ends It。创作一个有意思的Anagram并不是一件容易的事,你很可能需要计算机的帮助才能找到合适的词。例如,我们可以利用Hash表瞬间找出与给定单词所使用的字母完全相同的单词。我们可以把字典中每个单词的字母按照字母顺序重新排列,于是对单词dame和made操作后的结果都是adem,这样的话使用字母完全相同的单词就对应了一个唯一的Hash值,我们就可以方便地把它们归在一起。
    而实际上,这个Hash表往往没什么用。一个Anagram很可能是由多个单词构成的,因此我们更希望知道,使用某个单词中的字母(不一定全部使用)可以构造出哪些新的单词。例如,我输入单词dormitory,则程序可以输出dirty, motor, trim, dry, room等单词。很多Anagram辅助程序都有这样的功能,并且这也单独作为一个文字游戏存在。我们称这种只用到一部分给定字母的单词叫做不完全Anagram。假如字典里共有n个单词,输入数据长度为l,那么你怎样才能找出所有的不完全Anagram?一种方法是遍历所有n个单词,依次判断每个单词是否合法;另一种方法则是枚举输入数据的2^l子集,对每个子集在之前建立的Hash表中查询一次。现在,你能否想出一个数据结构,使得你的Anagram辅助程序能够以最快的速度输出任何一个给定单词的不完全Anagram?

  
    答案比你想像的更简单,这是一个非常简单的数据结构。我们建立一棵高度为26的树,按照每个字母出现的次数像Trie一样插入到树中。比如,abacus有2个a,于是插入到根的第二个子树里,接下来数出字母b的个数为1,并继续沿标号为1的边往下走,依此类推。最后,所有的数据都存放在对应的叶子节点上。查询时,在每个节点上只需数一数输入数据中对应字母的个数N,沿着标号小于等于N的边往下走就行了。
    下面是一个非常有趣的问题:这个数据结构还有什么优化的余地?比如,单词在树中是按照从A到Z的顺序依次分类,但实际上我们可以任意调整这个顺序。那么,你觉得建这棵树时是先按E、T等常用字母的个数分类好,还是先按照Q、Z等不常用字母的个数分类好?这个问题很简单,留给大家思考吧。
    另一个比较类似的东西是用于拼写检查的数据结构。这两个有趣的数据结构都是我在这里看到的。

做人要厚道
转贴请注明出处

编辑距离、拼写检查与度量空间:一个有趣的数据结构

    除了字符串匹配、查找回文串、查找重复子串等经典问题以外,日常生活中我们还会遇到其它一些怪异的字符串问题。比如,有时我们需要知道给定的两个字符串“有多像”,换句话说两个字符串的相似度是多少。1965年,俄国科学家Vladimir Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离,我们通常叫它“编辑距离”。字符串A到B的编辑距离是指,只用插入、删除和替换三种操作,最少需要多少步可以把A变成B。例如,从FAME到GATE需要两步(两次替换),从GAME到ACM则需要三步(删除G和E再添加C)。Levenshtein给出了编辑距离的一般求法,就是大家都非常熟悉的经典动态规划问题。
    在自然语言处理中,这个概念非常重要,例如我们可以根据这个定义开发出一套半自动的校对系统:查找出一篇文章里所有不在字典里的单词,然后对于每个单词,列出字典里与它的Levenshtein距离小于某个数n的单词,让用户选择正确的那一个。n通常取到2或者3,或者更好地,取该单词长度的1/4等等。这个想法倒不错,但算法的效率成了新的难题:查字典好办,建一个Trie树即可;但怎样才能快速在字典里找出最相近的单词呢?这个问题难就难在,Levenshtein的定义可以是单词任意位置上的操作,似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能,提出更正建议的速度是很快的。它们到底是怎么做的呢?1973年,Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在,它初步解决了一个看似不可能的问题,而其原理非常简单。

    首先,我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离,那么显然:

1. d(x,y) = 0 当且仅当 x=y  (Levenshtein距离为0 <==> 字符串相等)
2. d(x,y) = d(y,x)     (从x变到y的最少步数就是从y变到x的最少步数)
3. d(x,y) + d(y,z) >= d(x,z)  (从x变到z所需的步数不会超过x先变成y再变成z的步数)

    最后这一个性质叫做三角形不等式。就好像一个三角形一样,两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”,如果这个距离函数同时满足上面说的三个性质,我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间,它的距离函数就是点对的直线距离。度量空间还有很多,比如Manhattan距离,图论中的最短路,当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样,BK树可以用于任何一个度量空间。

    建树的过程有些类似于Trie。首先我们随便找一个单词作为根(比如GAME)。以后插入一个单词时首先计算单词与根的Levenshtein距离:如果这个距离值是该节点处头一次出现,建立一个新的儿子节点;否则沿着对应的边递归下去。例如,我们插入单词FAME,它与GAME的距离为1,于是新建一个儿子,连一条标号为1的边;下一次插入GAIN,算得它与GAME的距离为2,于是放在编号为2的边下。再下次我们插入GATE,它与GAME距离为1,于是沿着那条编号为1的边下去,递归地插入到FAME所在子树;GATE与FAME的距离为2,于是把GATE放在FAME节点下,边的编号为2。
      
    查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词,这个错误单词与树根所对应的单词距离为d,那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小,因此每次与某个节点进行比较时都可以排除很多子树。
    举个例子,假如我们输入一个GAIE,程序发现它不在字典中。现在,我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较,得到的距离d=1。由于Levenshtein距离满足三角形不等式,因此现在所有离GAME距离超过2的单词全部可以排除了。比如,以AIM为根的子树到GAME的距离都是3,而GAME和GAIE之间的距离是1,那么AIM及其子树到GAIE的距离至少都是2。于是,现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离,发现它为2,于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点,发现GAIE和GAIN距离为1,输出GAIN并继续沿编号为1或2的边递归下去(那条编号为4的边连接的子树又被排除掉了)……
    实践表明,一次查询所遍历的节点不会超过所有节点的5%到8%,两次查询则一般不会17-25%,效率远远超过暴力枚举。适当进行缓存,减小Levenshtein距离常数n可以使算法效率更高。

Matrix67原创
做人要厚道 转贴请注明出处

Google面试题中的两道趣题

看看下面两道题,它的解答非常简单,即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来?一小时?一分钟?一秒钟?

1. 给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。

2. 给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。

Solution:
1. 遍历链表,给每个元素赋一个0到1之间的随机数作为权重(像Treap一样),最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍,然后从后往前再扫一遍。也就是说,线性时间构造两个新数组,P[i]=A[1]*A[2]*…*A[i],Q[i]=A[n]*A[n-1]*…*A[i]。于是,B[i]=P[i-1]*Q[i+1]。

突然想到,给别人(MM?)介绍信息学时,用这两道题当例子挺合适的。

推荐网页:一大堆的Computer Science Puzzle

http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml

一些很另类的信息学问题,比如:用常数空间线性时间找链表中的一个环,只用NAND实现XOR门,不用乘法和加法把一个数乘以7,常数时间无附加空间交换两变量,写一个输出自己代码的程序,用n + O(log n)次比较查找第二小的元素,写一个程序用C编译时输出“C”而用C++编译时输出“C++”……

另外,不要找我要答案,我这里没有答案