Java 剪枝搜索

剪枝搜索（Pruning Search）是一种优化搜索算法的技术，它通过减少搜索空间的大小来提高搜索效率。在解决诸如路径查找、决策制定和组合优化等问题时，剪枝搜索显得尤为重要。Java 语言中，你可以实现各种剪枝搜索算法，如深度优先搜索（DFS）、广度优先搜索（BFS）以及 A*（A-star）等，并在这些算法中融入剪枝策略。

以下是一个简单的 Java 示例，展示如何在深度优先搜索（DFS）中应用剪枝策略。在这个例子中，我们假设要在一个二维网格中找到从左上角到右下角的路径，且路径只能向右或向下移动。

public class GridPruningDFS {  
  
    static class Point {  
        int x, y;  
        Point(int x, int y) {  
            this.x = x;  
            this.y = y;  
        }  
    }  
  
    public static boolean isSafe(int[][] grid, Point pt, int n, int m) {  
        return pt.x >= 0 && pt.x < n && pt.y >= 0 && pt.y < m && grid[pt.x][pt.y] == 1;  
    }  
  
    public static boolean isGoal(Point pt, int n, int m) {  
        return pt.x == n - 1 && pt.y == m - 1;  
    }  
  
    public static boolean solveDFSUtil(int[][] grid, Point pt, boolean[][] visited, int n, int m) {  
        if (isGoal(pt, n, m)) {  
            return true;  
        }  
  
        // Mark the current cell as visited  
        visited[pt.x][pt.y] = true;  
  
        // Define all 4 possible moves: right, left, down, up  
        int[][] dr = {{0, 1}, {1, 0}};  
  
        // Try all 4 directions  
        for (int[] d : dr) {  
            Point newPt = new Point(pt.x + d[0], pt.y + d[1]);  
  
            // If move is safe and not visited, then move to this cell  
            if (isSafe(grid, newPt, n, m) && !visited[newPt.x][newPt.y]) {  
                // Recur to continue search  
                if (solveDFSUtil(grid, newPt, visited, n, m)) {  
                    return true;  
                }  
            } else if (!isSafe(grid, newPt, n, m)) {  
                // If move is unsafe (blocked cell), prune this branch  
                // This is the pruning step  
                continue;  
            }  
        }  
  
        // If none of the moves work out, backtrack  
        visited[pt.x][pt.y] = false;  
        return false;  
    }  
  
    public static boolean solveDFS(int[][] grid, int n, int m) {  
        boolean[][] visited = new boolean[n][m];  
        Point start = new Point(0, 0);  
        return solveDFSUtil(grid, start, visited, n, m);  
    }  
  
    public static void main(String[] args) {  
        int[][] grid = {  
            {1, 1, 0, 1},  
            {1, 1, 1, 1},  
            {0, 1, 1, 1},  
            {1, 0, 0, 1}  
        };  
  
        int n = grid.length;  
        int m = grid[0].length;  
  
        if (solveDFS(grid, n, m)) {  
            System.out.println("There is a path from top-left to bottom-right");  
        } else {  
            System.out.println("There is no path from top-left to bottom-right");  
        }  
    }  
}

解释

1. isSafe 方法：检查给定的点是否在网格内且可通行（值为1）。
2. isGoal 方法：检查是否到达目标点（右下角）。
3. solveDFSUtil 方法：递归地尝试从当前点移动到下一个点，并使用剪枝策略。如果下一个点不可通行（值为0），则跳过该方向，不继续递归。
4. solveDFS 方法：初始化访问数组，并从起点开始调用递归辅助方法。
5. main 方法：定义了一个示例网格，并调用 solveDFS 方法来查找路径。

在这个例子中，剪枝策略体现在 if (!isSafe(grid, newPt, n, m)) { continue; } 这一行。如果下一个点不可通行，则直接跳过该方向，不再继续递归，从而减少了不必要的搜索。

你可以根据具体问题的需求，进一步调整和扩展这个剪枝策略。