数据结构与算法 / 系统课时

回溯搜索的决策树

回溯搜索的决策树

回溯用于系统尝试多条候选路径:做出选择、递归深入,失败后恢复现场再试其他分支。本课以迷宫寻路为主示例,明确决策树、路径、候选选择和撤销操作之间的关系。

学习目标

  • 把搜索过程抽象为决策树
  • 掌握做选择、递归与撤销选择的顺序
  • 使用访问状态避免当前路径形成环

决策树中的三个要素

决策树的节点表示当前状态,边表示一次选择,叶子表示完整答案或无法继续的失败状态。实现回溯前,需要先回答三个问题:当前路径记录什么、当前有哪些合法选择、何时得到答案或结束分支。

回溯可看作带“现场恢复”的深度优先搜索。共享的 path 和 visited 会被每层递归修改,因此递归返回后必须撤销本层修改,保证兄弟分支从相同父状态出发。

迷宫回溯的决策树与状态恢复

主示例:寻找一条迷宫路径

下面的 Java 17 程序在 0 表示可通行、1 表示障碍的迷宫中寻找一条路径。找到终点后直接返回 true,因此保留成功路径;只有当前分支失败时才执行撤销。

java
import java.util.ArrayList;
import java.util.List;

public class BacktrackingDecisionTreeDemo {

    private static final int[][] MAZE = {
        {0, 0, 1, 0, 0},
        {1, 0, 1, 0, 1},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0}
    };

    private static final int[][] DIRECTIONS = {
        {1, 0}, {0, 1}, {-1, 0}, {0, -1}
    };

    public static void main(String[] args) {
        boolean[][] visited =
            new boolean[MAZE.length][MAZE[0].length];
        List<Position> path = new ArrayList<>();

        boolean found = search(0, 0, visited, path);
        System.out.println("found = " + found);
        System.out.println("path = " + path);
    }

    private static boolean search(
        int row,
        int column,
        boolean[][] visited,
        List<Position> path
    ) {
        if (!isAvailable(row, column, visited)) {
            return false;
        }

        // 做选择:把当前位置加入当前分支。
        visited[row][column] = true;
        path.add(new Position(row, column));

        if (row == MAZE.length - 1
            && column == MAZE[0].length - 1) {
            return true;
        }

        for (int[] direction : DIRECTIONS) {
            int nextRow = row + direction[0];
            int nextColumn = column + direction[1];
            if (search(nextRow, nextColumn, visited, path)) {
                return true;
            }
        }

        // 当前分支失败,恢复进入本层前的状态。
        path.remove(path.size() - 1);
        visited[row][column] = false;
        return false;
    }

    private static boolean isAvailable(
        int row,
        int column,
        boolean[][] visited
    ) {
        return row >= 0
            && row < MAZE.length
            && column >= 0
            && column < MAZE[0].length
            && MAZE[row][column] == 0
            && !visited[row][column];
    }

    private record Position(int row, int column) {
    }
}

预期输出:

text
found = true
path = [Position[row=0, column=0], Position[row=0, column=1], Position[row=1, column=1], Position[row=2, column=1], Position[row=2, column=2], Position[row=2, column=3], Position[row=2, column=4], Position[row=3, column=4]]

方向顺序会影响首先找到的路径,但不会改变“是否存在路径”的结论。

状态恢复与问题目标

寻找任意一条路径时,成功后可立即返回,不必撤销成功分支。若要收集全部路径,到达终点时应复制当前路径保存,然后继续撤销并搜索其他分支。

visited 在本例中表示“当前路径是否包含该位置”,因此回溯时要清除。若问题语义是“全局只访问一次”,则访问标记可能不应恢复;是否撤销取决于状态属于当前分支还是整个搜索过程。

边界与复杂度

四方向迷宫若允许回退,未使用 visited 会在相邻格子间循环。最坏情况下,回溯可能探索大量简单路径,时间复杂度呈指数增长;路径与递归栈最多包含 m × n 个位置,空间复杂度为 O(m × n)。

实现时应先判断越界、障碍和已访问,再修改路径。撤销顺序要与做选择相反,避免路径和访问状态不一致。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

回溯搜索的决策树

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通