数学之美

前言 　　第1章　文字和语言 vs 数字和信息 　　第2章　自然语言处理 — 从规则到统计 　　第3章　统计语言模型 　　第4章　谈谈中文分词 　　第5章　隐含马尔可夫模 　　第6章　信息的度量和作用 　　第7章　贾里尼克和现代语言处理 　　第8章　简单之美 — 布尔代数和搜索引擎的索引 　　第9章　图论和网络爬虫 　　第10章　PageRank — Google的民主表决式网页排名技术 　　第11章　如何确定网页和查询的相关性 　　第12章　地图和本地搜索的最基本技术 — 有限状态机和动态规划 　　第13章　Google AK-47的设计者 — 阿米特 · 辛格博士 　　第14章　余弦定理和新闻的分类 　　第15章　矩阵运算和文本处理中的两个分类问题 　　第16章　信息指纹及其应用 　　第17章　由电视剧《暗算》所想到的 — 谈谈密码学的数学原理 　　第18章　闪光的不一定是金子 — 谈谈搜索引擎反作弊问题 　　第19章　谈谈数学模型的重要性 　　第20章　不要把鸡蛋放到一个篮子里 — 谈谈最大熵模型 　　第21章　拼音输入法的数学原理 　　第22章　自然语言处理的教父马库斯和他的优秀弟子们 　　第23章　布隆过滤器 　　第24章　马尔可夫链的扩展 — 贝叶斯网络 　　第25章　条件随机场和句法分析 　　第26章　维特比和他的维特比算法 　　第27章　再谈文本自动分类问题 — 期望最大化算法 　　第28章　逻辑回归和搜索广告 　　第29章　各个击破算法和Google云计算的基础
数学之美 系列二十四 -- 从全球导航到输入法――谈谈动态规划
2008 年 10 月 14 日 下午 08:34:00

发表者：Google（谷歌）研究员 吴军



今年九月二十三日，Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机，

其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用，并且早在

五六年前就已经有实现这一功能的车载设备出售。其中的关键技术只有两个：第一是利用卫星定位；第二

根据用户输入的起终点，在地图上规划最短路线或者最快路线。后者的关键算法是计算机科学图论中的动

态规划（Dynamic Programming）的算法。




在图论（请见拙著《图论和网络爬虫》）中，一个抽象的图包括一些节点和连接他们的弧。比如说中国公

路网就是一个很好的“图”的例子：每个城市一是个节点，每一条公路是一个弧。图的弧可以有权重，权重

对应于地图上的距离或者是行车时间、过路费金额等等。图论中很常见的一个问题是要找一个图中给定两

个点之间的最短路径（shortest path）。比如，我们想找到从北京到广州的最短行车路线或者最快行车

路线。当然，最直接的笨办法是把所有可能的路线看一遍，然后找到最优的。这种办法只有在节点数是个

位数的图中还行得通，当图的节点数（城市数目）有几十个的时候，计算的复杂度就已经让人甚至计算机

难以接受了，因为所有可能路径的个数随着节点数的增长而成呈指数增长（或者说几何级数），也就是说

每增加一个城市，复杂度要大一倍。显然我们的导航系统中不会用这种笨办法。



所有的导航系统采用的都是动态规划的办法（Dynamic Programming），这里面的规划（programming）

一词在数学上的含义是“优化”的意思，不是计算机里面编程的意