回溯法

回溯法概念

回溯算法有“通用的解题法”之称。用它可以系统地搜索一个问题的所在解或任一解。回溯法是一个即带有系统性又带有跳跃性的所搜算法。

回溯法思想

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

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法解题步骤

用回溯法解题通常包含以下3个步骤：
1. 针对所给问题，定义问题的解空间
2. 确定易于搜索的解空间结构
3. 以深度优先方式所搜解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯算法一般框架

int solution[MAX_DIMENSION];    //多维度解
void backtrack(int dimension)
{/*检验当前维度数组是否是一个解*/if ( solution[] is well-generated ){check and record solution;return;}/* 列举当前维度的所有取值的情况，并且进入到下一维度*/for ( x = each value of current dimension ){solution[dimension] = x;backtrack( dimension + 1 );}
}

backtrack( [v1,...,vn] )    // [v1,...,vn]是多维度数值
{/*检验当前多维度数值是不是一个解*/if ( [v1,...,vn] is well-generated ){if ( [v1,...,vn] is a solution ) process solution;return;}/* 列举当前维度的所有取值的情况，并且进入到下一维度*/for ( x = possible values of vn+1 )backtrack( [v1,...,vn, x] );
}

使用回溯法解决排列问题

Question: 列出 {0,1,2,3,4} 所有的排列

int solution[5];
bool use[5] = {false};void backtrac

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！