核心思想

分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

求解目标

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

• 是一种在问题的解空间树T上搜索问题解的算法。
• 求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

搜索方式

以广度优先或以最小代价优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

常见的两种分支限界法

所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。

队列式分支限界法

• 按照队列先进先出（FIFO）原则选取下一个结点为扩展结点
• 从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同

优先队列分支限界法（代价最小或效益最大）

• 每个结点都有一个对应的耗费或收益，以此决定结点的优先级
• 从优先队列中选取优先级最高的结点成为当前扩展结点
• 如果查找一个具有最小耗费的解：则活结点表可用小顶堆来建立，下一个扩展结点就是具有最小耗费的活结点
• 如果希望搜索一个具有最大收益的解：则可用大顶堆来构造活结点表，下一个扩展结点是具有最大收益的活结点

分支限界法解决的常见问题

• 0/1背包问题
• 对于有非负边权的有向图G，从源顶点s到目标顶点t之间的最短路径问题
• 货郎担问题（经过每个节点一次且仅当一次，然后返回原点，求此过程的最短距离及路径）

算法示例

• 单源最短路径

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径

# 初始化图参数 用字典初始初始化这个图
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_fifo(di, v0):
    Q.append(v0)  # 加入顶点
    d = di[1]  # dict 获取顶点到最近节点的字典
    while len(Q) != 0:
        head = Q[0]  # 队列头元素出队
        # 松弛操作，并且满足条件的后代入队
        for key in d:  # dict遍历
            # 判断顶点到目标点的距离是否小于指定的距离， 分界限定判断
            if length[head] + di[head][key] <= length[key]:
                length[key] = length[head] + di[head][key]  # 顶点到目标点的距离重新赋值
                Q.append(key)  # 符合要求进入下次判断
        # 松弛完毕，队头出列
        del Q[0]
        if len(Q) != 0:
            d = di[Q[0]]

# 优先队列法实现
def branch_queue(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)
        # 松弛完毕后，该扩散点出队
        Q.remove(head)

总结

人生苦短，我用python！

#python##学习##程序员#