编辑“︁可行解搜索（回溯与分支限界）”︁

{{DISPLAYTITLE:可行解搜索（回溯与分支限界）}}

== 简介 ==
'''可行解搜索'''是[[回溯算法]]和[[分支限界法]]中的核心概念，指在问题的解空间中系统地寻找满足约束条件的解。这类方法通过逐步构建候选解，并在发现当前路径无法满足条件时进行回溯或剪枝，从而高效地缩小搜索范围。可行解搜索广泛应用于组合优化、约束满足问题（如数独、N皇后）以及资源分配问题。

== 基本概念 ==
=== 解空间与状态树 ===
可行解搜索通常在问题的'''解空间树'''（也称状态树）中进行。树的每个节点代表一个'''部分解'''，从根到叶子的路径可能构成一个完整解。搜索过程分为两类：
* '''回溯法'''：深度优先搜索（DFS）策略，通过递归或栈实现，遇到无效解时回溯。
* '''分支限界法'''：广度优先搜索（BFS）或最佳优先策略，通过优先级队列实现，利用界限函数剪枝。

=== 约束条件与目标函数 ===
* '''约束条件'''：限制解的有效性（如N皇后中皇后不能互相攻击）。
* '''目标函数'''（分支限界法特有）：用于评估解的优劣（如旅行商问题中的路径长度）。

== 算法流程 ==
以下是回溯法的通用伪代码框架：
<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):
            backtrack(next_candidate)
</syntaxhighlight>

== 示例：子集和问题 ==
=== 问题描述 ===
给定集合<math>S = \{x_1, x_2, ..., x_n\}</math>和目标值<math>T</math>，找出所有子集使元素和等于<math>T</math>。

=== 代码实现 ===
<syntaxhighlight lang="python">
def subset_sum(nums, target):
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path.copy())
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                continue  # 剪枝
            path.append(nums[i])
            backtrack(i + 1, path, remaining - nums[i])
            path.pop()  # 回溯
    result = []
    backtrack(0, [], target)
    return result

# 示例输入
nums = [3, 1, 2, 4]
target = 5
print(subset_sum(nums, target))  # 输出：[[3, 2], [1, 4], [1, 2, 2]]
</syntaxhighlight>

=== 执行过程分析 ===
<mermaid>
graph TD
    A[开始: [], rem=5] --> B[选3: [3], rem=2]
    B --> C[选1: [3,1], rem=1]
    C --> D[选2: [3,1,2], rem=-1] --> 回溯
    C --> E[选4: [3,1,4], rem=-3] --> 回溯
    B --> F[选2: [3,2], rem=0] --> 记录解
    A --> G[选1: [1], rem=4]
    G --> H[选2: [1,2], rem=2]
    H --> I[选4: [1,2,2], rem=0] --> 记录解
    G --> J[选4: [1,4], rem=0] --> 记录解
</mermaid>

== 分支限界法案例：0-1背包问题 ==
=== 问题描述 ===
在背包容量限制下选择物品使总价值最大，每个物品只能选或不选。

=== 代码框架 ===
<syntaxhighlight lang="python">
from queue import PriorityQueue

def knapsack(items, capacity):
    items.sort(key=lambda x: x[1]/x[0], reverse=True)  # 按价值密度排序
    pq = PriorityQueue()
    best_value = 0

    def bound(i, weight, value):
        remaining = capacity - weight
        bound_val = value
        while i < len(items) and items[i][0] <= remaining:
            remaining -= items[i][0]
            bound_val += items[i][1]
            i += 1
        if i < len(items):
            bound_val += remaining * (items[i][1]/items[i][0])
        return bound_val

    # 初始节点：未选任何物品
    pq.put((-bound(0, 0, 0), 0, 0, 0))  # 优先级队列按负值排序

    while not pq.empty():
        _, i, weight, value = pq.get()
        if weight > capacity:
            continue
        if value > best_value:
            best_value = value
        if i == len(items):
            continue
        # 分支：选或不选第i件物品
        new_weight = weight + items[i][0]
        new_value = value + items[i][1]
        if new_weight <= capacity and bound(i+1, new_weight, new_value) > best_value:
            pq.put((-bound(i+1, new_weight, new_value), i+1, new_weight, new_value))
        if bound(i+1, weight, value) > best_value:
            pq.put((-bound(i+1, weight, value), i+1, weight, value))
    return best_value
</syntaxhighlight>

== 应用场景 ==
* '''数独求解'''：回溯法填充数字并验证有效性。
* '''电路板布线'''：分支限界法寻找最短路径。
* '''任务调度'''：搜索满足截止时间的任务序列。

== 优化技巧 ==
* '''剪枝策略'''：提前终止不可能产生更优解的分支。
* '''记忆化'''：存储已计算状态避免重复（如动态规划结合回溯）。
* '''启发式排序'''：优先处理高潜力分支（如背包问题按价值密度排序）。

== 复杂度分析 ==
最坏情况下，回溯法和分支限界法的复杂度均为<math>O(2^n)</math>（解空间大小），但实际效率取决于：
* 剪枝效果
* 问题约束的严格性
* 界限函数的准确性

{{算法导航}}

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