迪三
0%

五.分支限界

发表于 分类于 Valine：

原创 进阶算法概述

五.回溯算法

1.算法本质

  • 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

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

2.算法步骤

利用一个队列，进行对树或图的广度优先遍历

  • 伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
q = queue()
q.put(s) # 插入原点
v[s][s] = 0
def f(x):
    while true:
        i=q.get() 
        if !q.empty() :
            j=q.pull() #出队
            v[s][j]=v[s][j-1]+s.value()
            if i != x:
                while s.next():
                    q.put(s.next()) #入队
        else:
            break;
f(x)
print(min(v[s][x]))

3.典型应用

3.1 单源最短路径

3.2 TSP问题