地图持续为您导航，我**的给我带到山沟里了。这里有张地图，只有我家和SaSa讲知识办公室让你画路线图，你两点之间直接一条线段，很简单对吧？假如这时候中间突然长了一个池塘，你知道要去绕道，从左绕和从右绕都可以，但是我们更喜欢走右边，因为路短。
那么如果给人工智能，它是怎么选的？首先，路很多，左边能走，右边也能走，两个一起走同时考虑一下，这个叫做广度优先寻路算法。但是往里面走越里面路叉越来越多，因为广度优先，所以所有的路叉都要同时考虑，内存占用很大。另一个算法，一头走到底，叫深度优先寻路算法。
你别以为这么简单，首先绕远路我们不说，但是走进死胡同，咋办？这里以深度优先为例，又要换路。接下来是dijkstra算法，就是根据代价找到最短路径。注意这里的代价可能是时间，路程。
例如这张地图，这里将路程作为代价，从起点走到第一个岔路口，发现路程为1，然后若要休息，需要去凉亭，到凉亭的路程为1，所以从起点到凉亭的最小路程为2。休息好后，从凉亭到另一个岔路口路程为2，但是从起点到这个岔路口的最小路程为4吗？不是，下面还有一条更近的路，从起点到另一个岔路口的最小路程为3，所以从这个到终点的最小路程为4。在不休息的情况下，走下面这条路。
接下来是更好的A*算法，这个是星号，它的评估公式是f(x)=g(x)+h(x)，其中g是起点到达该点点的代价(口误)，这里用走了多远代替，h这里用到终点的路程代替。其中h有很多种距离计算函数，有欧几里得，曼哈顿距离等。这两种距离如图所示。
当在选择路线时，会选择f值更小的路线。如解算这张地图时，从起点走到第一个岔路口，然后选择路，从上面走预计的f比从下面走更大，所以从下面走过去更好。在实际运算中要算每个岔路口的f值来选出最好的。
这些寻路算法可以用在导航地图规划GIS引擎里，以及玩的游戏中的非玩家角色。但是实际上还要考虑在导航中总不能开车上火车线路上。
SaSa讲知识，让世界充满爱。SaSa talk knowledge，let the future full of love。