分支限界笔记

概要

分支限界笔记

整体架构流程

基本概念

分支限界法的定义

分支限界法是一种广度优先搜索问题解空间树的方法，它结合了限界函数以提高搜索效率。

核心思想

1. 分支：基于广度优先策略，逐步生成所有子结点。
2. 限界函数：
   • 为每个子结点计算一个值，用来衡量其可行性或优越性。
   • 将符合限界条件的结点加入“活结点表”中。
3. 选择最优的扩展结点：
   • 从活结点表中选取“最有利”的一个子结点，作为扩展的结点。
   • 引导搜索向解空间树的最优解方向推进，以尽快找到问题的解。

简单问题介绍

问题：简单背包问题

你有一个容量为 10kg 的背包，想从以下物品中挑选一些装进去，使背包中的总价值最大。

规则：

• 每个物品最多选一次。
• 背包的总重量不能超过 10kg。

思考：暴力解法

如果我们不聪明地去解决问题，可以用“穷举法”：

1. 列出所有可能的组合：包括不装任何物品、装一个物品、装两个物品等。
2. 对每个组合，检查是否符合背包容量限制。
3. 如果符合，就计算总价值，记录最大的一个。

举个例子：

• 不装任何物品，总重量为 0，总价值为 0。
• 装物品 A，总重量为 2，总价值为 6。
• 装物品 A 和 C，总重量为 5，总价值为 18。

这种方法对小规模问题还行，但物品数量一多，组合会成倍增加，效率太低。

聪明的解法：分支限界法

分支限界法可以帮助我们有选择地搜索组合，而不需要列举所有可能性。我们分步骤来看：

1. 分支：生成子问题

   • 从装还是不装某个物品的选择开始。例如：
     • 不装 A，背包里还有 10kg 容量。
     • 装 A，背包里剩下 8kg 容量。

2. 限界：筛选有希望的分支

   • 如果某个选择显然不可能比当前最优解更好，就放弃。
   • 比如：如果当前背包已经装满了，但价值远低于已知最优解，就不再考虑这条路径。

3. 活结点：保存还没探索的分支

   • 我们用一个“活结点表”来存储每一步生成的子问题。
   • 按照某种优先级（比如潜在价值的大小）选择下一个要扩展的结点。

4. 剪枝：放弃无意义的计算

   • 当某个分支已经超过背包容量限制，就直接丢弃。

直观理解分支限界法的步骤

假设我们开始解上面的问题：

1. 初始状态：背包空着，容量为 10kg，当前总价值为 0。

2. 第一分支：

   • 不装 A：剩余容量 = 10kg，总价值 = 0。
   • 装 A：剩余容量 = 8kg，总价值 = 6。

3. 第二分支：

   • 从“装 A”继续分支：
     • 不装 B：剩余容量 = 8kg，总价值 = 6。
     • 装 B：剩余容量 = 3kg，总价值 = 16。
   • 从“不装 A”继续分支：
     • 不装 B：剩余容量 = 10kg，总价值 = 0。
     • 装 B：剩余容量 = 5kg，总价值 = 10。

4. 每次分支后，检查是否超过容量。如果超过，就剪枝。例如：

   • 假设某分支剩余容量为负值，这条路径就无效。

5. 继续分支，直到所有路径探索完毕，记录下最大价值。

0-1背包问题

问题描述

给定n种物品和一个背包。物品的重量是w,其价值为p，背包的容量为C。
问:应如何选择装入背包的物品，使得装入背包的物品总重量不超过C,并且总价值最大?

问题建模

输入：物品数量n，各物品价值pi，背包容量C
输出：最优价值bestp，最佳选择方案s[1…n]
目标函数：
约束条件：

问题分析

1. 定义问题的解空间，确定易于搜索的解空间结构

在 0/1 背包问题中，解空间可以描述为一个多维向量 (x1, x2, …, xn)，其中：

• 每个变量 xi 属于 {0, 1}，表示第 i 个物品是否被选中。
• 解空间的结构是一个 解向量的集合，例如：对于 4 个物品，解空间可以表示为 (x1, x2, x3, x4) 的所有组合。

这种解空间结构的确定，使得搜索可以基于向量的组合逐步进行，清晰地定义了解的每一步推进方式。

2. 设计限界函数，确定目标函数值的估算方法

目标是求解 0/1 背包问题的最大价值，属于一个 目标函数最大值问题。

• 限界函数定义：在计算解向量中目标函数值的上界时，设计一个 限界函数 ( ub )，用于估算子问题的最大潜在解。
• 目的：通过目标函数上界的限制，加速剪枝，避免遍历不可能获得更优解的分支。

限界函数的引入，使得对每个子问题的解搜索能够快速判断是否值得继续深入计算。

3. 基于限界函数的广度优先搜索

广度优先搜索是解决 0/1 背包问题的一种有效方法，结合限界函数能够显著提高搜索效率。

1. 限界函数估算上界：
   在搜索树的每一个结点，限界函数为其所有可能的解计算一个最大价值的上界，用于筛选有潜力的分支。

2. 剪枝规则：

   • 规则 1：若结点的限界函数值小于当前已知的最大价值（maxvalue），则直接剪枝，避免不必要的搜索。
   • 规则 2：若结点的当前重量 cw 超过背包容量 C，则剪枝该分支，避免产生无效解。

通过这些规则，可以减少大量不必要的搜索，显著提高算法效率。

实例

以下是基于 优先队列分支限界法求解 0/1 背包问题 的伪代码以及一个简单的例子，帮助你理解算法的核心逻辑。

伪代码

INPUT: 
    w[1..n] - 物品重量数组
    p[1..n] - 物品价值数组
    C - 背包容量
OUTPUT:
    bestp - 最大价值
    x[1..n] - 最优解向量

1. 按照单位重量价值 p[i]/w[i] 的非递增次序对物品排序
2. 初始化：
    bestp = 0  # 当前最大价值
    x[1..n] = [0, ..., 0]  # 最优解向量
    将根结点加入优先队列 PT，初始 ub 为全体物品能装下的最大可能值
3. while PT 非空:
    3.1 从 PT 中取出优先级最高的结点 node
    3.2 if node.ub <= bestp:
            剪枝，跳过该结点
        else:
            if node 是叶子结点:
                if node.value > bestp:
                    更新 bestp 和 x[1..n]（通过回溯路径）
            else:
                左儿子：装入当前物品
                    if 剩余重量 >= 0:
                        计算左儿子的 ub 和 value，将左儿子加入 PT
                右儿子：不装当前物品
                    计算右儿子的 ub 和 value，将右儿子加入 PT
4. 输出 bestp 和 x[1..n]

简单例子

输入数据

• 物品重量 ( w = [2, 3, 4] )
• 物品价值 ( p = [4, 5, 6] )
• 背包容量 ( C = 5 )

按单位重量价值排序
计算单位重量价值 ( p[i]/w[i] )：

• ( p[1]/w[1] = 4/2 = 2 )
• ( p[2]/w[2] = 5/3 \approx 1.67 )
• ( p[3]/w[3] = 6/4 = 1.5 )

排序后（单位价值降序）：

• 重量 ( w = [2, 3, 4] )
• 价值 ( p = [4, 5, 6] )

执行过程：

1. 初始化：
   • 将根结点加入优先队列 ( PT )：
     • 当前价值 ( value = 0 )
     • 剩余容量 ( C = 5 )
     • 初始 ub = 9 （尝试装入前两个物品的最大价值）

2. 第一层（根结点展开）：
   • 左儿子（装入第一个物品）：
     • 当前价值 ( value = 4 )
     • 剩余容量 ( C = 5 - 2 = 3 )
     • ub = 9
     • 加入队列。
   • 右儿子（不装入第一个物品）：
     • 当前价值 ( value = 0 )
     • 剩余容量 ( C = 5 )
     • ub = 7
     • 加入队列。

3. 第二层（左儿子展开）：
   • 左儿子的左儿子（装入第二个物品）：
     • 当前价值 ( value = 4 + 5 = 9 )
     • 剩余容量 ( C = 3 - 3 = 0 )
     • ub = 9
     • 是叶子结点，更新 bestp = 9，解向量 ( x = [1, 1, 0] )。
   • 左儿子的右儿子（不装入第二个物品）：
     • 当前价值 ( value = 4 )
     • 剩余容量 ( C = 3 )
     • ub = 7
     • 加入队列。

4. 第三层（右儿子展开）：
   • 右儿子的左儿子（装入第二个物品）：
     • 当前价值 ( value = 0 + 5 = 5 )
     • 剩余容量 ( C = 5 - 3 = 2 )
     • ub = 7
     • 加入队列。
   • 右儿子的右儿子（不装入第二个物品）：
     • 当前价值 ( value = 0 )
     • 剩余容量 ( C = 5 )
     • ub = 6
     • 加入队列。

5. 剪枝与结束：
   • 队列中的所有结点 ub <= bestp = 9，剪枝完成，算法结束。

最终结果

• 最大价值：( bestp = 9 )
• 最优解：( x = [1, 1, 0] )（选择物品 1 和物品 2）

总结

1. 本算法通过 限界函数（ub） 估算子树的最大可能值，从而剪枝，减少不必要的计算。
2. 优先队列 优先处理潜在最优解的分支，结合剪枝极大提高效率。
3. 例子中展示了完整过程，最终输出了最优价值和解向量。

旅行商问题

问题描述

问题建模

分支界限法解决问题

小结

简单例子开始理解