网站建设毕业设计个人总结,网站建设现状调查研究,杭州网站排名服务,搭建网站教学文章目录 一、A星算法简介二、A星算法思想三、A星算法 java代码四、测试 一、A星算法简介
A*算法是一种静态路网中求解最短路径最有效的直接搜索方法#xff0c;也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近#xff0c;最终搜索速度越快。 二、A星算… 文章目录 一、A星算法简介二、A星算法思想三、A星算法 java代码四、测试 一、A星算法简介
A*算法是一种静态路网中求解最短路径最有效的直接搜索方法也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近最终搜索速度越快。 二、A星算法思想
A星A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法之后涌现了很多预处理算法如CH在线查询效率是A*算法的数千甚至上万倍。
A*算法通过下面这个函数来计算每个节点的优先级 f ( n ) f(n) f(n) 越小状态 n n n 被选择的优先级就越大
公式表示为 f ( n ) g ( n ) h ′ ( n ) f(n)g(n)h(n) f(n)g(n)h′(n), f ( n ) f(n) f(n) 是从初始状态经由状态 n n n 到目标状态的最小代价估计 g ( n ) g(n) g(n) 是在状态空间中从初始状态到状态 n n n 的最小代价 h ′ ( n ) h(n) h′(n) 是从状态 n n n 到目标状态的路径的最小估计代价。对于路径搜索问题状态就是图中的节点代价就是距离
假设 h ( n ) h(n) h(n) 为状态 n n n 到目标状态的路径的最小真实代价。
则保证找到最短路径最优解的条件关键在于估价函数 f ( n ) f(n) f(n) 的选取或者说 h ′ ( n ) h(n) h′(n) 的选取。
以 h ′ ( n ) h(n) h′(n) 表达状态 n n n 到目标状态估计的距离那么 h ′ ( n ) h(n) h′(n) 的选取大致有如下三种情况
如果 h ′ ( n ) h ( n ) h(n) h(n) h′(n)h(n) 这种情况下搜索的点数多搜索范围大效率低。但能得到最优解。如果 h ′ ( n ) h ( n ) h(n)h(n) h′(n)h(n) 此时的搜索效率是最高的。如果 h ′ ( n ) h ( n ) h(n)h(n) h′(n)h(n) 搜索的点数少搜索范围小效率高但不能保证得到最优解。 三、A星算法 java代码
Data
public class AStar {// 0是路 1是墙 2是起点 3是终点private int[][] map;// 起点坐标int startI;int startJ;// 终点坐标int endI;int endJ;public AStar(int[][] map) {this.map map;// 获取起点和终点坐标for (int i 0; i map.length; i) {for (int j 0; j map[i].length; j) {if(map[i][j]2){startI i;startJ j;}if(map[i][j]3){endI i;endJ j;}}}}public void solve(){boolean[][] active new boolean[map.length][map[0].length];PriorityBlockingQueueNode priorityBlockingQueue new PriorityBlockingQueue();// 从起点出发ArrayListint[] initPath new ArrayList();initPath.add(new int[]{startI,startJ});priorityBlockingQueue.add(new Node(startI,startJ,initPath,caculateDistance(startI,startJ)));active[startJ][startJ] true;// 开始循环while (!priorityBlockingQueue.isEmpty()){Node node priorityBlockingQueue.poll();if(node.getI()endI node.getJ()endJ){for (int[] p : node.getPath()) {System.out.println(Arrays.toString(p));}System.out.println(最短路长度为node.getPath().size());break;}// 向四周进行扩充// 上int i1 node.getI()-1;int j1 node.getJ();if(isAble(i1,j1,active)){ArrayListint[] path new ArrayList(node.getPath());path.add(new int[]{i1,j1});priorityBlockingQueue.add(new Node(i1,j1,path,caculateDistance(i1,j1)));active[i1][j1] true;}// 下int i2 node.getI()1;int j2 node.getJ();if(isAble(i2,j2,active)){ArrayListint[] path new ArrayList(node.getPath());path.add(new int[]{i2,j2});priorityBlockingQueue.add(new Node(i2,j2,path,caculateDistance(i2,j2)));active[i2][j2] true;}// 左int i3 node.getI();int j3 node.getJ()-1;if(isAble(i3,j3,active)){ArrayListint[] path new ArrayList(node.getPath());path.add(new int[]{i3,j3});priorityBlockingQueue.add(new Node(i3,j3,path,caculateDistance(i3,j3)));active[i3][j3] true;}// 右int i4 node.getI();int j4 node.getJ()1;if(isAble(i4,j4,active)){ArrayListint[] path new ArrayList(node.getPath());path.add(new int[]{i4,j4});priorityBlockingQueue.add(new Node(i4,j4,path,caculateDistance(i4,j4)));active[i4][j4] true;}}}// 判断坐标是否可行private boolean isAble(int i,int j,boolean[][] active){if(i0 || imap.length){return false;}if(j0 || j map[0].length){return false;}if(map[i][j]1 || active[i][j]){return false;}return true;}// 计算距离终点的曼哈顿private int caculateDistance(int i,int j){return Math.abs(i-endI)Math.abs(j-endJ);}DataNoArgsConstructorAllArgsConstructorclass Node implements ComparableNode{int i;int j;Listint[] path;// 距离终点的曼哈顿距离int lenToEnd;Overridepublic int compareTo(Node o) {return Integer.compare(lenToEndpath.size(),o.lenToEndo.path.size());}Overridepublic String toString() {return Node{ i i , j j , lenToEnd lenToEnd };}}
}四、测试
public class Test {public static void main(String[] args) {long start System.currentTimeMillis();int[][] map new int[][]{{1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0},{0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0},{0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},{0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0},{0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},{0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1},{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1},{0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1},{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0},};new AStar(map).solve();System.out.println(用时(System.currentTimeMillis()-start)ms);}
}控制台输出 [1, 4]
[1, 5]
[1, 6]
[1, 7]
[1, 8]
[1, 9]
[2, 9]
[2, 10]
[2, 11]
[3, 11]
[4, 11]
[5, 11]
[6, 11]
[7, 11]
[8, 11]
[9, 11]
[10, 11]
[10, 12]
[11, 12]
[12, 12]
[12, 11]
[13, 11]
[14, 11]
[15, 11]
[16, 11]
[17, 11]
[17, 12]
[17, 13]
[17, 14]
[18, 14]
[19, 14]
[19, 13]
[19, 12]
最短路长度为33
用时6ms上面输出的例如 [1, 4] [1, 5] [1, 6] 的文字代表最短路径从上往下看 即从14点走到15点再从15点走到16点
