Google、T-Mobile 和 HTC 宣布了第款基于开源操作系统 Android 3G 手机其中个重要功能是利用全球卫星定位系统实现全球导航这个功能在其它手机中早已使用并且早在 5 6年前就已经有实现这功能车载设备出售其中关键技术只有两个:第是利用卫星定位；第 2根据用户输入起终点在地图上规划最短路线或者最快路线后者关键算法是计算机科学图论中动态规划(Dynamic Programming)算法



　　在图论(请见拙著图论和网络爬虫)中个抽象图包括些节点和连接他们弧比如说中国公路网就是个很好“图”例子:每个城市是个节点每条公路是个弧图弧可以有权重权重对应于地图上距离或者是行车时间、过路费金额等等图论中很常见个问题是要找个图中给定两个点的间最短路径(est path)比如我们想找到从北京到广州最短行车路线或者最快行车路线当然最直接笨办法是把所有可能路线看遍然后找到最优这种办法只有在节点数是个位数图中还行得通当图节点数(城市数目)有几十个时候计算复杂度就已经让人甚至计算机难以接受了所有可能路径个数随着节点数增长而成呈指数增长(或者说几何级数)也就是说每增加个城市复杂度要大倍显然我们导航系统中不会用这种笨办法

　　所有导航系统采用都是动态规划办法(Dynamic Programming)这里面规划(programming)词在数学上含义是“优化”意思不是计算机里面编程意思它原理其实很简单以上面问题为例当我们要找从北京到广州最短路线时我们先不妨倒过来想这个问题:假如我们找到了所要最短路线(称为路线)如果它经过郑州那么从北京到郑州这条子路线(比如是北京-> 保定->石家庄->郑州称为子路线)必然也是所有从北京到郑州路线中最短否则话我们可以假定还存在从北京到郑州更短路线(比如北京->济南->徐州->郑州称为子路线 2)那么只要用这第 2条子路线代替第条我们就可以找到条从北京到广州全程更短路线(称为路线 2)这就和我们讲路线是北京到广州最短路线相矛盾其矛盾根源在于我们假设子路线 2或者不存在或者比子路线还来得长

　　在实际实现算法时我们又正过来解决这个问题也就是说要想找到从北京到广州最短路线先要找到从北京到郑州最短路线当然聪明读者可能已经发现其中个“漏洞”就是我们在还没有找到全程最短路线前不能肯定它定经过郑州不过没有关系只要我们在图上横切刀这刀要保证将任何从北京到广州路截 2如下图



　　那么从广州到北京最短路径必须经过这条线上某个城市(图中蓝色菱形)我们可以先找到从北京出发到这条线上所有城市最短路径最后得到全程最短路线定包括这些局部最短路线中条这样我们就可以将个“寻找全程最短路线”问题分解成个个小寻找局部最短路线问题只要我们将这条横切线从北京向广州推移直到广州为止我们全程最短路线就找到了这便是动态规划原理采用动态规划可以大大降低最短路径计算复杂度在我们上面例子中每加入条横截线线上平均有十个城市从广州到北京最多经过十 5个城市那么采用动态规划计算量是 10×10×15而采用穷举路径笨办法是 10 15 次方前后差了万亿倍



　　那么动态规划和我们拼音输入法又有什么关系呢？其实我们可以将汉语输入看成个通信问题而输入法则是个将拼音串到汉字串转换器每个拼音可以对应多个汉字个拼音串就可以对应图论中张图如下:



　　其中Y1,Y2,Y3,……,YN 是使用者输入拼音串W11,W12,W13 是第个音 Y1 候选汉字W21,W22,W23,W24 是对应于 Y2 候选汉字以此类推从第个字到最后个字可以组成很多很多句子我们拼音输入法就是要根据上下文找到个最优句子如果我们再将上下文相关性量化作为从前个汉字到后个汉字距离那么寻找给定拼音条件下最合理句子问题就变成了个典型“最短路径”问题我们算法就是动态规划

　　上面这两个例子导航系统和拼音输入法看似没什么关系但是其背后数学模型却是完全样数学妙处在于它每个工具都具有相当普遍性在区别应用中都可以发挥很大作用

　　我们在下个系列将详细介绍专门针对拼音输入法“维特比算法”