数学之美 系列二十四 - 从全球导航到输入法——谈谈动态规划
今年九月二十三日，Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机，其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用，并且早在五六年前就已经有实现这一功能的车载设备出售。其中的关键技术只有两个：第一是利用卫星定位；第二根据用户输入的起终点，在地图上规划最短路线或者最快路线。后者的关键算法是计算机科学图论中的动态规划（Dynamic Programming）的算法。
在图论（请见拙著《图论和网络爬虫》）中，一个抽象的图包括一些节点和连接他们的弧。比如说中国公路网就是一个很好的“图”的例子：每个城市一是个节点，每一条公路是一个弧。图的弧可以有权重，权重对应于地图上的距离或者是行车时间、过路费金额等等。图论中很常见的一个问题是要找一个图中给定两个点之间的最短路径（shortest path）。比如，我们想找到从北京到广州的最短行车路线或者最快行车路线。当然，最直接的笨办法是把所有可能的路线看一遍，然后找到最优的。这种办法只有在节点数是个位数的图中还行得通，当图的节点数（城市数目）有几十个的时候，计算的复杂度就已经让人甚至计算机难以接受了，因为所有可能路径的个数随着节点数的增长而成呈指数增长（或者说几何级数），也就是说每增加一个城市，复杂度要大一倍。显然我们的导航系统中不会用这种笨办法。
所有的导航系统采用的都是动态规划的办法（Dynamic Programming），这里面的规划（programming）一词在数学上的含义是“优化”的意思，不是计算机里面编程的意思。它的原理其实很简单。以上面的问题为例，当我们要找从北京到广州的最短路线时，我们先不妨倒过来想这个问题：假如我们找到了所要的最短路线（称为路线一），如果它经过郑州，那么从北京到郑州的这条子路线（比如是北京-> 保定->石家庄->郑州，称为子路线一），必然也是所有从北京到郑州的路线中最短的。否则的话，我们可以假定还存在从北京到郑州更短的路线（比如北京->济南->徐州->郑州，称为子路线二），那么只要用这第二条子路线代替第一条，我们就可以找到一条从北京到广州的全程更短的路线（称为路线二），这就和我们讲的路线一是北京到广州最短的路线相矛盾。其矛盾的根源在于，我们假设的子路线二或者不存在，或者比子路线一还来得长。
在实际实现算法时，我们又正过来解决这个问题，也就是说，要想找到从北京到广州的最短路线，先要找到从北京到郑州的最短路线。当然，聪明的读者可能已经发现其中的一个“漏洞”，就是我们在还没有找到全程最短路线前，不能肯定它一定经过郑州。不过没有关系，只要我们在图上横切一刀，这一刀要保证将任何从北京到广州的路一截二，如下图。
那么从广州到北京的最短路径必须经过这一条线上的某个城市（图中蓝色的菱形）。我们可以先找到从北京出发到这条线上所有城市的最短路径，最后得到的全程最短路线一定包括这些局部最短路线中的一条，这样，我们就可以将一个“寻找全程最短路线”的问题，分解成一个个小的寻找局部最短路线的问题。只要我们将这条横切线从北京向广州推移，直到广州为止，我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在我们上面的例子中，每加入一条横截线，线上平均有十个城市，从广州到北京最多经过十五个城市，那么采用动态规划的计算量是 10×10×15，而采用穷举路径的笨办法是 10 的 15 次方，前后差了万亿倍。
那么动态规划和我们的拼音输入法又有什么关系呢？其实我们可以将汉语输入看成一个通信问题，而输入法则是一个将拼音串到汉字串的转换器。每一个拼音可以对应多个汉字，一个拼音串就可以对应图论中的一张图，如下：
其中，Y1,Y2,Y3,……,YN 是使用者输入的拼音串，W11,W12,W13 是第一个音 Y1 的候选汉字，W21,W22,W23,W24 是对应于 Y2 的候选汉字，以此类推。从第一个字到最后一个字可以组成很多很多句子，我们的拼音输入法就是要根据上下文找到一个最优的句子。如果我们再将上下文的相关性量化，作为从前一个汉字到后一个汉字的距离，那么，寻找给定拼音条件下最合理句子的问题就变成了一个典型的“最短路径”问题，我们的算法就是动态规划。
上面这两个例子导航系统和拼音输入法看似没什么关系，但是其背后的数学模型却是完全一样的。数学的妙处在于它的每一个工具都具有相当的普遍性，在不同的应用中都可以发挥很大的作用。
我们在下一个系列将详细介绍专门针对拼音输入法的“维特比算法”。
全文很长，摘录其中几段与各位分享。
“请你想想，为什么有股市泡沫和楼市泡沫。在我的看法里，他是整个工商链条的第二张骨牌。第一张是什么？美国的问题来自于金融危机，中国的问题来源于制造业危机，也就是说这两年由于制造业所面临的投资营商环境不断恶化的结果，使得大量的制造业资金，原先应该投入制造业的没有投入，而去做什么呢？进入了楼市、股市，造成了楼市和股市的泡沫。”
“房价涨幅最大的地方，倒闭企业是最多的。”
“中国的实体经济最后的决定因素还是制造业，制造业受到摧残，就不断的下跌，直接导致了股市和楼市的下跌。那这之后呢？老百姓更加不想消费了，更加贫穷了，再下一张就会影响到生产，再下一张失业就出来了，再下一致张就更不敢消费了，然后就恶性循环。我们拿我们的工商链条和欧美的工商链条相比，你应该理解了，什么叫做真正意义上的救市。不过我们第一关没有在制造业产生危机的时候设立防火墙。第二关没有在股市泡沫和楼市泡沫的时候设立防火墙，而是打击他。你打击的话是加速你的崩溃，你要设立防火墙才可以解决你的问题。结果使老百姓更加的贫穷，这次股市下跌基本上摧毁了大部分的中产阶级，这导致居民更加不敢消费，从此造成了恶性循环。”
“我很担心大量的资源继续投入GDP工程，继续修桥铺路，如果这么做的话，会使得资源包括银行的信贷，继续被误导到过热的部门。因此制造业未来会更加的困难。我们虽然有更好的路，更好的桥，更好的绿化，而制造业持续的恶化，会让我们的老百姓给更加的贫穷。”
“我们的制造业为什么这么不抗压。我前面说过了，汇率、成本、劳动合同法的问题。使得制造业所面临的环境急速的恶化。很多人问我，为什么不提价呢？为什么不能提价？因为我们这么多年的经济发展，我们把社会上的资源都放在了纯制造，我们常常自诩为制造业大国，其实根本不是。为什么中国出不了三星，为什么出不了 LG、SK、现代，一个小小的韩国，还没有浙江省大，可以出四家大公司。你想想如果中国每一省都有这样一个这样的公司的话，我们有多少个三星。可是为什么改革开放30年中国没有一家三星，甚至没有一家高科技，没有大面积的高科技，甚至我们出不了一家真正意义上的跨国企业，为什么？”
“中国出不了索尼，出不了三星。为什么呢？因为我们缺乏一个系统。我们这么多年的发展，没有在企业的制造各个方面建立起一个前所未有的系统来。这也是为什么我们中国这么多年来，连个汽车发动机都做不好。或许有人说中国有厂家可以做了原型发动机，也达标了。我们说那是原型，一量产就不行了。我们缺乏系统，缺乏系统就会使得我们的质量不稳定。什么叫系统？第一，我们缺乏一个大的系统，叫做6+1的高效整合大系统，第二我们缺乏一个以1为主的小系统，叫做供需流程式的制造流程。我们既缺大的也缺小的。”
“我们很多的工厂，在上海做发动机的工厂，他只有车间没有系统，你只要没有系统，你就无法积累你的技术，而什么是现代工业的基础？什么是高科技的基础，那就是积累。那才叫做高科技。积累之后，你才知道如何改进。所以高科技的本质是什么？通用、索尼、现代的本质是什么？是小系统。所以说到这里我们发现，制造业要好，大系统、小系统都不能缺，如果都缺的话，你就会发现再困难的环境下，我们的制造业是举步维艰，你甚至往下走都不知道怎么走下去。第一，你一直处于6+1的最低端，第二以1为主的制造，你还缺乏小系统。这个所谓的系统工程，就是我国未来能够成为真正本质意义上制造业大国的必备基础。”
“但是你没有，没有的结果呢？那就是制造业出现了重大的危机，下一步是什么呢？最近央行公布有2万亿热钱流入中国，你们认为这些钱流入中国是干吗的？很多人说是抄底。你知道为什么这么讲吗？因为这就是我们的水平。因为我有钱我就炒炒底，我买一个楼。所以想外国人就是这样的水平。你觉得是吗？我跟你讲，这么多热钱，合法的也好，非法的也好，他不是不炒楼，也不是不炒股，真正的目的是什么？是收购制造业，大家都没有危机意识。”
“目前是什么状况呢？中国进出口总额55%是外资的，中国高科技出口87%是外资，高科技不谈了，连你们吃的食用油85%是外资，汽车零配件业高端的90% 是外资。连我们河北某些粮食局也被收购，高盛收购我们养猪的整条6+1产业链。为什么收购？收购之后改造小系统，完成大系统，这是外资的目的。因此把这些缺乏小系统的公司，收购之后融入到国际6+1的产业链当中去。虽然你做1块钱的巴比娃娃是亏钱的，你最多可以亏多少钱呢？最多也就是1块钱吧，他把这1美元的亏损收购了以后，然后放在6+1里面，这可以产生多少的利润呢？他可以轻松的把1美元赚回来。这就是他们的目的，你只要看到高盛收购整条养猪产业链你就应该警觉了，把你融入产业链之后，整条产业链是不赔钱的。如果你和他合资呢？如果你以1为主的制造业和6+1的外资合资的话，你就很可能会被吃掉，他把 6+1，跟你合资的部分，他把利润都转移到其他的部分，跟你合资的这块连亏3年，然后把你的股份稀释到1%，然后再把利润拿回来，把你吃掉。我们说产业链的战争时代来临了。这些事件我在以前也都说过，包括在八大危机当中我也说过，只是没有想到来的这么快，都来了。”
作者：李承鹏
我总觉得，全国30个作协主席参加“盛大网络文学大赛”角逐10万人民币，很像当年少林的色相大师和武当的空虚道长在洞里守不住寂寞，就黑衣黑裤跳到江湖中装夜行侠，这个的好处是重塑名门正派亲民的形象，坏处是由于地形不熟，哪天晚上一不小心走错门或用错“鸡鸣五更散”，便被民间妇女误当成了采花淫贼。
不过辛苦了色相、空虚两位大师，比起中国音协，中国作协的掌门人们还算敢放下身段，半年多前徐沛东、阎肃、谷建芬居然开大会围剿网络音乐，用“中国音协”的红头文件来禁止“老鼠爱大米”“香水有毒”进一步传播，最牛逼的是，徐沛东说他们要自己搞网络音乐创作，把网络音乐引入到严肃的殿堂，这相当于，少林武当弟子今后要改练广播体操了，还说这就是“易筋经”。
中国文学现在碰到的问题和中国足球是一样的，中国足球根本就不是足球，中国足球是行政长官的意志，是蹴鞠，中国文学也不是文学，是主流意志养活的产品，是二奶，直到现在广电总局还禁止电视剧反映第三者题材说是有伤教化，二奶反对“小三”，真他妈会排位。以此类推到中国音乐，中国美术，中国戏曲，中国新闻，凡意识形态的都成了意志形态，打上长官意志，又红又专像阳澄湖大闸蟹上的商标。
我们的语文教育恨不得让六年级小学生就明白“文以载道”，左一刀“中心思想”右一刀“段落大意”，把本来好好一篇文章肢解得不像人话，这种教育出来的作品基本都有点前列腺炎的症状，就是憋半天整不出一行顺溜的水来，滴滴哒哒的，还说能从“一滴水里发现太阳”。
到大学中文系，就是葵花宝典境界了，欲练此功必先自宫，我学的每一门课前言都是该门学科的“概论”，前言必是“用马克斯列宁主义毛泽东思想来指挥文学创作”，连古文史、语言学和美学都无一幸免，真不经细想，那时候革命的马列毛都没出生，就能指挥不那么革命的“羊大为美”“关关雎鸠”和“孤舟蓑笠翁，独钓寒江雪”……
这样能出好作家就怪了，建国以来根本没有好作家，小时候很崇拜白桦，后来发现“伤痕文学”其实是“撒娇文学”，就是被“四人帮”性虐待后还拿出伤疤给大家看说其实这是漂亮纹身，再后来的“寻根文学”就是自摸文学，自以为把根留住，实际上在搞无性繁殖。包括贾平凹、苏童、余华，他们好，但没有传说中那么好，也就是把半本《葵花宝典》练成《避邪剑谱》那个地步，还不如葵花宝典正主的郭沫若、茅盾来得更极品。
中国没出好作家的原因是拒绝民间，从这个意义我觉得新中国以来的好作家应该是赵本山、郭德纲、王朔、王小波，文学应该纪录时代特征，他们的作品一看就知道在反映哪个时代哪些人群，透着真实和人味，可其他的特别是郭沫若，你就说这是他在描写火星也无不可。
说回到30作协主席参加网络写作大赛，很难说主席们能写出什么好作品，这些年来已经正处副厅级别的他们要么在家养花喂鱼，要么忙着到处领红包，我知道这相当于政府花钱树立了一个牌坊，他们负责写春联，上联是：“有文化”，下联是“很和谐”，横批“坐家”。所以我特别不喜欢用雅文学和俗文学来对比，就像我从来没觉得《文化苦旅》很雅，也没觉得《十八摸》很俗，中国现阶段出不了索尔仁尼琴，但我觉得这是作协的康熙、乾隆们集体到网络的一次微服私访，捏了个脚，做一个SPA，玩腻了庄妃德妃后去和民间的翠花调回情，从这个意义来讲这个活动就成功了。
唯一的担心，不知主席们能不能受得了文章后面的网络跟帖，它极大考验着我们的作协领导们的心理素质，他们平时发言时总受跟屁虫的追捧，这次情况不一样了，网络像个虚拟的人体，每个人都可以发表文章，那就是大脑，可那些跟帖却是下水，按惯例，进化到色相、空虚这样的境界后一般就只有灵魂没有下水了，可你来网络混还不能没下水，凡关闭评论栏跟帖功能的显得多变态。不过我喜欢看这个，网络中的雷人很多，怕几回合下来没成就作协主席却成就了跟帖的帖主。这就像当年武林大会，没成就金轮法王，却成就了小杨过。
总之，这是一个很好的试验，说漂亮点是微服私访，说实在点就是贵妃们也出来混坐台了，下一步，就该全国各地足协主席上场比赛一回脚法，全国音协主席比一回唱歌，全国美协主席比一回画画，全国自行车摩托协会主席比一回自摩。
那才叫，盛况空前。
博文
所有评论
