- 分支限界法与回溯法的联系与区别
- 分支限界法的基本要素
- 求解问题的特点/回溯法问题的解空间/解空间树
- 分支限界的解空间树搜索策略/剪枝函数等 两类重要的数据结构
- FIFO队列,优先队列(最大/最小堆)
- 具体算法
- 0-1背包问题、旅行售货员问题、批处理作业调度
- 掌握上述具体算法相应的解空间、解空间树、所用算法框架、伪代码描述基本结构、剪枝策略等
- 给定输入,能大致描述算法的求解过程
分支与界限简介
分支与界限(branch and bound) 用于解决组合优化问题。这类问题的复杂度可能成指数增长,最坏情况下可能需要遍历所有组合。而分支与界限则可以很好地解决这些问题。
下面考虑之前提过的背包问题,之前的解法为:
- 贪心算法:只能解决分数背包问题
- 动态规划——能解决 0-1背包问题,但要求物体重量为整数
- 回溯算法——能解决0-1背包问题,但会搜索出所有的可行解
回溯算法是通过 DFS(深度优先搜索)来对搜索树进行剪枝,然后再比较得到最优解。我们可以在这个基础上进一步剪枝。采用 BFS(广度优先搜索),当每搜索到一个结点,我们对这个结点之后的结果进行估计,得到一个最优上界。如果这个最优上界比当前已经搜索得到的最优解还差,那么就可以舍去这个结点及其子树。
那么最优上界要如何估计?首先,结点的父母节点是已经搜索过的,所以只能根据实际加上。而后面的结点还没搜索,为了在得到最优上界的同时不超出背包容量限制,我们采用“贪心算法”,先尽可能放单位价值大的物品,若最后还有空位,则放分数个物品来填满。最终可以得到每个结点的最优上界。
为了方便计算上界,我们将物品按单位价值排序,并以这个顺序来构造搜索树。
给出如下 python 代码:
#该代码参考了Utkarsh Trivedi的C++代码
from queue import Queue #使用队列进行 BFS
from operator import itemgetter
from copy import deepcopy
class Node(object):
def __init__(self,level,profit,bound,weight):
"""
level --> 在搜索树中的层次(当前考察的物品的索引)
profit --> 从根到当前结点的价值和
bound --> 最优上界
weight --> 从根到当前结点的重量和
"""
self.level=level
self.profit=profit
self.bound=bound
self.weight=weight
def bound(u, n, W, item):
"""
用于获取当前结点的最优上界
u --> 结点
n --> item中物品数量
W --> 总重量
item --> 物品
"""
if u.weight>=W: #已放满
return 0
profit_bound = u.profit
j = u.level+1
totweight=u.weight
# 先尽可能放单位价值高的物品
while (j<n) and (totweight+item[j][0]<=W):
totweight += item[j][0]
profit_bound += item[j][1]
j+=1
# 最后用分数个物品填满
if j<n:
profit_bound += (W-totweight)*item[j][1]/item[j][0]
return profit_bound
def knapSack(W, item):
#按单位价值排序
n=len(item)
for i in range(n):
item[i].append(item[i][1]/item[i][0])
item=sorted(item, key=itemgetter(2),reverse=True)
Q = Queue() #初始化队列
u = Node(-1,0,0,0) #根结点
v = Node(0,0,0,0) #下一层结点
Q.put(u)
maxProfit=0 #初始化最大价值
# BFS
while not Q.empty():
u=Q.get()
# 已经到了最后一层
if u.level == n-1:
continue
#对 u 的子结点搜索
#将子结点的物品放入
v.level = u.level+1
v.weight=u.weight+item[v.level][0]
v.profit=u.profit+item[v.level][1]
#更新目前的最大价值
if v.weight <=W and v.profit>maxProfit:
maxProfit = v.profit
#计算最优上界
v.bound=bound(v,n,W,item)
if v.bound >= maxProfit:
#最优上界比目前最大价值大
#子树可能包含最优解
#放入队列,等待后续搜索
Q.put(deepcopy(v)) #深拷贝
#对 u 的子结点搜索
#不将子结点的物品放入
v.weight = u.weight
v.profit = u.profit
v.bound = bound(v,n,W,item)
#最大价值不变,无需计算
#计算最优上界
if v.bound >= maxProfit:
Q.put(deepcopy(v)) #深拷贝
return maxProfit
def main():
W=10
item=[[2.0,40.0],[3.14,50.0],[1.98,100.0],[5.0,95.0],[3.0,30.0]]
print("最大价值:", knapSack(W,item))
return 0
main()
代码对应的搜索树如下图:
旅行商问题
前面回溯算法讲过的旅行商问题同样可以用分支与界限算法来求解。
由于我们要求的是“最短”路径,所以这里的界限是“下界”,即可能的最短路程。我们可能容易想到:最短路径 = 已有路径 + 未到结点的最短边。但考虑到在路径中,每个结点实际上与两条边相连,所以改进为:最短路径 = 已有路径 + 1/2(未到结点的最短两边)。
import heapq
class Nod:
def __init__(self, indice, traseu, mat_redusa, cost, nr):
self.indice = indice # ce valoare e rep din matrice
self.traseu = traseu # vector de perechi p(nr,cost)
self.mat_redusa = mat_redusa
self.cost = cost
self.nr = nr # nr la care s-a ajuns in arbore
def __eq__(self, other):
return (self.cost == other.cost)
def __lt__(self, other):
return (self.cost < other.cost)
def __gt__(self, other):
return (self.cost > other.cost)
# functie pentru a adauga un nod (i,j) //de la i la j
def new_nod(parent_M, traseu, nr, i, j):
# Cream mat_redusa si punem pe linia i si coloana j INF
# mat_redusa = np.copy(parent_M) # copiez frumos incet
mat_redusa = []
for l in range(n):
aux = []
for k in range(n):
aux.append(parent_M[l][k])
mat_redusa.append(aux)
for k in range(n):
if nr == 0:
break
mat_redusa[i][k] = 'INF'
mat_redusa[k][j] = 'INF'
if nr != 0:
mat_redusa[j][i] = 'INF'
cost = 0 # nu a fost calculat inca
t = []
for l in traseu:
t.append(l)
nod = Nod(j, t, mat_redusa, cost, nr)
return nod
# functii pentru a reduce matricea a.i. sa fie un 0 pe fiecare linie
def linie_reducere(M, n):
v = ['INF'] * n # in v punem valoarea minima din fiecare linie
# formam v-ul
for i in range(n):
for j in range(n):
if v[i] == 'INF':
v[i] = M[i][j]
if M[i][j] == 'INF':
continue
elif v[i] > M[i][j]:
v[i] = M[i][j]
# scadem valorile minime
for i in range(n):
for j in range(n):
if v[i] == 'INF':
continue
if M[i][j] == 'INF':
continue
M[i][j] -= v[i]
return v
# functii pentru a reduce matricea a.i. sa fie un 0 pe fiecare coloana
def coloana_reducere(M, n):
v = ['INF'] * n # in v punem valoarea minima din fiecare coloana
# formam v-ul
for i in range(n):
for j in range(n):
if v[j] == 'INF':
v[j] = M[i][j]
if M[i][j] == 'INF':
continue
elif v[j] > M[i][j]:
v[j] = M[i][j]
# scadem valorile minime
for i in range(n):
for j in range(n):
if v[j] == 'INF':
continue
if M[i][j] == 'INF':
continue
M[i][j] -= v[j]
return v
# Functie de calculat cost minim
def calc_Cost(M, n):
cost = 0
# reducem matricea
l = linie_reducere(M, n)
c = coloana_reducere(M, n)
for i in range(n):
if l[i] != 'INF':
cost += l[i]
if c[i] != 'INF':
cost += c[i]
return cost
def TSP(costM, n):
# folosim coada de prioritati ca sa retinem ce noduri sunt acum in arbore
h = []
heapq.heapify(h)
traseu = []
# cream radacina si ii calculam costul, incepem din 0
mat_redusa = []
for i in range(n):
aux = []
for j in range(n):
aux.append(costM[i][j])
mat_redusa.append(aux)
root = new_nod(mat_redusa, traseu, 0, -1, 0)
root.cost = calc_Cost(root.mat_redusa, n)
# Aduagam radacina la lista cu noduri active
heapq.heappush(h, (root.cost, root))
# Gaseste un nod activ cu cost minim
# Adauga copii lui la lista de noduri active
# Si dupa il stergem din lista
while h:
min = heapq.heappop(h)
# Dupa ce scot min, sterg tot ce era in heap si actualizez traseul
h = [] # suprasciu h-ul
heapq.heapify(h)
if min[1].indice != 0:
if len(min[1].traseu) == 0:
min[1].traseu.append((0, min[1].indice))
else:
min[1].traseu.append(
(min[1].traseu[len(traseu)-1][1], min[1].indice))
i = min[1].indice # nr pe actual
if min[1].nr == n - 1: # daca toate orasele sunt visitate
# ne intoarcem la inceput
min[1].traseu.append((i, 0))
# Afisam Traseul si costul
print("Traseul este: ")
print(min[1].traseu)
print("Costul traseului %d" % min[1].cost)
# facem pt fiecare copil al minimului
# (i,j) muchie in arbore
for j in range(n):
if min[1].mat_redusa[i][j] != 'INF':
# cream un nod si ii calculam costul
copil = new_nod(min[1].mat_redusa,
min[1].traseu, min[1].nr + 1, i, j)
copil.cost = min[1].cost + int(min[1].mat_redusa[i][j]) + \
calc_Cost(copil.mat_redusa, n)
# Adugam copiul in lista cu noduri active
heapq.heappush(h, (copil.cost, copil))
# traseu.append(min[1].indice)
# n = 4 # nr linii si coloane
# Mat = [
# ['INF', 5, 4, 3],
# [3, 'INF', 8, 2],
# [5, 3, 'INF', 9],
# [6, 4, 3, 'INF']
# ] # cost 12
# n = 5
# Mat =\
# [
# ['INF', 10, 8, 9, 7],
# [10, 'INF', 10, 5, 6],
# [8, 10, 'INF', 8, 9],
# [9, 5, 8, 'INF', 6],
# [7, 6, 9, 6, 'INF']
# ]
# # cost 34
n = 4
Mat =\
[
['INF', 2, 1, 'INF'],
[2, 'INF', 4, 3],
[1, 4, 'INF', 2],
['INF', 3, 2, 'INF']
]
# cost 8
# n = 5
# Mat =\
# [
# ['INF', 3, 1, 5, 8],
# [3, 'INF', 6, 7, 9],
# [1, 6, 'INF', 4, 2],
# [5, 7, 4, 'INF', 3],
# [8, 9, 2, 3, 'INF']
# ]
# # cost 16
TSP(Mat, n)
import math
def first_second_min(adj, i):
first, second = float('inf'), float('inf')
for j in range(len(adj)):
if i == j:
continue
if adj[i][j] <= first:
second = first
first = adj[i][j]
elif adj[i][j] < second:
second = adj[i][j]
return first, second
def solveTSP(adj, curr_bound, curr_weight, level, curr_path, visited):
global final_res
# 到达叶子结点
if level == N:
# 回到出发点
if adj[curr_path[level - 1]][curr_path[0]] != 0:
curr_res = curr_weight + adj[curr_path[level - 1]][curr_path[0]]
if curr_res < final_res:
final_path[:N+1] = curr_path[:]
final_path[N] = curr_path[0]
final_res = curr_res
return
for i in range(N):
if (adj[curr_path[level-1]][i] != 100000 and
visited[i] == False):
temp = curr_bound
curr_weight += adj[curr_path[level - 1]][i]
currFirstMin, currSecondMin = first_second_min(adj, curr_path[level - 1])
iFirstMin, iSecondMin = first_second_min(adj, i)
if level == 1:
curr_bound -= ((currFirstMin + iFirstMin) / 2)
else:
curr_bound -= ((currSecondMin +
iFirstMin) / 2)
if curr_bound + curr_weight < final_res:
curr_path[level] = i
visited[i] = True
solveTSP(adj, curr_bound, curr_weight,
level + 1, curr_path, visited)
# 恢复
curr_weight -= adj[curr_path[level - 1]][i]
curr_bound = temp
# Also reset the visited array
visited = [False] * len(visited)
for j in range(level):
if curr_path[j] != -1:
visited[curr_path[j]] = True
def TSP(adj):
N = len(adj)
curr_bound = 0
curr_path = [-1] * (N + 1)
visited = [False] * N
for i in range(N):
firstMin, secondMin = first_second_min(adj, i)
curr_bound += (firstMin + secondMin)
# 向下取整
curr_bound = math.ceil(curr_bound / 2)
# 从第 1 个城市开始
visited[0] = True
curr_path[0] = 0
solveTSP(adj, curr_bound, 0, 1, curr_path, visited)
adj = [
[10000, 30, 6, 4],
[30, 10000, 5, 10],
[6, 5, 10000, 20],
[4, 10, 20, 10000]
]
N = 4
final_path = [None] * (N + 1)
visited = [False] * N
final_res = float("inf")
TSP(adj)
print("Minimum cost :", final_res)
print("Path Taken : ", end = ' ')
for i in range(N + 1):
print(final_path[i], end = ' ')
#结果:
# Minimum cost : 25
# Path Taken : 0 2 1 3 0
最大堆与最小堆
如果一个二叉树的父结点的值总是大于等于任一子结点时,这个二叉树称为最大堆。最小堆同理。
关于如何将一个数组构造成最大堆,以及如何在最大堆中插入、删除元素,可以参考:简书:最大堆和最小堆