深搜&广搜

Finlabtech

定义

深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。简单来说，其搜索过程和 “不撞南墙不回头” 类似[1]。
广度优先搜索算法（Breadth-First-Search，缩写为 BFS），是一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似[2]。

应用

这两种算法用途都非常广泛，比如走迷宫是一种很常见的搜索算法的应用。网上介绍这两种算法的文章也非常多，这里我也不多废话，而且我表述的也不一定准确。这里给两个例子吧，在看《啊哈算法》的时候书中抛出的两个问题，正好是通过BFS&DFS解决的。

打印1-9的全排列

public class DFS {
    //标记已经使用了的数字
    private static int[] book;
    //符合条件的排列数
    private static int[] a;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        book = new int[N+1];
        a = new int[N+1];
        //从第一位开始
        dfs(1, N);
    }
    private static void dfs(int n, int N) {
        if(n==N+1) {
            for(int i=1; i<N+1; i++) {
                System.out.print(a[i]);
            }
            System.out.println("");
            return;
        }
        for(int i=1; i<N+1; i++) {
            if(book[i] == 0) {
                a[n] = i;
                book[i] = 1;
                dfs(n+1, N);
                //这一句太重要了!但是很难理解啊。
                book[i] = 0;
            }
        }
    }
}

走迷宫

public class BFS {
    //记录已经被扫描到的节点
    private Queue<Node> queue = new LinkedList<>();
    private List<Node> already = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int xLength = sc.nextInt();
        int yLength = sc.nextInt();
        //0表示通,1表示不通
        int[][] maze = new int[xLength][yLength];
        for(int i=0;i<xLength;i++) {
            for(int j=0;j<yLength;j++) {
                maze[i][j] = sc.nextInt();
            }
        }
        Node startNode = new Node(sc.nextInt(), sc.nextInt());
        Node targetNode = new Node(sc.nextInt(), sc.nextInt());
        BFS bfs = new BFS();
        bfs.bfs(maze, startNode, targetNode);
    }
    private void bfs(int[][] maze, Node startNode, Node targetNode) {
        List<Node> neighbors = getNeighbor(startNode, maze);
        for(Node node : neighbors) {
            queue.offer(node);
        }
        while(!queue.isEmpty()) {
            Node next = queue.poll();
            if(already.contains(next)) {
                System.out.println("已走过!");
            } else {
                already.add(next);
                if(next.getX()==targetNode.getX() && next.getY()==targetNode.getY()) {
                    System.out.println("走到了(" + next.getX() + ", " + next.getY() + ")这个点,结束");
                    break;
                } else {
                    System.out.println("走到了(" + next.getX() + ", " + next.getY() + ")这个点");
                    neighbors = getNeighbor(next, maze);
                    for(Node node : neighbors) {
                        queue.offer(node);
                    }
                }
            }
        }
    }
    /**
     * 或者每个节点的临近节点
     * @param a
     * @param maze
     * @return
     */
    private List<Node> getNeighbor(Node a, int[][] maze) {
        List<Node> neighbors = new ArrayList<>();
        int[][] path = new int[][]{{1,0}, {0,1}, {-1,0}, {0, -1}};
        for(int i=0; i<path.length; i++) {
            Node next = march(a, path[i]);
            if(next.getX() >=0 && next.getX() < maze.length && next.getY() >=0 && next.getY() < maze.length) {
                if(maze[next.getX()][next.getY()] == 0) {
                    neighbors.add(next);
                }
            }
        }
        return neighbors;
    }
    /**
     * 定义上下左右的走法
     * @param source
     * @param path
     * @return
     */
    private Node march(Node source, int[] path) {
        return new Node(source.getX()+path[0], source.getY()+path[1]);
    }
}
class Node {
    int x;
    int y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    int getX() {
        return x;
    }
    int getY() {
        return y;
    }
    void setY(int y) {
        this.y = y;
    }
    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof Node)) {
            return false;
        }
        Node node = (Node) o;
        if(node.getX() == x && node.getY() == y) {
            return true;
        } else {
            return false;
        }
    }
}

总结

最后，截取我看到的一段总结放在最后，慢慢理解[3]。

搜索与DP，贪心，分治的共同点在于状态的转移，只不过在搜索中，一个阶段的最优状态是由之前所有状态得到的，这是其余其他算法的区别之处。
状态的转移即由某一个不同的状态转移至另一个不同的状态，DFS在于从一个初始状态出发，一直转移状态直到搜到目标或搜到状态无法进行转移为止，其中的剪枝便是通过应题目具体要求和仔细分析而去掉某些没必要或不存在的状态以节约时间和空间，而BFS在于一层一层地扩展状态,这样首先找到的目标便一定是用时或步数最少的。DFS几乎适用于所有情况，因为这本身是一种遍历所有状态的搜索，只不过在寻找最小步或最小时间的情况下比较慢，无法快速找到目标，但在程序世界里DFS本身也有不适用的情况，如果状态没有下限即转移的深度没有下限那么便无法深搜，同样，BFS也可能存在一层状态都扩展不完的情况，这样便才会有迭代加深搜索等扩展搜索的出现，它结合了两者的优点且实际应用效果不错。紫书上面的名词“解答树”便很好地描述了所有状态转移的过程，当然这个似乎与我们无关，但是其实也是一种刻画搜索过程的有利工具。