| 图：两点之间的最短距离 | 您所在的位置：网站首页 › 路途的图怎么写 › 图：两点之间的最短距离 |
图：两点之间的最短距离
|
文章出处：极客时间《数据结构和算法之美》-作者：王争。该系列文章是本人的学习笔记。 1 问题阐述像 Google 地图、百度地图、高德地图这样的地图软件，如果想从家开车到公司，你只需要输入起始、结束地址，地图就会给你规划一条最优出行路线。这里的最优，有很多种定义，比如最短路线、最少用时路线、最少红绿灯路线等等。我们先解决最简单的，最短路线。 2 算法解析解决软件开发中的实际问题，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。想要解决这个问题，有一个非常经典的算法，最短路径算法，更加准确地说，是单源最短路径算法（一个顶点到一个顶点）。提到最短路径算法，最出名的莫过于 Dijkstra 算法了。 package homework.graphdelete; import java.util.Arrays; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; /** * 有向有权图 */ public class DirectedGraph { private int v;//顶点数量 private LinkedList adj[]; public DirectedGraph(int v){ this.v = v; adj = new LinkedList[v]; for(int i=0;i this.addEdge(sid,tid,1); } public void addEdge(int sid,int tid,int weight){ Edge edge = new Edge(sid,tid,weight); adj[sid].add(edge); } /** * 计算从s到t的最短路径 * bfs * @param s * @param t */ public void dijkstrala(int s,int t){ Vertex[] vertexes = new Vertex[v]; for(int i=0;i Vertex vertex = queue.poll(); if(vertex.id == t){ break; } for(int j = 0;j predecessor[edge.tid] = vertex.id; to.distance = vertex.distance + edge.weight; if(inqueue[to.id]){ queue.remove(to); queue.offer(to); }else{ queue.offer(to); inqueue[to.id] = true; } } } } printPath(predecessor,t); } private void printPath(int[] pre,int nowNode){ if(pre[nowNode]!=-1){ printPath(pre,pre[nowNode]); } System.out.print(nowNode+" "); } class Edge{ private int sid; private int tid; private int weight; public Edge(int sid,int tid,int weight){ this.sid = sid; this.tid = tid; this.weight = weight; } } class Vertex implements Comparable{ private int id; private int distance;//从起始点到当前点的距离 public Vertex(int id,int distance){ this.id = id; this.distance = distance; } @Override public int compareTo(Vertex o) { return this.distance - o.distance; } } }我们用 vertexes 数组，记录从起始顶点到每个顶点的距离（dist）。起初，我们把所有顶点的 dist 都初始化为无穷大（也就是代码中的 Integer.MAX_VALUE）。我们把起始顶点的 dist 值初始化为 0，然后将其放到优先级队列中。我们从优先级队列中取出 dist 最小的顶点 minVertex，然后考察这个顶点可达的所有顶点（代码中的 nextVertex）。如果 minVertex 的 dist 值加上 minVertex 与 nextVertex 之间边的权重 w 小于 nextVertex 当前的 dist 值，也就是说，存在另一条更短的路径，它经过 minVertex 到达 nextVertex。那我们就把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w。然后，我们把 nextVertex 加入到优先级队列中。重复这个过程，直到找到终止顶点 t 或者队列为空。 时间复杂度计算：队列操作，队列中节点个数不会超过V。入队操作复杂度是O(logV)。在顶点重复插入的时候会有一个删除操作，时间复杂度O(V)。所有引起入队或者删除操作都是因为遍历到边，所有次数不会超过边的个数。总体时间复杂度最坏情况O(EV) ，最优情况O(E logV)。 3 A星算法实际上，像出行路线规划、游戏寻路，这些真实软件开发中的问题，一般情况下，我们都不需要非得求最优解（也就是最短路径）。在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢？ 这个快速的路径规划算法，就是我们今天要学习的 A* 算法。实际上，A* 算法是对 Dijkstra 算法的优化和改造。 Dijkstra 算法有点儿类似 BFS 算法，它每次找到跟起点最近的顶点，往外扩展。这种往外扩展的思路，其实有些盲目。为什么这么说呢？我举一个例子来给你解释一下。下面这个图对应一个真实的地图，每个顶点在地图中的位置，我们用一个二维坐标（x，y）来表示，其中，x 表示横坐标，y 表示纵坐标。 在 Dijkstra 算法的实现思路中，我们用一个优先级队列，来记录已经遍历到的顶点以及这个顶点与起点的路径长度。顶点与起点路径长度越小，就越先被从优先级队列中取出来扩展，从图中举的例子可以看出，尽管我们找的是从 s 到 t 的路线，但是最先被搜索到的顶点依次是 1，2，3。通过肉眼来观察，这个搜索方向跟我们期望的路线方向（s 到 t 是从西向东）是反着的，路线搜索的方向明显“跑偏”了。之所以会“跑偏”，那是因为我们是按照顶点与起点的路径长度的大小，来安排出队列顺序的。与起点越近的顶点，就会越早出队列。我们并没有考虑到这个顶点到终点的距离，所以，在地图中，尽管 1，2，3 三个顶点离起始顶点最近，但离终点却越来越远。如果我们综合更多的因素，把这个顶点到终点可能还要走多远，也考虑进去，综合来判断哪个顶点该先出队列，那是不是就可以避免“跑偏”呢？ 我们设计一个函数用于估算当前节点到终点的距离。这个函数又被称为启发函数。计算两点之间的距离可以用欧几里得距离，但是欧几里得距离需要开平方，计算量大，使用曼哈顿距离代替。 A星算法与dijkstra算法不同地方在于： 1 队列中按照f值（综合计算值）排序 2 退出条件不一样，在循环中遇到终点就退出（不用查找最优路径） 3 在更新顶点dist的时候，会同步更新f值。 测试代码与实现 |
【本文地址】