devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

A* (A Star) 算法 java实现_java astar算法

作者：我家自动化 | 2024-07-04 12:05:29

赞

踩

java astar算法

A*算法（A-star algorithm）是一种常用的启发式搜索算法，用于求解图中两个节点之间的最短路径。A算法综合了Dijkstra算法的广度优先搜索和贪婪最优搜索策略，通过使用估计函数（heuristic function）来指导搜索方向，从而提高搜索效率。

以下是A*算法的详细步骤：

  1. 初始化：将起始节点添加到一个开放列表（open list）中，并将其估计函数值（f值）设置为0。
  2. 循环直到开放列表为空或找到目标节点：
    a. 从开放列表中选择具有最小估计函数值（f值）的节点，将其称为当前节点，并将其移出开放列表。
    b. 如果当前节点是目标节点，则搜索完成，构建最短路径。
    c. 否则，对于当前节点的每个邻居节点：
    • 如果邻居节点不可通过或已在关闭列表中，则忽略它。
    • 如果邻居节点不在开放列表中，则将其添加到开放列表，并计算它的估计函数值（f值）和代价函数值（g值）。
    • 如果邻居节点已经在开放列表中，并且通过当前节点到达它的代价函数值（g值）更小，则更新它的父节点和代价函数值（g值）。
  3. 如果开放列表为空且未找到目标节点，则表示无法到达目标节点，搜索失败。

A*算法使用了一个估计函数来指导搜索，在每次选择下一个节点时，它考虑了两个值：g值和h值。

  • g值表示从起始节点到当前节点的实际代价。
  • h值表示从当前节点到目标节点的估计代价。

A*算法的估计函数f值定义为：f(n) = g(n) + h(n)，其中n是当前节点。f值越小，越有可能是优先考虑的节点。

A*算法的性能和效果取决于所选择的估计函数。一个好的估计函数应该能够提供较为准确的估计值，以便更好地引导搜索，但也需要具备一定的效率，以免过多地增加计算复杂度。

A算法的优点是在适当的估计函数下，能够找到最短路径，并且相对于其他完全搜索算法，它的搜索效率更高。然而，A算法并不能保证一定找到最短路径，且在某些情况下可能会陷入局部最优解。

节点代码

  1. class Node {
  2.     int x; // 节点的x坐标
  3.     int y; // 节点的y坐标
  4.     int g; // 从起始节点到当前节点的实际代价
  5.     int h; // 从当前节点到目标节点的估计代价
  6.     int f; // 估计函数值
  7.     Node parent; // 父节点
  8.  
  9.     public Node(int x, int y) {
  10.         this.x = x;
  11.         this.y = y;
  12.     }
  13.     // 必须重写equals方法
  14.     @Override
  15.     public boolean equals(Object o) {
  16.         if (this == o) return true;
  17.         if (o == null || getClass() != o.getClass()) return false;
  18.         Node node = (Node) o;
  19.         return x == node.x && y == node.y;
  20.     }
  21.     @Override
  22.     public int hashCode() {
  23.         return Objects.hash(x, y);
  24.     }
  25. }

算法实现

  1. public class AStar {
  2.     public static void main(String[] args) {
  3.         int[][] grid = {
  4.                 {0, 0, 0, 0, 0},
  5.                 {1, 1, 0, 1, 0},
  6.                 {0, 0, 0, 0, 0},
  7.                 {0, 1, 1, 1, 1},
  8.                 {0, 0, 0, 0, 0}
  9.         };
  10.  
  11.         Node start = new Node(0, 0);
  12.         Node end = new Node(4, 4);
  13.  
  14.         List<Node> path = findShortestPath(grid, start, end);
  15.  
  16.         if (path != null) {
  17.             for (Node node : path) {
  18.                 System.out.print("(" + node.x + ", " + node.y + ")");
  19.                 System.out.print("-> ");
  20.             }
  21.             System.out.print("end");
  22.         } else {
  23.             System.out.println("No path found");
  24.         }
  25.     }
  26.     public static List<Node> findShortestPath(int[][] grid, Node start, Node end) {
  27.         int rows = grid.length;
  28.         int cols = grid[0].length;
  29.         //创建开放 关闭列表
  30.         List<Node> openList = new ArrayList<>();
  31.         List<Node> closeList = new ArrayList<>();
  32.         //初始化开始节点
  33.         start.g = 0;// 从起始节点到当前节点的实际代价
  34.         start.h = calculateHeuristic(start, end);// 从当前节点到目标节点的估计代价
  35.         start.f = start.g + start.h;
  36.         //添加进开放列表
  37.         openList.add(start);
  38.         //开放列表不为null就一直循环
  39.         while (!openList.isEmpty()) {
  40.             //从开放列表中选f最小的节点
  41.             Node current = getMinimumFValueNode(openList);
  42.             //将当前节点从开放列表中删除
  43.             openList.remove(current);
  44.             //加入关闭列表
  45.             closeList.add(current);
  46.             if (current.equals(end)) {
  47.                 //找到最短路径,回溯到起始节点
  48.                 return buildPath(current);
  49.             }
  50.             //当前节点的邻居节点
  51.             List<Node> neighbors = getNeighbors(current, grid, rows, cols);
  52.             for (Node neighbor : neighbors) {
  53.                 if(closeList.contains(neighbor)){
  54.                     //已访问
  55.                     continue;
  56.                 }
  57.                 //当前节点移动到邻居节点 实际代价为1
  58.                 int tentativeG = current.g+1;
  59.                 // 如果开放列表中没有该几点,或者 存在该几点但是之走前路径的代价较大
  60.                 if(!openList.contains(neighbor)||tentativeG<neighbor.g){
  61.                     neighbor.parent = current;
  62.                     neighbor.g = tentativeG;
  63.                     neighbor.h = calculateHeuristic(neighbor,end);
  64.                     neighbor.f=neighbor.g+neighbor.h;
  65.                     //已经在里面 就不要添加了
  66.                     if(!openList.contains(neighbor)){
  67.                         openList.add(neighbor);
  68.                     }
  69.                 }
  70.             }
  71.  
  72.         }
  73.         return null; //无法找到最短路径
  74.     }
  75.     // 计算预估代价
  76.     private static int calculateHeuristic(Node current, Node end) {
  77.         // 使用曼哈顿距离作为估计函数
  78.         return Math.abs(current.x - end.x) + Math.abs(current.y - end.y);
  79.     }
  80.     // 得到列表中 f  最小的节点
  81.     private static Node getMinimumFValueNode(List<Node> nodes) {
  82.         int minF = Integer.MAX_VALUE;
  83.         Node minNode = null;
  84.         for (Node node : nodes) {
  85.             if (node.f < minF) {
  86.                 minF = node.f;
  87.                 minNode = node;
  88.             }
  89.         }
  90.         return minNode;
  91.     }
  92.     // 通过节点的parent 构建出路径
  93.     private static List<Node> buildPath(Node node) {
  94.         List<Node> path = new ArrayList<>();
  95.         while (node != null) {
  96.             path.add(0, node);
  97.             node = node.parent;
  98.         }
  99.         return path;
  100.     }
  101.     // 得到邻居节点列表
  102.     private static List<Node> getNeighbors(Node node, int[][] grid, int rows, int cols) {
  103.         List<Node> neighbors = new ArrayList<>();
  104.         int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
  105.         for (int[] direction : directions) {
  106.             int newX = node.x + direction[0];
  107.             int newY = node.y + direction[1];
  108.             if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 0) {
  109.                 // 邻居节点在有效范围内且不是障碍物
  110.                 Node neighbor = new Node(newX, newY);
  111.                 neighbors.add(neighbor);
  112.             }
  113.         }
  114.         return neighbors;
  115.     }
  116. }

使用优先队列

  1. public class AStarPriority {
  2.  
  3.     public static void main(String[] args) {
  4.         int[][] grid = {
  5.                 {0, 0, 0, 0, 0},
  6.                 {1, 1, 0, 1, 0},
  7.                 {0, 0, 0, 0, 0},
  8.                 {0, 1, 1, 1, 1},
  9.                 {0, 0, 0, 0, 0}
  10.         };
  11.  
  12.         Node start = new Node(0, 0);
  13.         Node end = new Node(4, 4);
  14.  
  15.         List<Node> path = findShortestPath(grid, start, end);
  16.  
  17.         if (path != null) {
  18.             for (Node node : path) {
  19.                 System.out.print("(" + node.x + ", " + node.y + ")");
  20.                 System.out.print("-> ");
  21.             }
  22.             System.out.print("end");
  23.         } else {
  24.             System.out.println("No path found");
  25.         }
  26.     }
  27.  
  28.  
  29.     public static List<Node> findShortestPath(int[][] grid, Node start, Node end) {
  30.         int rows = grid.length;
  31.         int cols = grid[0].length;
  32.         //优先队列
  33.         PriorityQueue<Node> queue = new PriorityQueue<>(rows + cols, Comparator.comparingInt(o -> o.f));
  34.         //已访问的节点
  35.         Set<Node> visited = new HashSet<>(rows + cols);
  36.         //处理开始节点
  37.         start.g = 0; //开始几点到当前节点的代价
  38.         start.h = guess(start, end); //猜测当前节点到终点的代价
  39.         //计算的代价
  40.         start.f = start.g + start.h;
  41.         //将当前节点添加到优先队列中
  42.         queue.offer(start);
  43.         while (!queue.isEmpty()) {
  44.             //代价最小(f最小)的节点出队列
  45.             Node current = queue.poll();
  46.             //将当前节点加入 已访问
  47.             visited.add(current);
  48.             //如果当前节点等于end
  49.             if (current.equals(end)) {
  50.                 //找到了
  51.                 return buildPath(current);
  52.             }
  53.             //当前节点的邻居
  54.             List<Node> neighbors = currentNeighbors(current, grid, rows, cols);
  55.             //遍历邻居
  56.             for (Node neighbor : neighbors) {
  57.                 //访问过 就跳过
  58.                 if (visited.contains(neighbor))
  59.                     continue;
  60.                 //从当前节点到邻居 花费代价1
  61.                 int tentativeG = current.g + 1;
  62.                 //如果当前节点没有在队列中 或者 当前路径代价更小
  63.                 if (!queue.contains(neighbor) || tentativeG < neighbor.g) {
  64.                     //更新邻居节点
  65.                     neighbor.parent = current;
  66.                     neighbor.g = tentativeG;
  67.                     neighbor.h = guess(neighbor, end);
  68.                     neighbor.f = neighbor.g + neighbor.h;
  69.                     if(!queue.contains(neighbor)){
  70.                         queue.offer(neighbor);
  71.                     }
  72.                 }
  73.             }
  74.         }
  75.         return null;
  76.     }
  77.  
  78.     private static List<Node> currentNeighbors(Node current, int[][] grid, int rows, int cols) {
  79.         //上下左右4个方向
  80.         int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  81.         List<Node> neighbors = new ArrayList<>();
  82.         for (int[] d : dir) {
  83.             int nx = current.x + d[0];//下一个几点的x
  84.             int ny = current.y + d[1];//下一个几点的y
  85.             //是否合法
  86.             if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == 1)
  87.                 continue;
  88.             neighbors.add(new Node(nx, ny));
  89.         }
  90.         return neighbors;
  91.     }
  92.  
  93.     private static List<Node> buildPath(Node current) {
  94.         List<Node> path = new ArrayList<>();
  95.         Node temp = current;
  96.         while (temp != null) {
  97.             path.add(0,temp);
  98.             temp = temp.parent;
  99.         }
  100.         return path;
  101.     }
  102.  
  103.     private static int guess(Node current, Node end) {
  104.         //当前节点到终点的曼哈顿距离: 曼哈顿距离比直线距离好算,不用开方
  105.         return Math.abs(current.x - end.x) + Math.abs(current.y - end.y);
  106.     }
  107. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/786746
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号