网站定位与功能分析,在互联网公司做网站,共同建设网站协议,下载建设银行官方网站下载安装算法解析
这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置#xff0c;终点就是鼠标点击的位置。我们需要在地图中#xff0c;找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物#xff0c;并且看起来要是一种非常聪明的走法。所谓“聪明”#xff0…算法解析
这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置终点就是鼠标点击的位置。我们需要在地图中找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物并且看起来要是一种非常聪明的走法。所谓“聪明”笼统地解释就是走的路不能太绕。理论上讲最短路径显然是最聪明的走法是这个问题的最优解。
实际上像出行路线规划、游戏寻路这些真实软件开发中的问题一般情况下都不需要非得求最优解也就是最短路径。 在权衡路线规划质量和执行效率的情况下我们只需要寻求一个次优解就足够了。 如何快速找出一条接近于最短路线的次优路线呢 A 算法*A* 算法是对 Dijkstra 算法的优化和改造。最优出行路线规划问题中如果图非常大Dijkstra 最短路径算法的执行耗时会很多 Dijkstra 算法有点儿类似 BFS 算法它每次找到跟起点最近的顶点往外扩展。这种往外扩展的思路其实有些盲目。
可以避免“跑偏”吗
当遍历到某个顶点时从起点到这个顶点的路径长度是确定的记作 g(i)i 表示顶点编号
虽然从这个顶点到终点的路径长度是未知的但可以用其他估计值来代替。可以通过这个顶点跟终点之间的直线距离(欧几里得距离)近似估算这个顶点跟终点的路径长度注意路径长度跟直线距离是两个概念把这个距离记作 h(i)i 表示这个顶点的编号专业的叫法是启发函数heuristic function。因为欧几里得距离的计算公式会涉及比较耗时的开根号计算所以一般通过另外一个更加简单的距离计算公式那就是曼哈顿距离Manhattan distance。曼哈顿距离是两点之间横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转所以比欧几里得距离更加高效。
原来只是单纯地通过顶点与起点之间的路径长度 g(i)来判断谁先出队列现在有了顶点到终点的路径长度估计值通过两者之和 f(i)g(i)h(i)来判断哪个顶点该最先出队列。 综合两部分就能有效避免“跑偏”。f(i) 的专业叫法是估价函数evaluation function
** A 算法就是对 Dijkstra 算法的简单改造* 在 A* 算法的代码实现中顶点 Vertex 类的定义跟 Dijkstra 算法中的定义稍微有点儿区别多了 xy 坐标以及刚刚提到的 f(i) 值。图 Graph 类的定义跟 Dijkstra 算法中的定义一样。 private class Vertex {public int id; // 顶点编号IDpublic int dist; // 从起始顶点到这个顶点的距离也就是g(i)public int f; // 新增f(i)g(i)h(i)public int x, y; // 新增顶点在地图中的坐标x, ypublic Vertex(int id, int x, int y) {this.id id;this.x x;this.y y;this.f Integer.MAX_VALUE;//!!!this.dist Integer.MAX_VALUE;}
}
// Graph类的成员变量在构造函数中初始化
Vertex[] vertexes new Vertex[this.v];
// 新增一个方法添加顶点的坐标
public void addVetex(int id, int x, int y) {vertexes[id] new Vertex(id, x, y)
}A* 算法的代码主要有 3 点区别 优先级队列构建的方式不同 A* 算法是根据 f 值 f(i)g(i)h(i)来构建优先级队列 Dijkstra 算法是根据 dist 值g(i)来构建优先级队列 A* 算法在更新顶点 dist 值的时候会同步更新 f 值 循环结束的条件也不一样。Dijkstra 算法是在终点出队列的时候才结束A* 算法是一旦遍历到终点就结束。 public void astar(int s, int t) { // 从顶点s到顶点t的路径int[] predecessor new int[this.v]; // 用来还原路径// 按照vertex的f值构建的小顶堆而不是按照distPriorityQueue queue new PriorityQueue(this.v);boolean[] inqueue new boolean[this.v]; // 标记是否进入过队列vertexes[s].dist 0;vertexes[s].f 0;queue.add(vertexes[s]);inqueue[s] true;while (!queue.isEmpty()) {Vertex minVertex queue.poll(); // 取堆顶元素并删除for (int i 0; i adj[minVertex.id].size(); i) {Edge e adj[minVertex.id].get(i); // 取出一条minVetex相连的边Vertex nextVertex vertexes[e.tid]; // minVertex--nextVertexif (minVertex.dist e.w nextVertex.dist) { // 更新next的dist,fnextVertex.dist minVertex.dist e.w;nextVertex.f nextVertex.disthManhattan(nextVertex, vertexes[t]);predecessor[nextVertex.id] minVertex.id;if (inqueue[nextVertex.id] true) {queue.update(nextVertex);} else {queue.add(nextVertex);inqueue[nextVertex.id] true;}}if (nextVertex.id t) { // 只要到达t就可以结束while了queue.clear(); // 清空queue才能推出while循环break; }}}// 输出路径System.out.print(s);print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
}
A 这是为什么不能找到最短路线呢* 要找出起点 s 到终点 t 的最短路径最简单的方法是通过回溯穷举所有从 s 到达 t 的不同路径然后对比找出最短的那个。但回溯算法的执行效率非常低是指数级的。
Dijkstra 算法在此基础之上利用动态规划的思想对回溯搜索进行了剪枝只保留起点到某个顶点的最短路径继续往外扩展搜索。动态规划相较于回溯搜索只是换了一个实现思路但它实际上也考察到了所有从起点到终点的路线所以才能得到最优解。
A* 算法之所以不能像 Dijkstra 算法那样找到最短路径主要原因是两者的 while 循环结束条件不一样Dijkstra 算法是在终点出队列的时候才结束A* 算法是一旦遍历到终点就结束对于 Dijkstra 算法当终点出队列时终点的 dist 值是优先级队列中所有顶点的最小值即便再运行下去终点的 dist 值也不会再被更新了。对于 A* 算法一旦遍历到终点我们就结束 while 循环这个时候终点的 dist 值未必是最小值。A* 算法利用贪心算法的思路每次都找 f 值最小的顶点出队列一旦搜索到终点就不在继续考察其他顶点和路线了。
所以它并没有考察所有的路线也就不可能找出最短路径了。
笔记整理来源 王争 数据结构与算法之美
