编辑“︁回溯法基本概念”︁

{{DISPLAYTITLE:回溯法基本概念}}

'''回溯法'''（Backtracking）是一种通过系统地搜索所有可能的解来寻找问题解决方案的算法策略。它属于[[暴力搜索]]的一种优化形式，通过逐步构建候选解并在发现当前路径无法满足条件时回退（即“回溯”），从而避免无效搜索。回溯法常用于解决[[组合问题]]、[[约束满足问题]]和[[排列问题]]。

== 核心思想 ==
回溯法的核心是'''深度优先搜索'''（DFS）与'''剪枝'''（Pruning）的结合：
# '''试探性选择'''：从问题的初始状态出发，逐步构建候选解。
# '''约束检查'''：每次选择后检查是否满足问题的约束条件。
# '''回溯撤销'''：当发现当前路径无法达到最终解时，撤销最近的选择，尝试其他可能性。

数学上可描述为递归过程：
<math>
\text{Backtrack}(i) = 
\begin{cases} 
\text{成功} & \text{若当前解满足终止条件} \\
\text{失败} & \text{若所有候选选择已穷尽} \\
\text{递归尝试} & \text{否则对每个候选选择进行约束检查并继续}
\end{cases}
</math>

== 算法框架 ==
以下是回溯法的通用伪代码框架：
<syntaxhighlight lang="python">
def backtrack(candidate):
    if is_solution(candidate):  # 终止条件
        output(candidate)
        return
    
    for next_candidate in generate_candidates(candidate):  # 生成候选
        if is_valid(next_candidate):  # 约束检查
            make_choice(next_candidate)  # 选择
            backtrack(next_candidate)    # 递归
            undo_choice(next_candidate)  # 撤销选择（回溯）
</syntaxhighlight>

=== 示例：全排列问题 ===
生成数字 [1, 2, 3] 的所有排列：
<syntaxhighlight lang="python">
def permute(nums):
    def backtrack(path):
        if len(path) == len(nums):  # 终止条件
            res.append(path.copy())
            return
        for num in nums:
            if num not in path:     # 约束检查
                path.append(num)    # 选择
                backtrack(path)    # 递归
                path.pop()         # 回溯
    
    res = []
    backtrack([])
    return res

# 输入: [1, 2, 3]
# 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
</syntaxhighlight>

== 关键概念 ==
=== 1. 状态空间树 ===
回溯过程可视为对'''状态空间树'''的深度优先遍历：
<mermaid>
graph TD
    A[初始状态] --> B[选择1]
    A --> C[选择2]
    B --> D[选择1.1]
    B --> E[选择1.2]
    C --> F[选择2.1]
    C --> G[选择2.2]
    style D stroke:#f00  // 标记无效路径
    linkStyle 3 stroke:#f00,stroke-width:2px
</mermaid>
* '''节点'''：表示部分解
* '''边'''：表示决策选择
* '''剪枝'''：红色路径表示因违反约束被剪枝

=== 2. 剪枝优化 ===
通过提前终止无效分支提高效率：
* '''可行性剪枝'''：检查当前部分解是否满足约束（如N皇后中是否冲突）
* '''最优性剪枝'''：在优化问题中提前终止非最优路径（如旅行商问题）

== 实际应用案例 ==
=== 案例1：N皇后问题 ===
在N×N棋盘上放置N个皇后，使其互不攻击：
<syntaxhighlight lang="python">
def solveNQueens(n):
    def backtrack(row, cols, diags, anti_diags, path):
        if row == n:
            res.append(path)
            return
        for col in range(n):
            d, ad = row - col, row + col  # 主/副对角线标识
            if col not in cols and d not in diags and ad not in anti_diags:
                backtrack(row+1, cols|{col}, diags|{d}, anti_diags|{ad}, path + [col])
    
    res = []
    backtrack(0, set(), set(), set(), [])
    return [['.'*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in res]

# 输入: n=4
# 输出: [
#  [".Q..", "...Q", "Q...", "..Q."],
#  ["..Q.", "Q...", "...Q", ".Q.."]
# ]
</syntaxhighlight>

=== 案例2：数独求解 ===
使用回溯法填充数独空格：
<syntaxhighlight lang="python">
def solveSudoku(board):
    def is_valid(row, col, num):
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
        box_row, box_col = 3*(row//3), 3*(col//3)
        for i in range(3):
            for j in range(3):
                if board[box_row+i][box_col+j] == num:
                    return False
        return True
    
    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if backtrack():
                                return True
                            board[i][j] = '.'
                    return False
        return True
    
    backtrack()
</syntaxhighlight>

== 时间复杂度分析 ==
回溯法的效率取决于：
* 状态空间树的大小（通常为指数级 <math>O(b^d)</math>，其中b为分支因子，d为最大深度）
* 剪枝的有效性（好的剪枝可显著减少实际搜索空间）

{{重要提示|回溯法适合解空间明确且需要完整遍历的问题，但对大规模问题需谨慎使用}}

== 扩展阅读 ==
* [[递归与迭代的实现差异]]
* [[动态规划与回溯法的对比]]
* [[启发式搜索优化回溯]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:回溯与分支限界]]