分支限界算法概述 - 与回溯对比 - 分支限界与回溯的区别

分支限界算法概述 - 与回溯对比 - 分支限界与回溯的区别

引言

在算法的世界里，有许多强大的工具帮助我们解决各种复杂的问题，分支限界算法和回溯算法就是其中两个重要的方法。它们在解决组合优化问题、搜索问题等方面发挥着重要作用。虽然这两种算法都用于搜索解空间，但它们有着不同的策略和特点。本文将对分支限界算法进行概述，并与回溯算法进行对比，探讨它们之间的区别。

分支限界算法概述

基本概念

分支限界算法是一种在问题的解空间树中搜索问题解的算法。它的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在扩展结点处，首先生成其所有的儿子结点（分支），然后从当前的活结点表中选择下一个扩展结点。为了加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

工作流程

1. 定义解空间：确定问题的所有可能解的集合，通常表示为一棵解空间树。
2. 确定扩展结点的规则：选择下一个要扩展的活结点的策略，常见的有队列式（FIFO）分支限界和优先队列式分支限界。
3. 计算限界函数：用于估计从当前结点出发可能得到的最优解的界限，帮助剪去不可能包含最优解的子树。
4. 搜索解空间：从根结点开始，按照扩展结点的规则不断扩展结点，直到找到最优解或确定无解。

实例：0 - 1 背包问题

假设有一个背包，它的容量为 $C = 50$，有 3 个物品，其重量分别为 $w = [20, 30, 10]$，价值分别为 $v = [60, 120, 50]$。我们使用优先队列式分支限界算法来解决这个问题。

import heapq
class Node:
    def __init__(self, level, profit, weight, bound):
        self.level = level
        self.profit = profit
        self.weight = weight
        self.bound = bound
    def __lt__(self, other):
        return self.bound > other.bound
def bound(node, n, capacity, weights, values):
    if node.weight >= capacity:
        return 0
    profit_bound = node.profit
    level = node.level + 1
    total_weight = node.weight
    while level < n and total_weight + weights[level] <= capacity:
        total_weight += weights[level]
        profit_bound += values[level]
        level += 1
    if level < n:
        profit_bound += (capacity - total_weight) * (values[level] / weights[level])
    return profit_bound
def knapsack_branch_and_bound(capacity, weights, values):
    n = len(weights)
    root = Node(-1, 0, 0, 0)
    root.bound = bound(root, n, capacity, weights, values)
    max_profit = 0
    pq = []
    heapq.heappush(pq, root)
    while pq:
        current = heapq.heappop(pq)
        if current.bound > max_profit:
            next_level = current.level + 1
            # 考虑包含下一个物品
            left_child = Node(next_level, current.profit + values[next_level], current.weight + weights[next_level], 0)
            if left_child.weight <= capacity and left_child.profit > max_profit:
                max_profit = left_child.profit
            left_child.bound = bound(left_child, n, capacity, weights, values)
            if left_child.bound > max_profit:
                heapq.heappush(pq, left_child)
            # 考虑不包含下一个物品
            right_child = Node(next_level, current.profit, current.weight, 0)
            right_child.bound = bound(right_child, n, capacity, weights, values)
            if right_child.bound > max_profit:
                heapq.heappush(pq, right_child)
    return max_profit
capacity = 50
weights = [20, 30, 10]
values = [60, 120, 50]
result = knapsack_branch_and_bound(capacity, weights, values)
print("最大价值:", result)

回溯算法概述

基本概念

回溯算法是一种深度优先搜索算法，它通过深度优先的方式系统地搜索问题的解空间树。在搜索过程中，当发现当前的路径不可能得到问题的解时，就回溯到上一步，尝试其他的路径。回溯算法通常用于解决组合问题、排列问题等。

工作流程

1. 定义解空间：同样需要确定问题的所有可能解的集合，以解空间树的形式表示。
2. 深度优先搜索：从根结点开始，沿着一条路径不断深入，直到达到叶子结点或无法继续扩展。
3. 回溯操作：当无法继续扩展或当前路径不可能得到解时，回溯到上一个结点，尝试其他的分支。

实例：八皇后问题

八皇后问题是一个经典的回溯算法应用场景，要求在 $8 \times 8$ 的棋盘上放置 8 个皇后，使得它们互不攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。

def is_safe(board, row, col):
    # 检查列是否有皇后冲突
    for i in range(row):
        if board[i][col] == 1:
            return False
    # 检查左上对角线是否有皇后冲突
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    # 检查右上对角线是否有皇后冲突
    for i, j in zip(range(row, -1, -1), range(col, 8)):
        if board[i][j] == 1:
            return False
    return True
def solve_n_queens(board, row):
    if row == 8:
        return True
    for col in range(8):
        if is_safe(board, row, col):
            board[row][col] = 1
            if solve_n_queens(board, row + 1):
                return True
            board[row][col] = 0
    return False
board = [[0] * 8 for _ in range(8)]
if solve_n_queens(board, 0):
    for row in board:
        print(row)
else:
    print("无解")

分支限界与回溯的区别

搜索策略

• 回溯算法：采用深度优先搜索策略，沿着一条路径一直深入，直到无法继续或达到叶子结点，然后回溯到上一个结点尝试其他分支。这种策略适合于寻找所有可能的解或找到一个可行解。
• 分支限界算法：可以采用广度优先搜索（队列式分支限界）或优先队列式搜索，根据限界函数选择最有希望的结点进行扩展。它更侧重于寻找最优解。

目标不同

• 回溯算法：主要用于找出问题的所有可行解或一个可行解，不保证找到的解是最优解。
• 分支限界算法：目标是找到问题的最优解，通过限界函数剪去不可能包含最优解的子树，提高搜索效率。

结点扩展方式

• 回溯算法：一次只扩展一个结点，沿着一条路径深入搜索，只有在当前路径无法继续时才回溯。
• 分支限界算法：在扩展结点时，会生成该结点的所有儿子结点，并根据限界函数选择下一个扩展结点。

内存使用

• 回溯算法：只需要保存当前路径上的结点信息，内存开销相对较小。
• 分支限界算法：需要维护一个活结点表，保存所有待扩展的结点，内存开销相对较大。

对比表格总结

结论

分支限界算法和回溯算法都是解决组合优化和搜索问题的有效方法，但它们有着不同的特点和适用场景。回溯算法简单直观，适合于寻找可行解的问题；而分支限界算法通过限界函数的剪枝操作，更适合于寻找最优解的问题。在实际应用中，我们需要根据问题的特点和要求选择合适的算法。