第 12 章 地图和本地搜索的最基本技术
Last updated
Last updated
利用导航仪进行卫星定位。
地址的识别。
根据用户输入的起点和终点，在地图上规划最短路线或者最快路线。
有限状态机是一个特殊的有向图，包括一些状态（节点）和连接这些状态的有向弧。每一个有限状态机有一个开始状态和一个终止状态，以及若干中间状态。每一条弧上带有从上一个状态进入下一个状态的条件。如果输入的符号可以从状态机的开始状态经过中间状态，走到终止状态，那么这条地址就有效，否则无效。
定义（有限状态机）有限状态机是一个五元组，其中：
是输入符号的集合。
是一个非空的有限状态的集合。
是中的一个特殊状态，起始状态。
是一个从空间到的映射函数，即：。
是中另外一个特殊状态，终止状态。
如果输入和输出的可能性不同，也可以给赋予每条边权重。
关键要解决两个问题，即：通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。
有限状态机只能进行严格匹配，当用户输入存在错误时，则无法识别。基于概率的有限状态机可以解决该问题（效果等同马尔可夫链，相当于给每个有向弧加上概率）。
加权图：一个抽象的图包括节点和连接他们的弧，以及每条弧的权重。找到一个图中给定两点间的距离，最直接的办法就是计算出所有的路径权重，找出最优的。不过可能路径数量随着节点数的增长而成指数增长，复杂度过高。
假设已经找到了从北京到广州的最短路径，且经过郑州，那么从北京到郑州的这条子径也是所有从北京到郑州的路线中最短的。反过来想，如果想要找到从北京到广州的最短路线，先要找到北京到郑州（即某个必经的中间节点）的最短路线。如何找到必经的中间节点？
只要在图上横切一刀，这一刀一定要保证将任何从北京到广州的路线一分为二（怎么切？？）。那么从广州到北京的最短路径必须经过这一条线上的某个城市。我们可以先找到从北京出发到这条线上所有城市的最短路径，最后得到的全城最短路线一定包括这些局部最短路线中的一条，这样，就可以将一个“寻找全城最短路线”的问题，分解成一个个寻找局部最短路线的小问题。
动态规划最重要的两个要点：
状态(状态不太好找，可先从转化方程入手分析)
状态间的转化方程(从题目的隐含条件出发寻找递推关系)
其他的要点则是如初始化状态的确定(由状态和转化方程得知)，需要的结果(状态转移的终点)
动态规划问题中一般从以下四个角度考虑：
状态(State)
状态间的转移方程(Function)
状态的初始化(Initialization)
返回结果(Answer)
动规适用的情形：
最大值/最小值
有无可行解
求方案个数(如果需要列出所有方案，则一定不是动规，因为全部方案为指数级别复杂度，所有方案需要列出时往往用递归)
给出的数据不可随便调整位置
有限状态机和动态规划应用广泛。