广州白云离天河有多远?
从地图上量距离,其实是很傻的做法,因为城市并不是一个规则图形,而是一个复杂的网状结构。把每一个十字路口都当作一个节点,把每一条路都当作一根线,这样就能组成一张“路面网络图”。 然后我们输入起点和终点,就可以得到“路程”这个答案了——实际上就是求两个节点的最短路径。 但是这样的算法是有局限性的,它只考虑了“路”的因素,却没有考虑到其他因素(比如红绿灯、路段封闭等等)的影响,得到的“路程”其实只是一个理论值。 在现实中,我们并不会看到两条平行的线段连接着同一个节点,因为我们不会走直线——当我们转弯的时候,“路线”其实是转了一个“圆弧”的。
我们实际走的路线比这两条平行线组成的“最短线路”要长。 为了考虑转弯的问题,我们需要引入另一个工具:拓扑学。
在数学中,拓扑学是研究几何学对象的集合,这些集合并不依赖于具体的度量方式。拓扑学不关心“距离”这个问题。但是,如果我们在拓扑学对象里进行路径查找,就能直接得出结果来。 因为拓扑学是一个宏观学科,它不能给出某一个具体问题的解,只能给出一般性结论。所以拓扑学用在计算机领域的“搜索”中时,需要与其它技术配合使用。
目前应用最广的拓扑数据结构是哈斯图。在计算机科学中,哈斯图是一种表示有向无环图的抽象结构。这种结构可以应用于许多问题之中,其中就包括搜索问题。
既然哈斯图这么好用,为什么还要用冗长的“平面网格”来描述地形呢?这是因为真实世界不是拓扑学的世界,它有它的规律,也有它的局限性。
对于地形来说,用哈斯图来模拟现实场景是需要很大成本的,因为每一帧画面都需要重新计算。而且,随着地理范围的扩大,计算量也会呈指数增长。 所以,尽管拓扑学是最完美的数学模型,但它并不能解决所有的问题。在某些情况下,我们不得不牺牲一定的精确度来换取效率。对于地理搜索来说,用平面网格来计算最短路径虽然不够精确,但已经足够快了,所以我们能在线导航,实时获取路况信息。