【算法】回溯法

【算法】回溯法


回溯法

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。

利用深度优先在空间树中找出满足条件的所有解

剪枝函数

剪枝函数包括两类:

  1. 约束函数:用于去除不满足条件的
  2. 限界函数:用于获取最优解

解题框架步骤

也是利用了递归,其实本质上也是一种“在所有情况中遍历出解”的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void backtrack(int t)          //t表示递归深度,即当前扩展节点在解空间树的深度
{
if ( t > n ) output(x); //n控制递归深度,如果算法已经搜索到叶节点,记录输出可行解X
else
{
for(int i = f(n,t) ; i <= g(n,t) ; i++) //在深度t,i从未搜索过得起始编号到终止编号
{
x[t] = h(i); //查看i这个点的值是否满足题目的要求
if( constraint(t) && bound(t))
backtrack(t+1)
//constraint(t)为true表示在当前扩展节点处x[1:t]的取值满足问题的约束条件;
//bound(t)为true表示当前扩展节点取值没有使目标函数越界;
//为true表示还需要进一步的搜索子树,否则减去子树。
}
}

 
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×