有限状态机和动态规划
地图与本地搜索的核心技术
1 地质分析和有限状态机
上下文有关文法的分析，既复杂又耗时，他的分析器也不好写，如果没有好的模型，这个分析写出来很难看，不说还有很多情况覆盖不了
地址的文法是上下文，有关文法中最简单的一种，因此有许多识别和分析的方法，但是最有效的是有限状态机
有限状态机是一个特殊的有向图，它包括一些状态节点和连接这些状态的有向弧
每一个有限状态机都有一个开始状态和中止状态，以及若干中间状态，每一条湖上带有从一个状态进入下一个状态的条件
如果一条地址能从状态机的开始状态经过状态机的若干中间状态，走到终止状态，则这条地址有效，否则无效
上述基于有限状态机的地址识别方法在实用中会有一些问题：当用户输入的地址不太标准，或者有错别字时，有限状态机会束手无策，因为他只能进行严格匹配
为了解决这个问题，我们希望看到可以进行模糊匹配，并给出一个字串为正确地址的可能性
为了实现这一目标，科学家们提出了基于概率的有限状态机，这种其于状态的有限状态机和离散的马尔科夫链基本上等效
2 全球导航 和 动态规划
全球导航的关键算法是计算机科学图论中的动态规划的算法
在图论中，一个抽象的图包括一些节点和连接他们的弧，如果再考虑每条弧的长度，或者说权重那么这个图就是加权图
图中湖的群众对于地图上的距离
图论中很常见的一个问题，就是要找一个图中给定两个点之间的最短路径
先找到从北京出发到这条线上所有城市的最短路径，
最后得到的全程最短路线一定包括这些局部最短路线中的一条，
这样就可以将一个“寻找全程最短路线”的问题分解成一个个寻找局部最短路线的小问题。
只要将这条横切线从北京向广州推，直到广州为止，我们的全程最短路线就找到了
这边是动态规划的原理。采用动态规划，可以打打降低最低路径的计算复杂度
正确的数学模型可以将一个计算量开始很大的问题的计算复杂度大大降低，这便是数学的妙用
小结
有限状态机和动态规划的应用非常广泛，远远不止识别地址，导航等地图服务相关领域，他们在语音识别拼写语法纠错，拼音输入法，工业控制和生物的序列分析等领域都有着极其重要的应用
-----摘抄 吴军《数学之美》第二版