（算法理论）回溯法与与分⽀限界法（python）
分⽀限界法与回溯法的区别
1. 求解⽬标：回溯法的求解⽬标是出解空间树中满⾜约束条件的所有解，⽽分⽀限界法的求解⽬标则是出满⾜约束条件的⼀个解，
或是在满⾜约束条件的解中出在某种意义下的最优解。
2. 搜索⽅式的不同：回溯法以深度优先的⽅式搜索解空间树，⽽分⽀限界法则以⼴度优先或以最⼩耗费优先的⽅式搜索解空间树。 分⽀限界法
虚拟架子鼓
核⼼思想：分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展结点。活结点⼀旦成为扩展结点，就⼀次性产⽣其所有⼉⼦结点。在这些⼉⼦结点中，导致不可⾏解或导致⾮最优解的⼉⼦结点被舍弃，其余⼉⼦结点被加⼊活结点表中。 此后，从活结点表中取下⼀结点成为当前扩展结点，并重复上述结点扩展过程。这个过程⼀直持续到到所需的解或活结点表为空时为⽌。常见的两种分⽀限界法
按照队列先进先出（FIFO）原则选取下⼀个结点为扩展结点。
2. 优先队列式分⽀限界法:
按照优先队列中规定的优先级选取优先级最⾼的结点成为当前扩展结点。
分⽀限定法解单源最短路径：
问题描述：
在下图所给的有向图G中，每⼀边都有⼀个⾮负边权。要求图G的从源顶点s到⽬标顶点t之间的最短路径。
个⼈理解：扇贝笼
什么叫分⽀限界？⽤FIFO队列⽅法来说明：
⼀、将图G的单源最短路径问题分解为解空间树。其中，每⼀个结点旁边的数字表⽰该结点所对应的当前路长。
创建队列。
⼆、
1. 节点s⼊队列，Ｑ＝{ s }，我们取出队头节点，作为扩散节点，更新他的后代的值。 如图所⽰更新节点a，b，c的距离，并将他们加⼊队列，Ｑ＝｛s，a，b，c｝。 完成后节点s出队。
Ｑ＝｛a，b，c｝。
2. 同样，重复１的步骤，取出队头节点，a作为扩散节点，Ｑ＝｛a，b，c，u，e，d｝。完成后节点a
出队。
Ｑ＝｛b，c，u，e，d｝。
3. 同样，继续重复，取出队头节点，b作为扩散节点，Ｑ＝｛b，c，u，e，d，g，f｝。完成后节点b出队。
Ｑ＝｛c，u，e，d，g，f｝。
4. 同样，继续重复，取出队头节点，c作为扩散节点，Ｑ＝｛c，u，e，d，g，f , h ｝。完成后节点c出队。
Ｑ＝｛u，e，d，g，f , h ｝。
5. 当u作为扩散节点，f和g⼊队，我们发现f节点已经在队列中，这时⽐较：s—a—u—f 权重为14，s—b—f 权重为12，所以s—a—u
—f这条路径就被剪枝掉了，之后我们不再考虑。 这就是“限界”（称为”剪枝“）的思想。
6. 重复步骤，直到Ｑ为空。
优先队列法⽅法和FIFO⽅法类似，区别在于优先队列每次取队列元素中到源点距离最短的点。
python实现源代码：
# 初始化图参数⽤字典初始初始化这个图
化学浆糊G = {1: { 2: 4, 3: 2,4:5},
2: { 5: 7, 6: 5},
3: { 6: 9},
4: { 5: 2, 7: 7},
5: { 8: 4},
6: { 10:6},
7: { 9: 3},
8: { 10:7},
9: { 10:8},
10:{}
}
inf=9999
#保存源点到各点的距离，为了让顶点和下标⼀致，前⾯多了⼀个inf作为哨兵节点。
length=[inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf]
Q=[]
#FIFO队列实现
黄花菜加工def branch(G,v0):
Q.append(v0)
dict=G[1]
while len(Q)!=0:
#队列头元素出队
head=Q[0]
抗坏血酸过氧化物酶#松弛操作，并且满⾜条件的后代⼊队
for key in dict:
if length[head]+G[head][key]<=length[key]:
length[key]=length[head]+G[head][key]
Q.append(key)
#松弛完毕，队头出列
del Q[0]
if len(Q)!=0:
dict=G[Q[0]]
#优先队列法实现
def branch(G, v0):
Q.append(v0)
while len(Q) != 0:
min=99999
flag=0
#到队列中距离源点最近的点
for v in Q:
if min > length[v]:
min=length[v]
flag = v
head = flag
dict=G[head]
#到扩散点后进⾏松弛操作
for key in dict:
if length[head] + G[head][key] <= length[key]:
length[key] = length[head] + G[head][key]
Q.append(key)
#松弛完毕后，该扩散点出队
branch(G,1)
print(length[1:])
看到这⾥，其实可以看出优先队列的分⽀限界算法和Dijkstra算法的相似性很⼤，都是取离源点最近的点做扩散点，但是不同在于优先队列的分⽀限界可以让边权为负（但是负权环路会造成死循环），⽽Dijkstra不⾏，因为两者维护的队列的意义不同。
回溯法
**核⼼思想:**按选优条件向前搜索，以达到⽬标。但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择，这种⾛不通就退回再⾛的技术为回溯法，⽽满⾜回溯条件的某个状态的点称为“回溯点”。
回溯法按深度优先策略搜索问题的解空间树。⾸先从根节点出发搜索解空间树，当算法搜索⾄解空间树的某⼀节点时，先利⽤剪枝函数判断该节点是否可⾏（即能得到问题的解）。如果不可⾏，则跳过对该节点为根的⼦树的搜索，逐层向其祖先节点回溯；否则，进⼊该⼦树，继续按深度优先策略搜索。
回溯法的基本⾏为是搜索，搜索过程使⽤剪枝函数来为了避免⽆效的搜索。剪枝函数包括两类：
1. 使⽤约束函数，剪去不满⾜约束条件的路径；
2. 使⽤限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：
1. ⼦集树
2. 排列树。
为了说明这两个概念的区别，我们⾸先假定有⼀个集合⼦树集
当我们求解的结果是集合的某⼀⼦集的时候，其对应的解空间是⼦集树。时间复杂度O(
)
排列树
当我们求解的结果是集合S的元素的某⼀种排列的时候，其对应的解空间就是排列树。时间复杂度O()
解空间为排列树的典型问题就是旅⾏售货员问题。
回溯法解0-1背包问题
问题描述：给定n种物品和⼀背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤?
S
S 2n n !
问题分析：问题是n个物品中选择部分物品，可知，问题的解空间是⼦集树。⽐如物品数⽬n=3时，其解空间树如下图，边为1代表选择该物品，边为0代表不选择该物品。使⽤x[i]表⽰物品i是否放⼊背包，x[i]=0表⽰不放，x[i]=1表⽰放⼊。回溯搜索过程，如果来到了叶⼦节点，表⽰⼀条搜索路径结束，如果该路径上存在更优的解，则保存下来。如果不是叶⼦节点，是中点的节点（如B），就遍历其⼦节点（D 和E），如果⼦节点满⾜剪枝条件，就继续回溯搜索⼦节点。
python实现源代码:
N=3 #物品的数量
C=16 #背包的容量
w = [10,8,5] # 每个物品的重量
v = [5,4,1] # 每个物品的价值
x = [0,0,0] # 0-1表状态：不放⼊和放⼊
CurWeight=0 #当前放⼊背包的物品总重量
CurValue=0 #当前放⼊背包的物品总价值
BestValue=0 # 最优值；当前的最⼤价值，初始化为0
BestX =[0,0,0]# 最优解；
def backtrack(t):
global N,C,w,y,x,CurWeight,CurValue,BestValue,BestX
if t>N-1:
if CurValue>BestValue :
BestValue = CurValue
BestX = x
else:
for i in range(2):
面瘫的中药
x[t] = i
if i==0:
backtrack(t + 1)
else:
if CurWeight+w[t] <= C:
CurWeight += w[t]
CurValue += v[t]
backtrack(t + 1)
CurWeight -= w[t]
CurValue -= v[t]
基础的讲解就到这⾥，后续还会添加⼀些经典问题，⽐如N皇后、迷宫之类的。
迷宫问题
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议