回溯与分支极限
回溯
关于回溯
- 许多问题很难用算法求解,但是又不得不解决;
- 回溯搜索问题的解空间,可以看作穷举查找的改进,可解决规模较大的组合难题;
- 回溯通常按照深度优先、宽度优先或者结合的方式等多种方法遍历树;
n 皇后问题
TODO
哈密顿回路
TODO
子集和问题
TODO
分支界限
概述
在此之前,你应该知道回溯的方法
和回溯法相比,分支界限法需要两个额外的条件:
- 对于一颗状态空间树的每一个节点所代表的部分解,我们提供一种方法,计算出通过这个部分解繁衍出的任何解在目标函数上的最佳边界。
- 目前求得的最佳解的值。
在最小化问题中不小于,在最大化问题中不大于目前的最佳解,这个节点就是一个没有希望的节点,需要立即终止(剪枝)
一般来说,只要符合下面三种中的一种原因,我们就会终止它在当前节点上的查找路径:
- 该节点的边界值不能超越目前最佳解的值。
- 该节点无法代表任何可行解,因为它已经违反了问题的约束。
- 该节点代表的可行解的子集只包含一个单独的点(因此无法给出更多的选择)。在这种情况下,我们拿这个可行解在目标函数上的值和目前求得的最佳解进行比较,如果新的解更好一些,就用前者替换后者。
分支界限求旅行商问题(图示)
问题:寻找最小成本分配
成本下界:任何解的成本不会小于每行最小元素之和,即 2+3+1+4=10;
分支界限求背包问题(图示)
问题:装入承重量 W=10 的背包价值最大的物品
价值上界:对于给定实例中的物品,按照降序对”价值/重量“比排序;
依次装入还未装入背包价值最大的物品;
若已经选的物品总价值为
,重量为 ,后续装入物品后总结之的上界 ;
分支界限解决旅行商问题(代码)
python
import math
maxsize = float('inf')
def copyToFinal(curr_path):
final_path[:N + 1] = curr_path[:]
final_path[N] = curr_path[0]
def firstMin(adj, i):
min = maxsize
for k in range(N):
if adj[i][k] < min and i != k:
min = adj[i][k]
return min
def secondMin(adj, i):
first, second = maxsize, maxsize
for j in range(N):
if i == j:
continue
if adj[i][j] <= first:
second = first
first = adj[i][j]
elif (adj[i][j] <= second and adj[i][j] != first):
second = adj[i][j]
return second
python
def TSPRec(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:
copyToFinal(curr_path)
final_res = curr_res
return
for i in range(N):
if (adj[curr_path[level - 1]][i] != 0 and visited[i] == False):
temp = curr_bound
curr_weight += adj[curr_path[level - 1]][i]
if level == 1:
curr_bound -= (
(firstMin(adj, curr_path[level - 1]) + firstMin(adj, i)) /
2)
else:
curr_bound -= (
(secondMin(adj, curr_path[level - 1]) + firstMin(adj, i)) /
2)
if curr_bound + curr_weight < final_res:
curr_path[level] = i
visited[i] = True
TSPRec(adj, curr_bound, curr_weight, level + 1, curr_path,
visited)
curr_weight -= adj[curr_path[level - 1]][i]
curr_bound = temp
visited = [False] * len(visited)
for j in range(level):
if curr_path[j] != -1:
visited[curr_path[j]] = True
def TSP(adj):
curr_bound = 0
curr_path = [-1] * (N + 1)
visited = [False] * N
for i in range(N):
curr_bound += (firstMin(adj, i) + secondMin(adj, i))
curr_bound = math.ceil(curr_bound / 2)
visited[0] = True
curr_path[0] = 0
TSPRec(adj, curr_bound, 0, 1, curr_path, visited)
python
adj1 = [
[0, 3, 1, 5, 8],
[3, 0, 6, 7, 9],
[1, 6, 0, 4, 3],
[5, 7, 4, 0, 3],
[8, 9, 2, 3, 0]
]
N = 5
final_path = [None] * (N + 1)
visited = [False] * N
final_res = maxsize
TSP(adj1)
print("Minimum cost :", final_res)
print("Path Taken : ", end=' ')
for i in range(N + 1):
print(final_path[i], end=' ')
python
Minimum cost : 16
Path Taken : 0 1 3 4 2 0