文章目录
@[toc]问题描述问题转换回溯法时间复杂性`Python`实现
个人主页：丷从心
系列专栏：回溯法
问题描述
有一批共
n
n
n个集装箱要装上
2
2
2艘载重量分别为
c
1
c_{1}
c1和
c
2
c_{2}
c2的轮船，其中集装箱
i
i
i的重量为
w
i
w_{i}
wi，且
∑
i
=
1
n
w
i
≤
c
1
+
c
2
\displaystyle\sum\limits_{i = 1}^{n}{w_{i}} \leq c_{1} + c_{2}
i=1∑nwi≤c1+c2是否有一个合理的装载方案可将这
n
n
n个集装箱装上这两艘轮船
问题转换
先将第一艘轮船尽可能装满，然后将剩余的集装箱装上第二艘轮船装载问题等价于以下特殊的
0
−
1
0-1
0−1背包问题
{
max
∑
i
=
1
n
w
i
x
i
s
.
t
.
∑
i
=
1
n
w
i
x
i
≤
c
1
x
i
∈
{
0
,
1
}
,
1
≤
i
≤
n
\begin{cases} \max{\displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}}} \\ s.t. \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c_{1} \end{cases} \kern{2em} x_{i} \in \set{0 , 1} , 1 \leq i \leq n
⎩
⎨
⎧maxi=1∑nwixis.t.i=1∑nwixi≤c1xi∈{0,1},1≤i≤n
回溯法
用子集树表示解空间，根节点为第
0
0
0层约束函数用于剪去不满足约束条件
∑
i
=
1
n
w
i
x
i
≤
c
1
\displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c_{1}
i=1∑nwixi≤c1的子树
在子集树的第
j
j
j层的结点
Z
Z
Z处，用
c
w
cw
cw记为当前的装载重量，即
c
w
=
∑
i
=
1
j
w
i
x
i
cw = \displaystyle\sum\limits_{i = 1}^{j}{w_{i} x_{i}}
cw=i=1∑jwixi当
c
w
>
c
1
cw > c_{1}
cw>c1时，以结点
Z
Z
Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去 限界函数用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率
设
Z
Z
Z是解空间树第
i
i
i层上的当前扩展结点，
c
w
cw
cw是当前载重量，
b
e
s
t
w
bestw
bestw是当前最优载重量，
r
r
r是剩余集装箱的重量，即
r
=
∑
j
=
i
+
1
n
w
j
r = \displaystyle\sum\limits_{j = i + 1}^{n}{w_{j}}
r=j=i+1∑nwj定义限界函数为
c
w
+
r
cw + r
cw+r，在以
Z
Z
Z为根的子树中任一叶节点所相应的重量均不超过
c
w
+
r
cw + r
cw+r，当
c
w
+
r
≤
b
e
s
t
w
cw + r \leq bestw
cw+r≤bestw时，可将
Z
Z
Z的子树剪去 当
i
=
n
i = n
i=n时，算法搜索至叶结点，其相应的装载重量为
c
w
cw
cw，如果
c
w
>
b
e
s
t
w
cw > bestw
cw>bestw，则表示当前解优于当前最优解，此时更新
b
e
s
t
w
bestw
bestw当
i
<
n
i < n
i Z Z Z是子集树中的内部结点，该结点的左儿子表示 x [ i + 1 ] = 1 x[i + 1] = 1 x[i+1]=1的情形，仅当 c w + w [ i + 1 ] ≤ c 1 cw + w[i + 1] \leq c_{1} cw+w[i+1]≤c1且满足限界函数时进入左子树，对左子树递归搜索，该结点的右儿子表示 x [ i + 1 ] = 0 x[i + 1] = 0 x[i+1]=0的情形，由于可行结点的右儿子结点总是可行的，因此进入右子树时不需要检查约束函数，只需要检查限界函数 时间复杂性 在每个结点处算法花费 O ( n ) O(n) O(n)时间，子集树中结点个数为 O ( 2 n ) O(2^{n}) O(2n)，故时间复杂性为 O ( n 2 n ) O(n 2^{n}) O(n2n) Python实现 def backtrack_loading(weights, capacity): n = len(weights) best_solution = [] best_value = 0 def constraint(solution): # 约束函数: 检查当前解是否满足容量限制 total_weight = sum(item for item in solution) return total_weight <= capacity def bound(solution, index): # 限界函数: 计算当前解的重量总和加上剩余物品重量作为上界, 用于剪枝 total_weight = sum(item for item in solution) + sum(weight for weight in weights[index + 1:]) return total_weight def backtrack(solution, value, index): nonlocal best_solution, best_value if index == n: # 已经遍历完所有物品 if value > best_value: # 如果当前解的重量更大, 更新最优解 best_solution = solution best_value = value return # 尝试选择当前物品 weight = weights[index] if constraint(solution + [weight]) and bound(solution + [weight], index) >= best_value: # 如果满足约束函数, 继续探索下一个物品 backtrack(solution + [weight], value + weight, index + 1) # 尝试不选择当前物品 if bound(solution, index) >= best_value: # 如果当前解的上界仍然可能更好, 继续探索下一个物品 backtrack(solution, value, index + 1) # 开始回溯搜索 backtrack([], 0, 0) return best_solution, best_value weights = [2, 4, 5, 7] capacity = 10 best_solution, best_value = backtrack_loading(weights, capacity) print(f'最优解: {best_solution}') print(f'最优值: {best_value}') 最优解: [2, 7] 最优值: 9 相关文章
发表评论