数据结构与算法 / 系统课时
回溯搜索的决策树
回溯搜索的决策树
回溯用于系统尝试多条候选路径:做出选择、递归深入,失败后恢复现场再试其他分支。本课以迷宫寻路为主示例,明确决策树、路径、候选选择和撤销操作之间的关系。
学习目标
- 把搜索过程抽象为决策树
- 掌握做选择、递归与撤销选择的顺序
- 使用访问状态避免当前路径形成环
决策树中的三个要素
决策树的节点表示当前状态,边表示一次选择,叶子表示完整答案或无法继续的失败状态。实现回溯前,需要先回答三个问题:当前路径记录什么、当前有哪些合法选择、何时得到答案或结束分支。
回溯可看作带“现场恢复”的深度优先搜索。共享的 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)。
实现时应先判断越界、障碍和已访问,再修改路径。撤销顺序要与做选择相反,避免路径和访问状态不一致。
按自己的节奏,确认真正理解。