可行解搜索（回溯与分支限界）

简介[编辑 | 编辑源代码]

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

基本概念[编辑 | 编辑源代码]

解空间与状态树[编辑 | 编辑源代码]

可行解搜索通常在问题的解空间树（也称状态树）中进行。树的每个节点代表一个部分解，从根到叶子的路径可能构成一个完整解。搜索过程分为两类：

回溯法：深度优先搜索（DFS）策略，通过递归或栈实现，遇到无效解时回溯。
分支限界法：广度优先搜索（BFS）或最佳优先策略，通过优先级队列实现，利用界限函数剪枝。

约束条件与目标函数[编辑 | 编辑源代码]

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

算法流程[编辑 | 编辑源代码]

以下是回溯法的通用伪代码框架：

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)

示例：子集和问题[编辑 | 编辑源代码]

问题描述[编辑 | 编辑源代码]

给定集合 $S = {x_{1}, x_{2}, . . ., x_{n}}$ 和目标值 $T$ ，找出所有子集使元素和等于 $T$ 。

代码实现[编辑 | 编辑源代码]

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]]

执行过程分析[编辑 | 编辑源代码]

分支限界法案例：0-1背包问题[编辑 | 编辑源代码]

问题描述[编辑 | 编辑源代码]

在背包容量限制下选择物品使总价值最大，每个物品只能选或不选。

代码框架[编辑 | 编辑源代码]

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