A* Search Algorithms in code

A* search Based on BFS, There are four functions are required in A* search: - g: real cost - h: an estimation function from current cost; - h*: real cost in theory; - f = g + h Also, Priority queue is used since we handle shortest estimation at first.

1. leetcod-752: open the lock

   import java.util.*;
   import java.util.stream.Collectors;
   import java.util.stream.Stream;
   
   class Main {
       public int openLock(String[] deadends, String target) {
           if (target == "0000") return 0;
           Set<String> deads = Stream.of(deadends).collect(Collectors.toSet());
           if (deads.contains(target)) return -1;
           PriorityQueue<Astar> q = new PriorityQueue<>(Comparator.comparingInt(Astar::getF));
           q.offer(new Astar("0000", target, 0));
           Set<String> seen = new HashSet<>(List.of("0000"));
           while (!q.isEmpty()) {
               Astar node = q.poll();
               for (String status : node.next()) {
                   if (seen.contains(status) || deads.contains(status)) continue;
                   if (status == target) return node.g + 1;
                   q.offer(new Astar(status, target, node.g + 1));
               }
           }
           return -1;
       }
   }
   
   class Astar {
       int f, g, h;
       String status;
   
       public int getF() {
           return f;
       }
   
       public List<String> next() {
           List<String> list = new ArrayList<>();
           char[] next = status.toCharArray();
           for (int i = 0; i < 4; i++) {
               char num = status.charAt(i);
               next[i] = num == '0' ? '9' : (char) (num - 1);
               list.add(new String(next));
               next[i] = num == '9' ? '0' : (char) (num + 1);
               list.add(new String(next));
               next[i] = num;
           }
           return list;
       }
   
       public Astar(String status, String target, int g) {
           this.g = g;
           h = computeH(status, target);
           f = g + h;
       }
   
       public static int computeH(String status, String target) {
           int ans = 0;
           for (int i = 0; i < 4; i++) {
               int d = Math.abs(status.charAt(i) - target.charAt(i));
               ans += Math.min(d, 10 - d);
           }
           return ans;
       }
   }
   

2. Leetcode-Q-1091 Shortest Path in a Binary Matrix

   import java.util.ArrayList;
   import java.util.List;
   import java.util.PriorityQueue;
   
   class Astar {
       int row;
       int col;
       int g;
       int f;
   
       Astar(int row, int col, int g, int f) {
           this.row = row;   //"this" is required
           this.col = col;
           this.g = g;
           this.f = f;
       }
   }
   
   class Solution {
       private int[][] directions = new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
   
       public int shortestPathBinaryMatrix(int[][] grid) {
           if (grid[0][0] != 0 || grid[grid.length - 1][grid[0].length - 1] != 0) return -1;
           PriorityQueue<Astar> pq = new PriorityQueue<>((a, b) -> a.f - b.f);
           pq.add(new Astar(0, 0, 1, estimateH(0, 0, grid)));
           boolean[][] visited = new boolean[grid.length][grid[0].length];
           while (!pq.isEmpty()) {
               Astar best = pq.remove();
               if (best.row == grid.length - 1 && best.col == grid[0].length - 1) return best.g;
               if (visited[best.row][best.col]) continue;
               visited[best.row][best.col] = true;
               for (int[] nb : getNeighbours(best.row, best.col, grid)) {
                   int neighbourRow = nb[0];
                   int neighbourCol = nb[1];
                   if (visited[neighbourRow][neighbourCol]) continue;
                   int g = best.g + 1;
                   int totalEstimate = g + estimateH(neighbourRow, neighbourCol, grid);
                   pq.add(new Astar(neighbourRow, neighbourCol, g, totalEstimate));
               }
           }
           return -1;
       }
   
       public List<int[]> getNeighbours(int row, int col, int[][] grid) {
           List<int[]> neighbours = new ArrayList<>();
           for (int[] d : directions) {
               int ni = row + d[0];
               int nj = col + d[1];
               if (ni < 0 || ni >= grid.length || nj < 0 || nj >= grid[0].length || grid[row][col] != 0) continue;
               neighbours.add(new int[]{ni, nj});
           }
           return neighbours;
       }
   
       public int estimateH(int row, int col, int[][] grid) {
           int remainingRows = grid.length - row + 1;
           int remainingCols = grid[0].length - col + 1;
           return Math.max(remainingRows, remainingCols);
       }
   
       public static void main(String[] args) {
           System.out.println(new Solution().shortestPathBinaryMatrix(new int[][]{{0, 1}, {1, 0}}) == 2);
       }
   }